Search

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]

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 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]

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]