Covering a graph with cycles

Let k and n be two integers such that k ≥ 0 and n ≥ 3(k + 1). Let G be a graph of order n with minimum degree at least ?(n + k)/2?. Then G contains k + 1 independent cycles covering all the vertices of G such that k of them are triangles. © 1995, John Wiley & Sons, Inc.     

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.     

Pancyclic and panconnected line graphs

Let G be a graph of order n ? 3. We prove that if G is k-connected (k ? 2) and the degree sum of k + 1 mutually independent vertices of G is greater than 1/3(k + 1)(n + 1), then the line graph L(G) of G is pancyclic. We also prove that if G is such that the degree sum of every 2 adjacent vertices is at least n, then L(G) is panconnected with some exceptions.     

On a k-Tree Containing Specified Leaves in a Graph

A k-tree of a graph is a spanning tree with maximum degree at most k. We give sufficient conditions for a graph G to have a k-tree with specified leaves: Let k,s, and n be integers such that k≥2, 0≤s≤k, and n≥s+1. Suppose that (1) G is (s+1)-connected and the degree sum of any k independent vertices of G is at least |G|+(k−1)s−1, or (2) G is n-connected and the independence number of G is at most (n−s)(k−1)+1. Then for any s specified vertices of G, G has a k-tree containing them as leaves. We also discuss the sharpness of the results. This research was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Encouragement of Young Scientists, 15740077, 2005 This research was partially supported by the Japan Society for the Promotion of Science for Young Scientists.     

Large Vertex-Disjoint Cycles in a Bipartite Graph

Let s≥2 and k be two positive integers. Let G=(V ₁,V ₂;E) be a bipartite graph with |V ₁|=|V ₂|=n≥s k and the minimum degree at least (s−1)k+1. When s=2 and n >2k, it is proved in [5] that G contains k vertex-disjoint cycles. In this paper, we show that if s≥3, then G contains k vertex-disjoint cycles of length at least 2s. Received: March 2, 1998 Revised: October 26, 1998     

On Independent Cycles in a Bipartite Graph

 Let G=(V ₁,V ₂;E) be a bipartite graph with 2k≤m=|V ₁|≤|V ₂|=n, where k is a positive integer. We show that if the number of edges of G is at least (2k−1)(n−1)+m, then G contains k vertex-disjoint cycles, unless e(G)=(2k−1)(n−1)+m and G belongs to a known class of graphs. Received: December 9, 1998 Final version received: June 2, 1999     

Pentagons and cycle coverings

Let G be a graph of order n ≥ 5k + 2, where k is a positive integer. Suppose that the minimum degree of G is at least ?(n + k)/2?. We show that G contains k pentagons and a path such that they are vertex‐disjoint and cover all the vertices of G. Moreover, if n ≥ 5k + 7, then G contains k + 1 vertex‐disjoint cycles covering all the vertices of G such that k of them are pentagons. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 194–208, 2007     

Covering the vertices of a graph by cycles of prescribed length

The main theorem of that paper is the following: let G be a graph of order n, of size at least (n² - 3n + 6)/2. For any integers k, n₁, n₂,…,n_k such that n = n₁ + n₂ +. + n_k and n_i ? 3, there exists a covering of the vertices of G by disjoint cycles (C_i) =l…k with |C_i| = ni, except when n = 6, n₁ = 3, n₂ = 3, and G is isomorphic to G₁, the complement of G₁ consisting of a C₃ and a stable set of three vertices, or when n = 9, n₁ = n₂ = n₃ = 3, and G is isomorphic to G₂, the complement of G₂ consisting of a complete graph on four vertices and a stable set of five vertices. We prove an analogous theorem for bipartite graphs: let G be a bipartite balanced graph of order 2n, of size at least n² - n + 2. For any integers s, n₁, n₂,…,n_s with n_i ? 2 and n = n₁ + n₂ + ? + n_s, there exists a covering of the vertices of G by s disjoint cycles C_i, with |C_i| = 2n_i.     

Edge disjoint cycles in graphs

Ore proved in 1960 that if G is a graph of order n and the sum of the degrees of any pair of nonadjacent vertices is at least n, then G has a hamiltonian cycle. In 1986, Li Hao and Zhu Yongjin showed that if n ? 20 and the minimum degree δ is at least 5, then the graph G above contains at least two edge disjoint hamiltonian cycles. The result of this paper is that if n ? 2δ², then for any 3 ? l₁ ? l₂ ? ? ? l_k ? n, 1 = k = [(δ - 1)/2], such graph has K edge disjoint cycles with lengths l₁, l₂…l_k, respectively. In particular, when l₁ = l₂ = ? = l_k = n and k = [(δ - 1)/2], the graph contains [(δ - 1)/2] edge disjoint hamiltonian cycles.     

Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at least k

Let G_n,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property A_k, if G contains ⌊(k − 1)/2⌋ edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size ⌊n/2⌋. We prove that, for k ≥ 3, there is a constant C_k such that if 2m ≥ C_kn then A_k occurs in G_n,m,k with probability tending to 1 as n → ∞. © 2000 John Wiley & Sons, Inc. J. Graph Theory 34: 42–59, 2000     

Maximal Total Length Of k Disjoint Cycles In Bipartite Graphs

Let k, s and n be three integers with sk2, n2k+1. Let G=(V ₁,V ₂;E) be a bipartite graph with |V ₁|=|V ₂|=n. If the minimum degree of G is at least s+1, then G contains k vertex-disjoint cycles covering at least min(2n,4s) vertices of G.     

Spanning Trees with Few Leaves

In this paper, we prove that an m-connected graph G on n vertices has a spanning tree with at most k leaves (for k ≥ 2 and m ≥ 1) if every independent set of G with cardinality m + k contains at least one pair of vertices with degree sum at least n − k + 1. This is a common generalization of results due to Broersma and Tuinstra and to Win.     

Chromatic factorizations of a graph

Let n₁ ? n₂ ? …? ? n_k ? 2 be integers. We say that G has an (n₁, n₂, …?, n_k-chromatic factorization if G) can be edge-factored as G₁ ⊕ G₂ ⊕ …? ⊕ G_k with χ(G_i) = nA_i, for i = 1,2,…, k. The following results are proved:

• i If (n₁ ? 1)n₂ …? n_k < χ(G) ? n₁n₂ …? n_k, then G has an (n₁, n₂, …?, n_k)-chromatic factorization.
• ii If n₁ + n₂ + …? + n_k ? (k - 1) ? n ? n₁n₂ …? n_k, then K_n has an (n₁, n₂, …?, n_k)-chromatic factorization.

     

On the size of graphs labeled with a condition at distance two

A labeling of graph G with a condition at distance two is an integer labeling of V(G) such that adjacent vertices have labels that differ by at least two, and vertices distance two apart have labels that differ by at least one. The lambda-number of G, λ(G), is the minimum span over all labelings of G with a condition at distance two. Let G(n, k) denote the set of all graphs with order n and lambda-number k. In this paper, we examine the sizes of graphs in G(n, k). We modify Chvàtal's result on non-hamiltonian graphs to obtain a formula for the minimum size of a graph in G(n, k), and we use an algorithmic approach to obtain a formula for the maximum size. Finally, we show that for any integer j between the maximum and minimum sizes there exists a graph with size j in G(n, k). © 1996 John Wiley & Sons, Inc.     

The color space of a graph

If k is a prime power, and G is a graph with n vertices, then a k‐coloring of G may be considered as a vector in $\mathbb{GF}$(k)ⁿ. We prove that the subspace of $\mathbb{GF}$(3)ⁿ spanned by all 3‐colorings of a planar triangle‐free graph with n vertices has dimension n. In particular, any such graph has at least n − 1 nonequivalent 3‐colorings, and the addition of any edge or any vertex of degree 3 results in a 3‐colorable graph. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 234–245, 2000     

Vertices of Degree 5 in a Contraction Critically 5-connected Graph

An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. A k-connected graph with no k-contractible edge is said to be contraction critically k-connected. We prove that a contraction critically 5-connected graph on n vertices has at least n/5 vertices of degree 5. We also show that, for a graph G and an integer k greater than 4, there exists a contraction critically k-connected graph which has G as its induced subgraph.     

A vertex cover with chorded 4-cycles

Let k be an integer with k ≥ 2 and G a graph with order n > 4k. We prove that if the minimum degree sum of any two nonadjacent vertices is at least n + k, then G contains a vertex cover with exactly k components such that k−1 of them are chorded 4-cycles. The degree condition is sharp in general.     

Periods in missing lengths of rainbow cycles

A cycle in an edge‐colored graph is said to be rainbow if no two of its edges have the same color. For a complete, infinite, edge‐colored graph G, define Then ??(G) is a monoid with respect to the operation n°m=n+ m?2, and thus there is a least positive integer π(G), the period of ??(G), such that ??(G) contains the arithmetic progression {N+ kπ(G)|k?0} for some sufficiently large N. Given that n∈??(G), what can be said about π(G)? Alexeev showed that π(G)=1 when n?3 is odd, and conjectured that π(G) always divides 4. We prove Alexeev's conjecture: Let p(n)=1 when n is odd, p(n)=2 when n is divisible by four, and p(n)=4 otherwise. If 2<n∈??(G) then π(G) is a divisor of p(n). Moreover, ??(G) contains the arithmetic progression {N+ kp(n)|k?0} for some N=O(n²). The key observations are: If 2<n=2k∈??(G) then 3n?8∈??(G). If 16≠n=4k∈??(G) then 3n?10∈??(G). The main result cannot be improved since for every k>0 there are G, H such that 4k∈??(G), π(G)=2, and 4k+ 2∈??(H), π(H)=4. © 2009 Wiley Periodicals, Inc. J Graph Theory     

Domination number in graphs with minimum degree two

A set D of vertices of a graph G = （V, E） is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a dominating set of cardinality at most 3n/8. In this paper we generalize Reed＇s result. We show that every graph G of order n with minimum degree at least 2 has a dominating set of cardinality at most （3n ＋IV21）/8, where V2 denotes the set of vertices of degree 2 in G. As an application of the above result, we show that for k ≥ 1, the k-restricted domination number rk （G, γ） ≤ （3n＋5k）/8 for all graphs of order n with minimum degree at least 3.     

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