Search

In this paper, we continue our study of 2-colorings in hypergraphs (see, Henning and Yeo, 2013). A hypergraph is 2-colorable if there is a 2-coloring of the vertices with no monochromatic hyperedge. It is known (see Thomassen, 1992) that every 4-uniform 4-regular hypergraph is 2-colorable. Our main result in this paper is a strengthening of this result. For this purpose, we define a vertex in a hypergraph H to be a free vertex in H if we can 2-color V ( H ) ∖ { v } such that every hyperedge in H contains vertices of both colors (where v has no color). We prove that every 4-uniform 4-regular hypergraph has a free vertex. This proves a conjecture in Henning and Yeo (2015). Our proofs use a new result on not-all-equal 3-SAT which is also proved in this paper and is of interest in its own right. [ABSTRACT FROM AUTHOR]

Recently, Balogh et al. (2018) answered in negative the question that was posed in several earlier papers whether the packing chromatic number is bounded in the class of graphs with maximum degree 3. In this note, we present an explicit infinite family of subcubic graphs with unbounded packing chromatic number. [ABSTRACT FROM AUTHOR]

In this paper we investigate light dual multinets labeled by a finite group in the projective plane P G ( 2 , K ) defined over a field K . We present two classes of new examples. Moreover, under some conditions on the characteristic of K , we classify group-labeled light dual multinets with lines of length at least 9. [ABSTRACT FROM AUTHOR]

Finding the maximum number of maximal independent sets in an n -vertex graph G , i ( G ) , from a restricted class is an extensively studied problem. Let k K 2 denote the matching of size k , that is a graph with 2 k vertices and k disjoint edges. A graph with an induced copy of k K 2 contains at least 2 k maximal independent sets. The other direction was established in a series of papers (Farber, 1989; Balas and Yu, 1989; Farber, 1993) finally yielding i ( G ) ≤ ( n ∕ k ) 2 k for a graph G without an induced ( k + 1 ) K 2 . Alekseev proved in Alekseev (2007) that i ( G ) is at most the number of induced matchings of G . This work generalises the aforementioned results to clutters. The right substructures in this setting are minors rather than induced subgraphs. Maximal independent sets of a clutter H are in one-to-one correspondence to the sets of its blocker, b ( H ) , hence i ( H ) = | b ( H ) | . We show that | b ( H ) | ≤ ∑ m = 0 k ⋅ f ( r ) | H | m r 2 m for a ( k + 1 ) K 2 -minor-free clutter H where f ( r ) = ( 2 r − 3 ) 2 r − 2 and r is the maximum size of a set in H . A key step in the proofs is, similarly to Alekseev’s result, showing that i ( H ) is bounded by the number of a substructure called semi-matching, and then proving a dependence between the number of semi-matchings and the number of minor matchings. Note that similarly to graphs, a clutter containing a k K 2 minor has at least 2 k maximal independent sets. From a computational perspective, a polynomial number of independent sets is particularly interesting. Our results lead to polynomial algorithms for restricted instances of many problems including Set Cover and k -SAT. [ABSTRACT FROM AUTHOR]

A spanning subgraph F of a graph G is called a { P 2 , C 2 i + 1 : i ≥ k } -factor if each component of F is isomorphic to either a path of order 2 or a cycle of order 2 i + 1 for some i ≥ k . In this paper, we obtain the following two results (here c i ( G − X ) is the number of components C of G − X with | V ( C ) | = i ): (i) If a graph G satisfies c 1 ( G − X ) + c 3 ( G − X ) ≤ 1 2 | X | for all X ⊆ V ( G ) , then G has a { P 2 , C 2 i + 1 : i ≥ 2 } -factor. (ii) For k ≥ 3 , if a graph G satisfies ∑ 0 ≤ j ≤ k − 1 c 2 j + 1 ( G − X ) ≤ 2 5 ( k 2 − 1 ) | X | for all X ⊆ V ( G ) , then G has a { P 2 , C 2 i + 1 : i ≥ k } -factor. [ABSTRACT FROM AUTHOR]

In this paper we consider the possibility that groups S n w r S 2 , 4 ≤ n ≤ 63 , act flag-transitively on block designs with n 2 points. We rule out n ∈ { 7 , 11 , 15 , 19 , 23 , 31 , 35 , 43 , 47 , 59 } and confirm the required action for other n in the given range through performing the construction of base blocks of the desired designs. Our construction makes use of flag-transitive incidence structures and weakly flag-transitive incidence structures. [ABSTRACT FROM AUTHOR]

Abstract: This paper investigates a competitive version of the coloring game on a finite graph . An asymmetric variant of the -relaxed coloring game is called the -relaxed -coloring game. In this game, two players, Alice and Bob, take turns coloring the vertices of a graph , using colors from a set , with . On each turn Alice colors vertices and Bob colors vertices. A color is legal for an uncolored vertex if by coloring with color , the subgraph induced by all the vertices colored with has maximum degree at most . Each player is required to color an uncolored vertex legally on each move. The game ends when there are no remaining uncolored vertices. Alice wins the game if all vertices of the graph are legally colored, Bob wins if at a certain stage there exists an uncolored vertex without a legal color. The -relaxed -game chromatic number of , denoted -, is the least for which Alice has a winning strategy in the -relaxed -coloring game. This paper extends the well-studied activation strategy of coloring games to relaxed asymmetric coloring games. The extended strategy is then applied to the -relaxed -coloring games on planar graphs, partial -trees and -pseudo-partial -trees. This paper shows that for planar graphs , if , then - for all . If is a partial -tree, , then - for all . If is an -pseudo-partial -tree, , let , then - for all . For planar graphs and , - for all . These results extend the corresponding -relaxed -coloring game results to more generalized asymmetric cases. [Copyright &y& Elsevier]

Abstract: Let be an integer and a bipartite graph with such that . In this paper it has been proved that if for each pair of nonadjacent vertices and , , then for any independent edges of , has a 2-factor with cycles such that and for each . We shall also show that the conditions in this paper are sharp. [Copyright &y& Elsevier]

Abstract: This paper investigates a competitive version of the coloring game on a finite graph . An asymmetric variant of the -relaxed coloring game is called the -relaxed -coloring game. In this game, two players, Alice and Bob, take turns coloring the vertices of a graph , using colors from a set , with . On each turn Alice colors vertices and Bob colors vertices. A color is legal for an uncolored vertex if by coloring with color , the subgraph induced by all the vertices colored with has maximum degree at most . Each player is required to color an uncolored vertex legally on each move. The game ends when there are no remaining uncolored vertices. Alice wins the game if all vertices of the graph are legally colored, Bob wins if at a certain stage there exists an uncolored vertex without a legal color. The -relaxed -game chromatic number, denoted by , of is the least for which Alice has a winning strategy in the -relaxed -coloring game. The -relaxed -coloring game has been well studied and there are many interesting results. For the -relaxed -coloring game, this paper proves that if a graph has an orientation with maximum outdegree and , then for all ; If , then - for all . [Copyright &y& Elsevier]

Abstract: Let be a regular covering projection of connected graphs with the group of covering transformations isomorphic to N. If N is an elementary abelian p-group, then the projection is called p-elementary abelian. The projection is vertex-transitive (edge-transitive) if some vertex-transitive (edge-transitive) subgroup of the automorphism group of X lifts along , and semisymmetric if it is edge- but not vertex-transitive. The projection is minimal semisymmetric if it cannot be written as a composition of two (nontrivial) regular covering projections, where is semisymmetric. Malnič et al. [Semisymmetric elementary abelian covers of the Möbius–Kantor graph, Discrete Math. 307 (2007) 2156–2175] determined all pairwise nonisomorphic minimal semisymmetric elementary abelian regular covering projections of the Möbius–Kantor graph, the Generalized Petersen graph , by explicitly giving the corresponding voltage rules generating the covering projections. It was remarked at the end of the above paper that the covering graphs arising from these covering projections need not themselves be semisymmetric (a graph with regular valency is said to be semisymmetric if its automorphism group is edge- but not vertex-transitive). In this paper it is shown that all these covering graphs are indeed semisymmetric. [Copyright &y& Elsevier]

Abstract: In this paper we investigate a new graph reconstruction problem which was introduced in a paper by Levenshtein, Konstantinova, Konstantinov and Molodtsov [Reconstruction of a graph from 2-vicinities of its vertices, Discrete Appl. Math., accepted for publication], motivated by reconstruction of chemical compounds. It consists of the exact reconstruction of an unknown simple connected graph G from subsets of vertices which are metric balls of radius r () around all its vertices. A metric ball of radius r about vertex is the set of all vertices of distance at most r from . The value is introduced which is equal to the minimum number t such that a simple connected graph G without terminal vertices with girth at least t is reconstructible from metric balls of radius r around all its vertices. Consideration of the cycle graph with vertices shows that . We conjecture that . The main result is the upper bound which, in particular, implies that this conjecture is true for . Moreover, it is proved that if the knowledge of metric balls of radius r around all vertices of a simple connected graph G without terminal vertices with girth at least allows one to determine at least one edge of G. [Copyright &y& Elsevier]

Abstract: We give a simple alternative proof of the representation theorem of all genus two 3-manifolds by a 6-parameter family of integers, due to Casali and Grasselli (see [M.R. Casali, A catalogue of the genus two 3-manifolds, Atti. Sem. Mat. Fis. Univ. Modena 37 (1989) 207–236]; [M.R. Casali, L. Grasselli, 2-Symmetric crystallizations and 2-fold branched coverings of , Discrete Math. 87 (1991) 9–22]). Our approach is different from that of the quoted papers, and it is based on the concept of extended Heegaard diagram. This permits to obtain new topological meanings of the arithmetic conditions which the parameters must satisfy for representing closed manifolds. Some applications and results on some homology spheres of genus 2 complete the paper. [Copyright &y& Elsevier]

Abstract: We investigate the free complex of a convex geometry. Edelman and Reiner showed that the free complex of a convex geometry is contractible. Moreover, their paper stated a conjecture about the topology of free complexes. This paper proves their conjecture. [Copyright &y& Elsevier]

Abstract: This paper deals with multialgebras. An important tool in the theory of multialgebras is the fundamental relation, which brings us into the class of the universal algebras. In this paper we will present the construction of the direct limit of a direct system of multialgebras, some basic properties of this construction, and we will see that the fundamental algebra of the direct limit of multialgebras is the direct limit of the fundamental algebras of the given multialgebras. [Copyright &y& Elsevier]

Abstract: A graph H of order n is said to be k-placeable into a graph G of order n, if G contains k edge-disjoint copies of H. It is well known that any non-star tree T of order n is 2-placeable into the complete graph . In the paper by Kheddouci et al. [Packing two copies of a tree into its fourth power, Discrete Math. 213 (2000) 169–178], it is proved that any non-star tree T is 2-placeable into . In this paper, we prove that any non-star tree T is 2-placeable into . [Copyright &y& Elsevier]

Abstract: In this paper we formulate four families of problems with which we aim at distinguishing different levels of randomness. The first one is completely non-random, being the ordinary Ramsey–Turán problem and in the subsequent three problems we formulate some randomized variations of it. As we will show, these four levels form a hierarchy. In a continuation of this paper we shall prove some further theorems and discuss some further, related problems. [Copyright &y& Elsevier]

Abstract: The aim of this paper is to define the notions of -valued Lukasiewicz-Moisil algebra of fractions and maximal algebra of fractions taking as a guide-line the elegant construction of a complete ring of fractions by partial morphisms introduced by [Lambek, 1996. Lectures on Rings and Modules, p. 36]. For some informal explanations of the notion of fraction see [Lambek, 1996. Lectures on Rings and Modules, p. 36] In the last part of this paper we prove the existence of a maximal n-valued Lukasiewicz–Moisil algebra of fractions for an n-valued Lukasiewicz–Moisil algebra (Theorem 3.2) and we give an explicit description of this -valued Lukasiewicz–Moisil algebra for some classes of -valued Lukasiewicz–Moisil algebras (finite, chains, Boolean algebras). [Copyright &y& Elsevier]

Abstract: The Steiner trade spectrum of a simple graph G is the set of all integers t for which there is a simple graph H whose edges can be partitioned into t copies of G in two entirely different ways. The Steiner trade spectra of complete partite graphs were determined in all but a few cases in a recent paper by Billington and Hoffman (Discrete Math. 250 (2002) 23). In this paper we resolve the remaining cases. [Copyright &y& Elsevier]

The distance d(u,v) from vertex u to vertex v in a digraph G is the length of the shortest directed path from u to v. The eccentricity e(v) of vertex v is the maximum distance of v to any other vertex of G. A vertex u is an eccentric vertex of vertex v if the distance from v to u is equal to the eccentricity of v. The eccentric digraph ED(G) of a digraph G is the digraph that has the same vertex set as G and the arc set defined by: there is an arc from u to v iff v is an eccentric vertex of u. The idea of the eccentric digraph of a graph was introduced by Buckley (Congr. Numer. 149 (2001) 65) and the idea of the eccentric digraph of a digraph by Boland and Miller (Proceedings of AWOCA’01, July 2001, p. 66). In this paper, we examine eccentric digraphs of digraphs for various families of digraphs and we consider the behaviour of an iterated sequence of eccentric digraphs of a digraph. The paper concludes with several open problems. [Copyright &y& Elsevier]

In this paper we consider S-prime graphs, that is the graphs that cannot be represented as nontrivial subgraphs of nontrivial Cartesian products of graphs. Lamprey and Barnes characterized S-prime graphs via so-called basic S-prime graphs that form a subclass of all S-prime graphs. However, the structure of basic S-prime graphs was not known very well. In this paper we prove several characterizations of basic S-prime graphs. In particular, the structural characterization of basic S-prime graphs of connectivity 2 enables us to present several infinite families of basic S-prime graphs. Furthermore, simple S-prime graphs are introduced that form a relatively small subclass of basic S-prime graphs, and it is shown that every basic S-prime graph can be obtained from a simple S-prime graph by a sequence of certain transformations called extensions. [Copyright &y& Elsevier]

Extremal combinatorics is an area in discrete mathematics that has developed spectacularly during the last decades. This paper contains a collection of problems and results in the area, including solutions or partial solutions to open problems suggested by various researchers in extremal graph theory, extremal finite set theory and combinatorial geometry. This is not meant to be a comprehensive survey of the area, it is merely a collection of various extremal problems, which are hopefully interesting. The choice of the problems is inevitably somewhat biased, and as the title of the paper suggests I hope to write a related paper in the future. Each section of this paper is essentially self contained, and can be read separately. [Copyright &y& Elsevier]

In their paper on minimal graphs with crossing number at least k (or, equivalently, k-crossing-critical graphs) (J. Combin. Theory Ser. B 58 (2) (1993) 217–224) Richter and Thomassen described a construction of an infinite family of 4-regular 3-crossing-critical graphs. They also showed that no infinite family of 6-regular k-crossing-critical graphs exists. In this paper we generalize the Richter and Thomassen construction, and prove the following result: for each rational number q∈[4,6) there is an infinite family of graphs that are k-crossing-critical for the same integer k, each of which has average degree q. Moreover, we show that for each rational number q∈[4,6) this statement holds for infinitely many values of k. [Copyright &y& Elsevier]

In this paper we investigate colorings of sets avoiding similarly colored subsets. If S is an arbitrary colored set and T is a fixed family of bijections of S to itself, then two subsets A,B⊆S are said to be colored similarly with respect to T, if there exists a transformation t∈T mapping A onto B, and preserving a coloring of A. This general setting covers some well-known topics such as non-repetitive sequences of Thue or the famous Hadwiger–Nelson problem on unit distances in Euclidean spaces. Our main theorem of this paper concerns arbitrary infinite sets, however, the most striking consequences are obtained for the case of Euclidean spaces. For instance, there exist 2-colorings of Rn with no two different line segments colored similarly, with respect to translations. The method is based on the principle of induction, hence it is not constructive in general, and the problem of explicit constructions arises naturally. We give two such examples of non-repetitive colorings of the sets R and Q, with respect to translations. In conclusion of the paper we discuss possible generalizations and pose two open problems. [Copyright &y& Elsevier]

In the present paper we present some tools in exploring the shadow process in self–dual codes for the purpose of finding singly even self–dual binary codes with higher minimal distances. The present paper can be viewed as a supplementary work to the preceding works (IEEE Trans. Inform. Theory 36 (1990) 1319; IEEE Trans. Inform Theory 37 (1991) 1222). [Copyright &y& Elsevier]

A T -decomposition of a graph G is a set of edge-disjoint copies of T in G that cover the edge set of G . Graham and Häggkvist (1989) conjectured that any 2 ℓ -regular graph G admits a T -decomposition if T is a tree with ℓ edges. Kouider and Lonc (1999) conjectured that, in the special case where T is the path with ℓ edges, G admits a T -decomposition D where every vertex of G is the end-vertex of exactly two paths of D , and proved that this statement holds when G has girth at least ( ℓ + 3 ) ∕ 2 . In this paper we verify Kouider and Lonc’s Conjecture for paths of length 4 . [ABSTRACT FROM AUTHOR]

For a graph H , the circumference of H , denoted by c ( H ) , is the length of a longest cycle in H . It is proved in Chen (2016) that if H is a 3-connected claw-free graph of order n with δ ≥ 8 , then c ( H ) ≥ min { 9 δ − 3 , n } . In Li (2006), Li conjectured that every 3-connected k -regular claw-free graph H of order n has c ( H ) ≥ min { 10 k − 4 , n } . Later, Li posed an open problem in Li (2008): how long is the best possible circumference for a 3-connected regular claw-free graph? In this paper, we study the circumference of 3-connected claw-free graphs without the restriction on regularity and provide a solution to the conjecture and the open problem above. We determine five families F i ( 1 ≤ i ≤ 5 ) of 3-connected claw-free graphs which are characterized by graphs contractible to the Petersen graph and show that if H is a 3-connected claw-free graph of order n with δ ≥ 16 , then one of the following holds: (a) either c ( H ) ≥ min { 10 δ − 3 , n } or H ∈ F 1 . (b) either c ( H ) ≥ min { 11 δ − 7 , n } or H ∈ F 1 ∪ F 2 . (c) either c ( H ) ≥ min { 11 δ − 3 , n } or H ∈ F 1 ∪ F 2 ∪ F 3 . (d) either c ( H ) ≥ min { 12 δ − 10 , n } or H ∈ F 1 ∪ F 2 ∪ F 3 ∪ F 4 . (e) if δ ≥ 23 then either c ( H ) ≥ min { 12 δ − 7 , n } or H ∈ F 1 ∪ F 2 ∪ F 3 ∪ F 4 ∪ F 5 . This is also an improvement of the prior results in Chen (2016), Lai et al. (2016), Li et al. (2009) and Mathews and Sumner (1985). [ABSTRACT FROM AUTHOR]

The leaf distance of a tree is the maximum d such that the distance between any pair of leaves in the tree is at least d . Kaneko provided sufficient conditions to force the existence of a spanning tree with leaf distance at least d = 3 and conjectured that similar conditions suffice for larger d . The case when d = 4 was later proved by Kaneko, Kano, and Suzuki. In this paper, we show that when d ≥ 4 , a stronger form of this conjecture holds for graphs with independence number at most five. As an immediate corollary, we obtain that when d ≥ n ∕ 3 , this stronger version holds for all n -vertex graphs, consequently proving Kaneko’s conjecture for d ≥ n ∕ 3 . [ABSTRACT FROM AUTHOR]

Let k⩾3 be an integer. Denote by Tk the following statement:If a graph G is a non-star graph without cycles of length ⩽k then G is a subgraph of its complement.It has been conjectured by Faudree, Rousseau, Schelp and Schuster that T4 holds. As far as we know the best general result is in the paper of Brandt who proved that T6 holds.In this paper we give an another, relatively short proof of Brandt''s result. [Copyright &y& Elsevier]

Hedayat et al. first introduced balanced sampling plans for the exclusion of contiguous units. Wright detailed the results of a preliminary investigation of two-dimensional balanced sampling plans avoiding adjacent units (2-BSAs), and pointed out explicitly three types of 2-BSAs, which have different adjacency scheme, namely “Row and Column”, “Sharing a Border” and “Island”. This paper will provide more details for the three types of 2-BSAs from the point of view of design theory. [ABSTRACT FROM AUTHOR]