Search

Rota's basis conjecture (RBC) states that given a collection B of n bases in a matroid M of rank n, one can always find n disjoint rainbow bases with respect to B . In this paper, we show that if M has girth at least n - o (n) , and no element of M belongs to more than o (n) bases in B , then one can find at least n - o (n) disjoint rainbow bases with respect to B . More specifically, we show that if M has girth at least n - β (n) + 1 and each element belongs to no more than κ (n) bases in B , then letting γ (n) = 4 (κ (n) + β (n) + 1) 2 , one can find at least n - γ (n) disjoint rainbow bases provided 2 γ (n) < n . This result can be seen as an extension of the work of Geelen and Humphries, who proved RBC in the case where M is paving, and B is a pairwise disjoint collection. The proofs here are based on modifications to the cascade idea introduced by Bucić et al. [ABSTRACT FROM AUTHOR]

A graph G of order n is said to be k-factor-critical for integers 1 ≤ k < n , if the removal of any k vertices results in a graph with a perfect matching. 1- and 2-factor-critical graphs are the well-known factor-critical and bicritical graphs, respectively. A k-factor-critical graph G is called minimal if for any edge e ∈ E (G) , G - e is not k-factor-critical. In 1998, O. Favaron and M. Shi conjectured that every minimally k-factor-critical graph of order n has the minimum degree k + 1 and confirmed it for k = 1 , n - 2 , n - 4 and n - 6 . In this paper, we use a simple method to reprove the above results. As a main result, the further use of this method enables us to prove the conjecture to be true for k = n - 8 . We also obtain that every minimally (n - 6) -factor-critical graph of order n has at most n - Δ (G) vertices with the maximum degree Δ (G) for Δ (G) ≥ n - 4 . [ABSTRACT FROM AUTHOR]

A celebrated unresolved conjecture of Erdös and Hajnal states that for every undirected graph H there exists ϵ (H) > 0 such that every undirected graph on n vertices that does not contain H as an induced subgraph contains a clique or a stable set of size at least n ϵ (H) . This conjecture has a directed equivalent version stating that for every tournament H there exists ϵ (H) > 0 such that every H-free n-vertex tournament T contains a transitive subtournament of size at least n ϵ (H) . Recently the conjecture was proved for all six-vertex tournaments, except K 6 . In this paper we construct two infinite families of tournaments for which the conjecture is still open for infinitely many tournaments in these two families—the family of so-called super nebulas and the family of so-called super triangular galaxies. We prove that for every super nebula H 1 and every Δ galaxy H 2 there exist ϵ (H 1 , H 2) such that every { H 1 , H 2 } -free tournament T contains a transitive subtournament of size at least ∣ T ∣ ϵ (H 1 , H 2) . We also prove that for every central triangular galaxy H there exist ϵ (K 6 , H) such that every { K 6 , H } -free tournament T contains a transitive subtournament of size at least ∣ T ∣ ϵ (K 6 , H) . And we give an extension of our results. [ABSTRACT FROM AUTHOR]

Recently, in the paper (Cheon et al. in Linear Algebra Appl 579:89–135, 2019) we suggested the two conjectures about the diameter of io-decomposable Riordan graphs of the Bell type. In this paper, we give a counterexample for the first conjecture. Then we prove that the first conjecture is true for the graphs of some particular size and propose a new conjecture. Finally, we show that the second conjecture is true for some special io-decomposable Riordan graphs. [ABSTRACT FROM AUTHOR]

A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number is the minimum cardinality of a paired-dominating set of G. The paired-domination subdivision number is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the paired-domination number. It was conjectured that the paired-domination subdivision number is at most n - 1 for every connected graph G of order n ≥ 3 which does not contain isolated vertices. In this paper, we settle the conjecture in the affirmative. [ABSTRACT FROM AUTHOR]

Berge Conjecture states that every bridgeless cubic graph has 5 perfect matchings such that each edge is contained in at least one of them. In this paper, we show that Berge Conjecture holds for bridgeless cubic graphs which have two perfect matchings with at most one common edge. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph, and D(G) be the distance matrix of G. Suppose that D max (G) and λ 1 (G) are the maximum row sum and the spectral radius of D(G), respectively. In this paper, we give a lower bound for D max (G) - λ 1 (G) , and characterize the extremal graphs attaining the bound. As a corollary, we solve a conjecture posed by Liu, Shu and Xue. [ABSTRACT FROM AUTHOR]

Let n, k, t be positive integers. What is the maximum number of arcs in a digraph on n vertices in which there are at most t distinct walks of length k with the same endpoints? Denote f (t) = max { 2 t + 1 , 2 2 t + 9 / 4 + 1 / 2 + 3 } . In this paper, we prove that the maximum number is equal to n (n - 1) / 2 and the extremal digraph are the transitive tournaments when k ≥ n - 1 ≥ f (t) . Based on this result, we may determine the maximum numbers and the extremal digraphs when k ≥ f (t) and n is sufficiently large, which generalizes the existing results. A conjecture is also presented. [ABSTRACT FROM AUTHOR]

Let μ (G) denote the mean color number of a graph G. Dong proposed two mean color conjectures. One is that for any graph G and a vertex w in G with d (w) ≥ 1 , if H is a graph obtained from G by deleting all but one of the edges which are incident to w, then μ (G) ≥ μ (H) . The other is that for any graph G and a vertex w in G, μ (G) ≥ μ ((G - w) ∪ K 1) . In this paper, we show that the two conjectures hold under the condition that w is a simplicial vertex in G. And when G is a connected (n, m)-graph and w is not a cut vertex in G with d (w) = n - 1 , if m ≤ (2 2 + 2) n - 4.5 - 2 , the second conjecture holds too. The two conjectures also hold for some special cases, such as wheels and chordal graphs (Dong in J Combin Theory Ser B 87: 348–365, 2003). [ABSTRACT FROM AUTHOR]

Let G be a graph and k an integer with 2 ≤ k ≤ n . The k-tree-connectivity of G, denoted by κ k (G) , is defined as the minimum κ G (S) over all k-subsets S of vertices, where κ G (S) denotes the maximum number of internally disjoint S-trees in G. The k-path-connectivity of G, denoted by π k (G) , is defined as the minimum π G (S) over all k-subsets S of vertices, where π G (S) denotes the maximum number of internally disjoint S-paths in G. In this paper, we first prove that for any fixed integer k ≥ 1 , given a graph G and a subset S of V(G), deciding whether π G (S) ≥ k is NP -complete. Moreover, we also show that for any fixed integer k 1 ≥ 5 , given a graph G, a k 1 -subset S of V(G) and an integer 1 ≤ k 2 ≤ n - 1 , deciding whether π G (S) ≥ k 2 is NP -complete. Let π (k , ℓ) = 1 + max { κ (G) | G \ is\ a\ graph\ with π k (G) < ℓ } . Hager (Discrete Math 59:53–59, 1986) showed that ℓ (k - 1) ≤ π (k , ℓ) ≤ 2 k - 2 ℓ and conjectured that π (k , ℓ) = ℓ (k - 1) for k ≥ 2 and ℓ ≥ 1 . He also confirmed the conjecture for 2 ≤ k ≤ 4 and proved π (5 , ℓ) ≤ ⌈ 9 2 ℓ ⌉ . By introducing a "Generalized Path-Bundle Transformation", we confirm the conjecture for k = 5 and prove that π (k , ℓ) ≤ 2 k - 3 ℓ for k ≥ 5 and ℓ ≥ 1 . By employing this transformation, we also prove that if G is a graph with κ (G) ≥ (k - 1) ℓ for any k ≥ 2 and ℓ ≥ 1 , then κ k (G) ≥ ℓ . [ABSTRACT FROM AUTHOR]

Bermond et al in 1980 proved that if the size of a strong digraph D of order n is at least n - k + 2 2 + k - 1 , k ≥ 2 , then the girth of D is no more than k. Consequently, when D is a 3-free strong digraph of order n without loops or parallel arcs, which means that every directed cycle in D has length at least 4, the maximum size of D is n - 1 2 + 1 . In 2008, Seymour et al proved that if D is a 3-free digraph, then β (D) ≤ γ (D) , and they further conjectured that β (D) ≤ 1 2 γ (D) for every 3-free digraph D, where β (D) denotes the size of the smallest subset X ⊆ A (D) , such that D \ X is acyclic, and γ (D) is the number of unordered pairs { u , v } of vertices such that u, v are nonadjacent in D. In this paper, we first describe all 3-free strong digraphs of order n with the maximum size n - 1 2 + 1 . Then we prove that such 3-free strong digraphs satisfy the minimum out-degree of D equals 1 and β (D) ≤ 1 2 γ (D) . Moreover, we prove that if the minimum out-degree of a 3-free strong digraph D is at least 2, then the maximum size of D is between n - 1 2 - 2 and n - 1 2 . [ABSTRACT FROM AUTHOR]

This paper disproves a conjecture in Wang et al. (Graphs Comb. 31:1779–1787, 2015) and answers in the negative a question in Dvořák et al. (Electron J Comb:P26, 2019). In return, we pose five open problems. [ABSTRACT FROM AUTHOR]

A finite subset of a Euclidean space is called an s-distance set if there exist exactly s values of the Euclidean distances between two distinct points in the set. In this paper, we prove that the maximum cardinality among all 5-distance sets in R 3 is 20, and every 5-distance set in R 3 with 20 points is similar to the vertex set of a regular dodecahedron. [ABSTRACT FROM AUTHOR]

Zarankiewicz's conjecture states that the crossing number cr (K m , n) of the complete bipartite graph K m , n is Z (m , n) : = ⌊ m 2 ⌋ ⌊ m - 1 2 ⌋ ⌊ n 2 ⌋ ⌊ n - 1 2 ⌋ , where ⌊ x ⌋ denotes the largest integer no more than x. It is conjectured that the crossing number cr (K 1 , m , n) of the complete tripartite graph K 1 , m , n is Z (m + 1 , n + 1) - ⌊ m 2 ⌋ ⌊ n 2 ⌋ . When one of m and n is even, Ho proved that this conjecture is true if Zarankiewicz's conjecture holds, in 2008. When both m and n are odd, Ho proved that cr (K 1 , m , n) ≥ cr (K m + 1 , n + 1) - n m ⌊ m 2 ⌋ ⌊ m + 1 2 ⌋ and conjectured that equality holds in this inequality. Which one of the conjectures may be true? In this paper, we proved that if Zarankiewicz's conjecture holds, then the former one is true. [ABSTRACT FROM AUTHOR]

A graph G has the strong parity property if for every subset X ⊆ V (G) with |X| even, G has a spanning subgraph F with minimum degree at least one such that d F (v) ≡ 1 (mod 2) for all v ∈ X , d F (y) ≡ 0 (mod 2) for all y ∈ V (G) - X . Bujtás et al. (Graphs Combin 36(2020):1391–1399, 2020) introduced the concept and conjectured that every 2-edge-connected graph with minimum degree at least three has the strong parity property. In this paper, we give a characterization for graphs to have the strong parity property and construct a counterexample to disprove the conjecture proposed by Bujtás, Jendrol' and Tuza. [ABSTRACT FROM AUTHOR]

Motivated by several conjectures due to Nikoghosyan, in a recent article due to Li et al., the aim was to characterize all possible graphs H such that every 1-tough H-free graph is hamiltonian. The almost complete answer was given there by the conclusion that every proper induced subgraph H of K 1 ∪ P 4 can act as a forbidden subgraph to ensure that every 1-tough H-free graph is hamiltonian, and that there is no other forbidden subgraph with this property, except possibly for the graph K 1 ∪ P 4 itself. The hamiltonicity of 1-tough K 1 ∪ P 4 -free graphs, as conjectured by Nikoghosyan, was left there as an open case. In this paper, we consider the stronger property of pancyclicity under the same condition. We find that the results are completely analogous to the hamiltonian case: every graph H such that any 1-tough H-free graph is hamiltonian also ensures that every 1-tough H-free graph is pancyclic, except for a few specific classes of graphs. Moreover, there is no other forbidden subgraph having this property. With respect to the open case for hamiltonicity of 1-tough K 1 ∪ P 4 -free graphs we give infinite families of graphs that are not pancyclic. [ABSTRACT FROM AUTHOR]

For a fixed positive integer n and an r-uniform hypergraph H, the Turán number ex(n, H) is the maximum number of edges in an H-free r-uniform hypergraph on n vertices, and the Lagrangian density of H is defined as π λ (H) = sup { r ! λ (G) : G is an H -free r -uniform hypergraph } , where λ (G) = max { ∑ e ∈ G ∏ i ∈ e x i : x i ≥ 0 and ∑ i ∈ V (G) x i = 1 } is the Lagrangian of G. For an r-uniform hypergraph H on t vertices, it is clear that π λ (H) ≥ r ! λ (K t - 1 r) . Let us say that an r-uniform hypergraph H on t vertices is λ -perfect if π λ (H) = r ! λ (K t - 1 r) . A result of Motzkin and Straus implies that all graphs are λ -perfect. It is interesting to explore what kind of hypergraphs are λ -perfect. A conjecture in [22] proposes that every sufficiently large r-uniform linear hypergraph is λ -perfect. In this paper, we investigate whether the conjecture holds for linear 3-uniform paths. Let P t = { e 1 , e 2 , ⋯ , e t } be the linear 3-uniform path of length t, that is, | e i | = 3 , | e i ∩ e i + 1 | = 1 and e i ∩ e j = ∅ if | i - j | ≥ 2 . We show that P 3 and P 4 are λ -perfect. Applying the results on Lagrangian densities, we determine the Turán numbers of their extensions. [ABSTRACT FROM AUTHOR]

The connected graph of degree sequence 3, 3, 3, 1, 1, 1 is called a net, and the vertices of degree 1 in a net are called its endvertices. Broersma conjectured in 1993 that a 2-connected graph G with no induced K 1 , 3 is hamiltonian if every endvertex of each induced net of G has degree at least (| V (G) | - 2) / 3 . In this paper we prove this conjecture in the affirmative. [ABSTRACT FROM AUTHOR]

A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. The independent domination number of G, denoted by i(G), is the minimum cardinality of an independent dominating set. In this paper, we study the following conjecture posed by Goddard and Henning (Discrete Math. 313:839–854, 2013): If G ≇ K 3 , 3 is a connected, cubic, bipartite graph on n vertices, then i (G) ≤ 4 11 n . Henning et al. (Discrete Appl. Math. 162:399–403, 2014) prove the conjecture when the girth is at least 6. In this paper we strengthen this result by proving the conjecture when the graph has no subgraph isomorphic to K 2 , 3 . [ABSTRACT FROM AUTHOR]

Let T be a tree with m edges. It was conjectured that every m-regular bipartite graph can be decomposed into edge-disjoint copies of T. In this paper, we prove that every 6-regular bipartite graph can be decomposed into edge-disjoint paths with 6 edges. As a consequence, every 6-regular bipartite graph on n vertices can be decomposed into n 2 paths, which is related to the well-known Gallai's Conjecture: every connected graph on n vertices can be decomposed into at most n + 1 2 paths. [ABSTRACT FROM AUTHOR]

A subfamily { F 1 , F 2 , ⋯ , F | P | } ⊆ F is a copy of the poset P if there exists a bijection i : P → { F 1 , F 2 , ⋯ , F | P | } , such that p ≤ P q implies i (p) ⊆ i (q) . A family F is P-free, if it does not contain a copy of P. In this paper we establish basic results on the maximum number of k-chains in a P-free family F ⊆ 2 [ n ] . We prove that if the height of P, h (P) > k , then this number is of the order Θ (∏ i = 1 k + 1 l i - 1 l i ) , where l 0 = n and l 1 ≥ l 2 ≥ ⋯ ≥ l k + 1 are such that n - l 1 , l 1 - l 2 , ⋯ , l k - l k + 1 , l k + 1 differ by at most one. On the other hand if h (P) ≤ k , then we show that this number is of smaller order of magnitude. Let ∨ r denote the poset on r + 1 elements a , b 1 , b 2 , ... , b r , where a < b i for all 1 ≤ i ≤ r and let ∧ r denote its dual. For any values of k and l, we construct a { ∧ k , ∨ l } -free family and we conjecture that it contains asymptotically the maximum number of pairs in containment. We prove that this conjecture holds under the additional assumption that a chain of length 4 is forbidden. Moreover, we prove the conjecture for some small values of k and l. We also derive the asymptotics of the maximum number of copies of certain tree posets T of height 2 in { ∧ k , ∨ l } -free families F ⊆ 2 [ n ] . [ABSTRACT FROM AUTHOR]

A family of finite sets is called union-closed if it contains the union of any two sets in it. The Union-Closed Sets Conjecture of Frankl from 1979 states that each union-closed family contains an element that belongs to at least half of the members of the family. In this paper, we study structural properties of union-closed families. It is known that under the inclusion relation, every union-closed family forms a lattice. We call two union-closed families isomorphic if their corresponding lattices are isomorphic. Let F be a union-closed family and ⋃ F ∈ F F be the universe of F . Among all union-closed families isomorphic to F , we develop an algorithm to find one with a maximum universe, and an algorithm to find one with a minimum universe. We also study properties of these two extremal union-closed families in connection with the Union-Closed Set Conjecture. More specifically, a lower bound of sizes of sets of a minimum counterexample to the dual version of the Union-Closed Sets Conjecture is obtained. [ABSTRACT FROM AUTHOR]

Let H = (V , E) be a hypergraph, where V is a set of vertices and E is a set of non-empty subsets of V called edges. If all edges of H have the same cardinality r, then H is a r-uniform hypergraph; if E consists of all r-subsets of V, then H is a complete r-uniform hypergraph, denoted by K n r , where n = | V | . A hypergraph H ′ = (V ′ , E ′) is called a subhypergraph of H = (V , E) if V ′ ⊆ V and E ′ ⊆ E . A r-uniform hypergraph H = (V , E) is vertex-k-maximal if every subhypergraph of H has vertex-connectivity at most k, but for any edge e ∈ E (K n r) \ E (H) , H + e contains at least one subhypergraph with vertex-connectivity at least k + 1 . In this paper, we first prove that for given integers n, k, r with k , r ≥ 2 and n ≥ k + 1 , every vertex-k-maximal r-uniform hypergraph H of order n satisfies | E (H) | ≥ (r n) - (r n - k) , and this lower bound is best possible. Next, we conjecture that for sufficiently large n, every vertex-k-maximal r-uniform hypergraph H on n vertices satisfies | E (H) | ≤ (r n) - (r n - k) + (n k - 2) (r k) , where k , r ≥ 2 are integers. And the conjecture is verified for the case r > k . [ABSTRACT FROM AUTHOR]

Let k be a positive integer and let D be a digraph. A path partition P of D is a set of vertex-disjoint paths which covers V(D). Its k-norm is defined as ∑ P ∈ P min { | V (P) | , k } . A path partition is k-optimal if its k-norm is minimum among all path partitions of D. A partialk-coloring is a collection of k disjoint stable sets. A partial k-coloring C is orthogonal to a path partition P if each path P ∈ P meets min { | V (P) | , k } distinct sets of C . Berge (Eur J Comb 3(2):97–101, 1982) conjectured that every k-optimal path partition of D has a partial k-coloring orthogonal to it. A (path) k-pack of D is a collection of at most k vertex-disjoint paths in D. Its weight is the number of vertices it covers. A k-pack is optimal if its weight is maximum among all k-packs of D. A coloring of D is a partition of V(D) into stable sets. A k-pack P is orthogonal to a coloring C if each set C ∈ C meets min { | C | , k } paths of P . Aharoni et al. (Pac J Math 2(118):249–259, 1985) conjectured that every optimal k-pack of D has a coloring orthogonal to it. A digraph D is semicomplete if every pair of distinct vertices of D are adjacent. A digraph D is locally in-semicomplete if, for every vertex v ∈ V (D) , the in-neighborhood of v induces a semicomplete digraph. Locally out-semicomplete digraphs are defined similarly. In this paper, we prove Berge's and Aharoni–Hartman–Hoffman's Conjectures for locally in/out-semicomplete digraphs. [ABSTRACT FROM AUTHOR]

A graph G=(V(G),E(G)) is supereulerian if it has a spanning Eulerian subgraph. Let ℓ(G) be the maximum number of edges of spanning Eulerian subgraphs of a graph G. Motivated by a conjecture due to Catlin on supereulerian graphs, it was shown that if G is an r-regular supereulerian graph, then ℓ(G)≥23|E(G)| when r≠5, and ℓ(G)>35|E(G)| when r=5. In this paper we improve the coefficient and prove that if G is a 5-regular supereulerian graph, then ℓ(G)≥1930|E(G)|+43. For this, we first show that each graph G with maximum degree at most 3 has a matching with at least 27|E(G)| edges and this bound is sharp. Moreover, we show that Catlin's conjecture holds for claw-free graphs having no vertex of degree 4. Indeed, Catlin's conjecture does not hold for claw-free graphs in general. [ABSTRACT FROM AUTHOR]

The vertex cover problem and the dominating set problem are two well-known problems in graph theory. Their goal is to find the minimum size of a vertex subset satisfying some properties. Both hold a connected version, which imposes that the vertex subset must induce a connected component. To study the interdependence between the connected version and the original version of a problem, the Price of Connectivity (PoC) was introduced by Cardinal and Levy (Theor Comput Sci 411(26-28):2581-2590, 2010) and Levy (Approximation algorithms for covering problems in dense graphs. Ph.D. thesis, Université libre de Bruxelles, Brussels, 2009) as the ratio between invariants from the connected version and the original version of the problem. Camby et al. (Discret Math Theor Comput Sci 16:207-224, 2014) for the vertex cover problem, Camby and Schaudt (Discret Appl Math 177:53-59, 2014) for the dominating set problem characterized some classes of PoC-Near-Perfect graphs, hereditary classes of graphs in which the Price of Connectivity is bounded by a fixed constant. Moreover, only for the vertex cover problem, Camby et al. (2014) introduced the notion of critical graphs, graphs that can appear in the list of forbidden induced subgraphs characterization. By definition, the Price of Connectivity of a critical graph is strictly greater than that of any proper induced subgraph. In this paper, we prove that for the vertex cover problem, every critical graph is either isomorphic to a cycle on 5 vertices or bipartite. To go further in the previous studies, we also present conjectures on PoC-Near-Perfect graphs and critical graphs with the help of the computer software GraphsInGraphs (Camby and Caporossi in Studying graphs and their induced subgraphs with the computer: GraphsInGraphs. Cahiers du GERAD G-2016-10, 2016). Moreover, for the dominating set problem, we investigate critical trees and we show that every minimum dominating set of a critical graph is independent. [ABSTRACT FROM AUTHOR]

A proper edge k-colouring of a graph $$G=(V,E)$$ is an assignment $$c:E\rightarrow \{1,2,\ldots ,k\}$$ of colours to the edges of the graph such that no two adjacent edges are associated with the same colour. A neighbour sum distinguishing edge k-colouring, or nsd k-colouring for short, is a proper edge k-colouring such that $$\sum _{e\ni u}c(e)\ne \sum _{e\ni v}c(e)$$ for every edge uv of G. We denote by $$\chi '_{\Sigma }(G)$$ the neighbour sum distinguishing index of G, which is the least integer k such that an nsd k-colouring of G exists. By definition at least maximum degree, $$\Delta (G)$$ colours are needed for this goal. In this paper we prove that $$\chi '_\Sigma (G) \le \Delta (G)+1$$ for any graph G without isolated edges, with $$\mathrm{mad}(G)<3$$ and $$\Delta (G) \ge 6$$ . [ABSTRACT FROM AUTHOR]

A graph G is said to be ISK4-free if it does not contain any subdivision of $$K_4$$ as an induced subgraph. In this paper, we propose new upper bounds for the chromatic number of ISK4-free graphs and $$\{$$ ISK4, triangle $$\}$$ -free graphs. [ABSTRACT FROM AUTHOR]

The semitotal domination number of a graph G without isolated vertices is the minimum cardinality of a set S of vertices of G such that every vertex in $$V(G){\setminus } S$$ is adjacent to at least one vertex in S, and every vertex in S is within distance 2 of another vertex of S. In Henning and Marcon (Ann Comb 20(4):1-15, 2016), it was shown that every connected claw-free cubic graph G of order n has semitotal domination number at most $$\frac{4n}{11}$$ when $$n\ge 10$$ , and it was conjectured that the bound can be improved from $$\frac{4n}{11}$$ to $$\frac{n}{3}$$ if $$G\notin \{K_4,N_2\}$$ . In this paper, we prove this conjecture. [ABSTRACT FROM AUTHOR]

A graph is called $$2K_2$$ -free if it does not contain two independent edges as an induced subgraph. Gao and Pasechnik conjectured that every $$\frac{3}{2}$$ -tough $$2K_2$$ -free graph with at least three vertices has a spanning trail with maximum degree at most 4. In this paper, we confirm this conjecture. We also provide examples for all $$t < \frac{5}{4}$$ of t-tough graphs that do not have a spanning trail with maximum degree at most 4. [ABSTRACT FROM AUTHOR]

An acyclic edge coloring of a graph G is a proper edge coloring such that every cycle is colored with at least three colors. The acyclic chromatic index $$\chi _{a}'(G)$$ of a graph G is the least number of colors in an acyclic edge coloring of G. It was conjectured that $$\chi '_{a}(G)\le {\varDelta }(G) + 2$$ for any simple graph G with maximum degree $${\varDelta }(G)$$ . A graph is 1-planar if it can be drawn on the plane such that every edge is crossed by at most one other edge. In this paper, we show that every triangle-free 1-planar graph G has an acyclic edge coloring with $${\varDelta }(G) + 16$$ colors. [ABSTRACT FROM AUTHOR]

Jaeger et al. conjectured that every 5-edge-connected graph is $$Z_3$$ -connected, which is equivalent to that every 5-edge-connected claw-free graph is $$Z_3$$ -connected by Lai et al. (Inf Process Lett 111:1085-1088, 2011), and Ma and Li (Discret Math 336:57-68, 2014). Let G be a claw-free graph on at least 3 vertices such that there are at least two common neighbors of every pair of 2-distant vertices. In this paper, we prove that G is not $$Z_3$$ -connected if and only if G is one of seven specified graphs, or three families of well characterized graphs. As a corollary, G does not admit a nowhere-zero 3-flow if and only if G is one of three specified graphs or a family of well characterized graphs. [ABSTRACT FROM AUTHOR]

Erdős, Faber and Lovász conjectured in 1972 that the vertices of a linear hypergraph with n edges, each of size n, can be strongly colored with n colors. It was shown by Romero and Sánchez-Arroyo that an equivalent conjecture is obtained when linear hypergraphs are replaced by n-clusters. In this paper we describe new families of EFL-compliant n-clusters; that is, those for which the conjecture holds. Moreover, we describe ways to extend some n-clusters to larger ones preserving EFL-compliance. Also, our approach allowed us to provide a new upper bound for the chromatic number of n-clusters. [ABSTRACT FROM AUTHOR]

Hajós conjectured that graphs containing no subdivision of $$K_5$$ are 4-colorable. It is shown in Yu and Zickfeld (J Comb Theory Ser B 96:482-492, ) that if there is a counterexample to this conjecture then any minimum such counterexample must be 4-connected. In this paper, we further show that if $$G$$ is a minimum counterexample to Hajós' conjecture and $$S$$ is a 4-cut in $$G$$ then $$G-S$$ has exactly two components. [ABSTRACT FROM AUTHOR]

Mariusz Meszka has conjectured that given a prime $$p=2n+1$$ and a list $$L$$ containing $$n$$ positive integers not exceeding $$n$$ there exists a near $$1$$ -factor in $$K_p$$ whose list of edge-lengths is $$L$$ . In this paper we propose a generalization of this problem to the case in which $$p$$ is an odd integer not necessarily prime. In particular, we give a necessary condition for the existence of such a near $$1$$ -factor for any odd integer $$p$$ . We show that this condition is also sufficient for any list $$L$$ whose underlying set $$S$$ has size $$1$$ , $$2$$ , or $$n$$ . Then we prove that the conjecture is true if $$S=\{1,2,t\}$$ for any positive integer $$t$$ not coprime with the order $$p$$ of the complete graph. Also, we give partial results when $$t$$ and $$p$$ are coprime. Finally, we present a complete solution for $$t\le 11$$ . [ABSTRACT FROM AUTHOR]

We classify all possible zero-divisor graphs of a particular family of quotients of $$\mathbf{Z}_4[x,y,w,z]$$ . As the 90 quotients vary, we obtain a total of 7 graphs, corresponding to seven isomorphism classes, and one of these graphs provides a new example which contradicts Beck's conjecture on the chromatic number of a zero-divisor graph. The algebraic analysis is strongly supported by the combinatorial setting, as already shown in a previous paper, where the graph-theoretical tools were presented and successfully applied to $$\mathbf{Z}_4[x,y,z]$$ -therefore, the just smaller case-in order to get a deeper knowledge of the classical counterexample to Beck's conjecture. [ABSTRACT FROM AUTHOR]

It has long been conjectured that the total chromatic number $$ \chi ^{\prime \prime }(K)$$ of the complete $$p$$ -partite graph $$K = K(r_1, \dots , r_p)$$ is $$\Delta (K) + 1$$ if and only if both $$K \ne K_{r,r}$$ and $$|V(K)| \equiv $$ 0 (mod 2) implies that $$\Sigma _{v \in V(K)}(\Delta (K) - d_K(v))$$ is at least the number of parts of odd size. It is known that $$\chi ^{\prime \prime }(K) \le \Delta (K) + 2$$ . In this paper, a new approach is introduced to attack the conjecture that makes use of amalgamations of graphs. The power of this approach is demonstrated by settling the conjecture for all complete 5-partite graphs. [ABSTRACT FROM AUTHOR]

The domination polynomial of a graph is the polynomial whose coefficients count the number of dominating sets of each cardinality. A recent question asks which graphs are uniquely determined (up to isomorphism) by their domination polynomial. In this paper, we completely describe the complete $$r$$ -partite graphs which are; in the bipartite case, this settles in the affirmative a conjecture of Aalipour et al. (Ars Comb, ). [ABSTRACT FROM AUTHOR]

Let G be a graph. The irregularity index of G, denoted by t( G), is the number of distinct values in the degree sequence of G. For any graph G, t( G) ≤ Δ( G), where Δ( G) is the maximum degree. If t( G) = Δ( G), then G is called maximally irregular. In this paper, we give a tight upper bound on the size of maximally irregular graphs, and prove the conjecture proposed in [] on the size of maximally irregular triangle-free graphs. Extremal graphs are also characterized. [ABSTRACT FROM AUTHOR]

The Cycle Double Cover Conjecture claims that every bridgeless graph has a cycle double cover and the Strong Cycle Double Conjecture states that every such graph has a cycle double cover containing any specified circuit. In this paper, we get a necessary and sufficient condition for bridgeless graphs to have a strong 5-cycle double cover. Similar condition for the existence of 5-cycle double covers is also obtained. These conditions strengthen/improve some known results. [ABSTRACT FROM AUTHOR]

A digraph D with p vertices and q arcs is labeled by assigning a distinct integer value g( v) from {0,1, ... , q} to each vertex v. The vertex values, in turn, induce a value g( u, v) on each arc ( u, v) where g( u, v) = ( g( v)− g( u))( mod q + 1). If the arc values are all distinct then the labeling is called a graceful labeling of a digraph. Bloom and Hsu (SIAM J Alg Discr Methods 6:519-536, ) conjectured that, all unicyclic wheels are graceful. Also, Zhao et al. (J Prime Res Math 4:118-126, ) conjectured that, for any positive even n and any integer m ≥ 14, the digraph $${n-\overrightarrow{C_m}}$$ is graceful. In this paper, we prove both the conjectures. [ABSTRACT FROM AUTHOR]

A graphic sequence π = ( d, d, . . . , d) is said to be potentially K-graphic if there is a realization of π containing K as a subgraph, where K is the 1 × 1 × s complete 3-partite graph. In this paper, a simple characterization of potentially K-graphic sequences for s ≥ 2 and n ≥ 3 s + 1 is obtained. This characterization implies Lai's conjecture on σ( K, n), which was confirmed by J.H. Yin, J.S. Li and W.Y. Li, and the values of σ( K, n) for s ≥ 4 and n ≥ 3 s + 1, where K is the 2 × s complete bipartite graph. [ABSTRACT FROM AUTHOR]

The R-set relative to a pair of distinct vertices of a connected graph G is the set of vertices whose distances to these vertices are distinct. This paper deduces some properties of R-sets of connected graphs. It is shown that for a connected graph G of order n and diameter 2 the number of R-sets equal to V( G) is bounded above by $${\lfloor n^{2}/4\rfloor}$$ . It is conjectured that this bound holds for every connected graph of order n. A lower bound for the metric dimension dim( G) of G is proposed in terms of a family of R-sets of G having the property that every subfamily containing at least r ≥ 2 members has an empty intersection. Three sufficient conditions, which guarantee that a family $${\mathcal{F}=(G_{n})_{n\geq 1}}$$ of graphs with unbounded order has unbounded metric dimension, are also proposed. [ABSTRACT FROM AUTHOR]

In 1988, Seiya Negami published a conjecture stating that a graph G has a finite planar cover (i.e. a homomorphism from some planar graph onto G which maps the vertex neighbourhoods bijectively) if and only if G embeds in the projective plane. Though the “if” direction is easy, and over ten related research papers have been published during the past 20 years of investigation, this beautiful conjecture is still open in 2008. We give a short accessible survey on Negami’s conjecture and all the (so far) published partial results, and outline some further ideas to stimulate future research towards solving the conjecture. [ABSTRACT FROM AUTHOR]

Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero Z 3-flow and Jaeger et al. [Group connectivity of graphs–a nonhomogeneous analogue of nowhere-zero flow properties, J. Combin. Theory Ser. B 56 (1992) 165-182] further conjectured that every 5-edge-connected graph is Z 3-connected. These two conjectures are in general open and few results are known so far. A weaker version of Tutte’s conjecture states that every 4-edge-connected graph with each edge contained in a circuit of length at most 3 admits a nowhere-zero Z 3-flow. Devos proposed a stronger version problem by asking if every such graph is Z 3-connected. In this paper, we first answer this later question in negative and get an infinite family of such graphs which are not Z 3-connected. Moreover, motivated by these graphs, we prove that every 6-edge-connected graph whose edge set is an edge disjoint union of circuits of length at most 3 is Z 3-connected. It is a partial result to Jaeger’s Z 3-connectivity conjecture. [ABSTRACT FROM AUTHOR]

Oxley has conjectured that for k≥4, if a matroid M has a k-element set that is the intersection of a circuit and a cocircuit, then M has a ( k−2)-element set that is the intersection of a circuit and a cocircuit. In this paper we prove a stronger version of this conjecture for regular matroids. We also show that the stronger result does not hold for binary matroids. [ABSTRACT FROM AUTHOR]