Claw‐free graphs and 2‐factors that separate independent vertices

In this article, we prove that a line graph with minimum degree δ≥7 has a spanning subgraph in which every component is a clique of order at least three. This implies that if G is a line graph with δ≥7, then for any independent set S there is a 2‐factor of G such that each cycle contains at most one vertex of S. This supports the conjecture that δ≥5 is sufficient to imply the existence of such a 2‐factor in the larger class of claw‐free graphs. It is also shown that if G is a claw‐free graph of order n and independence number α with δ≥2n/α?2 and n≥3α³/2, then for any maximum independent set S, G has a 2‐factor with α cycles such that each cycle contains one vertex of S. This is in support of a conjecture that δ≥n/α≥5 is sufficient to imply the existence of a 2‐factor with α cycles, each containing one vertex of a maximum independent set. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 251–263, 2012     

Proof of the Loebl–Komlós–Sós conjecture for large, dense graphs

The Loebl–Komlós–Sós conjecture states that for any integers k and n, if a graph G on n vertices has at least n/2 vertices of degree at least k, then G contains as subgraphs all trees on k+1 vertices. We prove this conjecture in the case when k is linear in n, and n is sufficiently large.     

The longest cycle of a graph with a large minimal degree

We show that every graph G on n vertices with minimal degree at least n/k contains a cycle of length at least [n/(k ? 1)]. This verifies a conjecture of Katchalski. When k = 2 our result reduces to the classical theorem of Dirac that asserts that if all degrees are at least 1/2n then G is Hamiltonian.     

Proof of a tiling conjecture of Komlós

A conjecture of Komlós states that for every graph H, there is a constant K such that if G is any n‐vertex graph of minimum degree at least (1 ? (1/χ_cr(H)))n, where χ_cr(H) denotes the critical chromatic number of H, then G contains an H‐matching that covers all but at most K vertices of G. In this paper we prove that the conjecture holds for all sufficiently large values of n. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 180–205, 2003     

On Hua-Tuan’s conjecture

Let G be a finite group and |G| = pn, p be a prime. For 0 m n, sm(G) denotes the number of subgroups of of order pm of G. Loo-Keng Hua and Hsio-Fu Tuan have ever conjectured: for an arbitrary finite p-group G, if p > 2, then sm(G) ≡ 1, 1 + p, 1 + p + p2 or 1 + p + 2p2 (mod p3). In this paper, we investigate the conjecture, and give some p-groups in which the conjecture holds and some examples in which the conjecture does not hold.     

A graph-theoretic version of the union-closed sets conjecture

An induced subgraph S of a graph G is called a derived subgraph of G if S contains no isolated vertices. An edge e of G is said to be residual if e occurs in more than half of the derived subgraphs of G. We introduce the conjecture: Every non-empty graph contains a non-residual edge. This conjecture is implied by, but weaker than, the union-closed sets conjecture. We prove that a graph G of order n satisfies this conjecture whenever G satisfies any one of the conditions: δ(G) ≤ 2, log₂ n ≤ δ(G), n ≤ 10, or the girth of G is at least 6. Finally, we show that the union-closed sets conjecture, in its full generality, is equivalent to a similar conjecture about hypergraphs. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 155–163, 1997     

A proof of a conjecture on diameter 2-critical graphs whose complements are claw-free

A graph G is diameter 2-critical if its diameter is 2, and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter 2-critical graph of order n is at most n²/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. We use an important association with total domination to prove the conjecture for the graphs whose complements are claw-free.     

UPPER BOUNDS ON THE LOWER OPEN PACKING NUMBER OF A TREE

Abstract

Let G be a graph and let v be a vertex of G. The open neigbourhood N(v) of v is the set of all vertices adjacent with v in G. An open packing of G is a set of vertices whose open neighbourhoods are pairwise disjoint. The lower open packing number of G, denoted ρ^° _L(G), is the minimum cardinality of a maximal open packing of G while the (upper) open packing number of G, denoted ρ^°(G), is the maximum cardinality among all open packings of G. It is known (see [7]) that if G is a connected graph of order n ≥3, then ρ^°(G) ≤ 2n/3 and this bound is sharp (even for trees). As a consequence of this result, we know that ρ^° _L(G) ≤ 2n/3. In this paper, we improve this bound when G is a tree. We show that if G is a tree of order n with radius 3, then ρ^° _L(G) ≤ n/2 + 2 √n-1, and this bound is sharp, while if G is a tree of order n with radius at least 4, then ρ^° _L(G) is bounded above by 2n/3—O√n).     

On a conjecture of Murty and Simon on diameter 2-critical graphs

A graph G is diameter 2-critical if its diameter is two, and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter 2-critical graph of order n is at most n²/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. We use an association with total domination to prove the conjecture for the graphs whose complements have diameter three.     

List multicoloring problems involving the k‐fold Hall numbers

We show that the four‐cycle has a k‐fold list coloring if the lists of colors available at the vertices satisfy the necessary Hall's condition, and if each list has length at least ?5k/3?; furthermore, the same is not true with shorter list lengths. In terms of h^(k)(G), the k ‐fold Hall number of a graph G, this result is stated as h^(k)(C₄)=2k??k/3?. For longer cycles it is known that h^(k)(C_n)=2k, for n odd, and 2k??k/(n?1)?≤h^(k)(C_n)≤2k, for n even. Here we show the lower bound for n even, and conjecture that this is the right value (just as for C₄). We prove that if G is the diamond (a four‐cycle with a diagonal), then h^(k)(G)=2k. Combining these results with those published earlier we obtain a characterization of graphs G with h^(k)(G)=k. As a tool in the proofs we obtain and apply an elementary generalization of the classical Hall–Rado–Halmos–Vaughan theorem on pairwise disjoint subset representatives with prescribed cardinalities. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 16–34, 2010.     

ON A CONJECTURE ON nTH ORDER DEGREE REGULAR GRAPHS

Abstract

For n a positive integer and v a vertex of a graph G, the nth order degree of v in G, denoted by deg_nv, is the number of vertices at distance n from v. The graph G is said to be nth order regular of degree k if, for every vertex v of G, deg_nv = k. The following conjecture due to Alavi, Lick, and Zou is proved: For n ≥ 2, if G is a connected nth order regular graph of degree 1, then G is either a path of length 2n—1 or G has diameter n. Properties of nth order regular graphs of degree k, k ≥ 1, are investigated.     

Packing in regular graphs

A set S of vertices in a graph G is a packing if the vertices in S are pairwise at distance at least 3 apart in G. The packing number of G, denoted by ρ(G), is the maximum cardinality of a packing in G. Favaron [Discrete Math. 158 (1996), 287–293] showed that if G is a connected cubic graph of order n different from the Petersen graph, then ρ(G) ≥ n/8. In this paper, we generalize Favaron’s result. We show that for k ≥ 3, if G is a connected k-regular graph of order n that is not a diameter-2 Moore graph, then ρ(G) ≥ n/(k² ? 1).     

Zero-Sum Flows in Regular Graphs

For an undirected graph G, a zero-sum flow is an assignment of non-zero real numbers to the edges, such that the sum of the values of all edges incident with each vertex is zero. It has been conjectured that if a graph G has a zero-sum flow, then it has a zero-sum 6-flow. We prove this conjecture and Bouchet’s Conjecture for bidirected graphs are equivalent. Among other results it is shown that if G is an r-regular graph (r ≥ 3), then G has a zero-sum 7-flow. Furthermore, if r is divisible by 3, then G has a zero-sum 5-flow. We also show a graph of order n with a zero-sum flow has a zero-sum (n + 3)²-flow. Finally, the existence of k-flows for small graphs is investigated.     

Three-regular subgraphs of four-regular graphs

Berge conjectured that every finite simple 4-regular graph G contains a 3-regular subgraph. We prove that this conjecture is true if the cyclic edge connectivity λ^c(G) of G is at least 10. Also we prove that if G is a smallest counterexample, then λ^c(G) is either 6 or 8.     

A Degree Constraint for Uniquely Hamiltonian Graphs

A graph, G, is called uniquely Hamiltonian if it contains exactly one Hamilton cycle. We show that if G=(V, E) is uniquely Hamiltonian then Where #(G)=1 if G has even number of vertices and 2 if G has odd number of vertices. It follows that every n-vertex uniquely Hamiltonian graph contains a vertex whose degree is at most c log₂n+2 where c=(log₂3−1)⁻¹≈1.71 thereby improving a bound given by Bondy and Jackson [3].     

A maximum degree theorem for diameter-2-critical graphs

A graph is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Let G be a diameter-2-critical graph of order n. Murty and Simon conjectured that the number of edges in G is at most ?n ²/4? and that the extremal graphs are the complete bipartite graphs K _?n/2?,?n/2?. Fan [Discrete Math. 67 (1987), 235–240] proved the conjecture for n ≤ 24 and for n = 26, while Füredi [J. Graph Theory 16 (1992), 81–98] proved the conjecture for n > n ₀ where n ₀ is a tower of 2’s of height about 10¹⁴. The conjecture has yet to be proven for other values of n. Let Δ denote the maximum degree of G. We prove the following maximum degree theorems for diameter-2-critical graphs. If Δ ≥ 0.7 n, then the Murty-Simon Conjecture is true. If n ≥ 2000 and Δ ≥ 0.6789 n, then the Murty-Simon Conjecture is true.     

On relative length of longest paths and cycles

For a graph G, p(G) and c(G) denote the order of a longest path and a longest cycle of G, respectively. In this paper, we prove that if G is a 3 ‐connected graph of order n such that the minimum degree sum of four independent vertices is at least n+ 6, then p(G)?c(G)?2. By considering our result and the results in [J Graph Theory 20 (1995), 213–225; Amer Math Monthly 67 (1950), 55], we propose a conjecture which is a generalization of Bondy's conjecture. Furthermore, using our result, for a graph satisfying the above conditions, we obtain a new lower bound of the circumference and establish Thomassen's conjecture. © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 279–291, 2009     

Vertex‐disjoint cycles containing prescribed vertices

Enomoto 7 conjectured that if the minimum degree of a graph G of order n ≥ 4k ? 1 is at least the integer , then for any k vertices, G contains k vertex‐disjoint cycles each of which contains one of the k specified vertices. We confirm the conjecture for n ≥ ck² where c is a constant. Furthermore, we show that under the same condition the cycles can be chosen so that each has length at most six. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 276–296, 2003     

The multiplicity of 1-factors in the square of a graph

Several authors have shown that if G is a connected graph of even order then its square G² has a 1-factor. We show that the square of any connected graph of order 2n has at least n 1-factors and describe all the extremal graphs.     

A note on Vizing's independence number conjecture of edge chromatic critical graphs

In 1968, Vizing conjectured that, if G is a Δ-critical graph with n vertices, then α(G)?n/2, where α(G) is the independence number of G. In this note, we verify this conjecture for n?2Δ.