Search

Let G be an n-vertex simple graph, and let Δ(G) and χ′(G) denote the maximum degree and chromatic index of G, respectively. Vizing proved that χ′(G)=Δ(G) or Δ(G)+1. Define G to be Δ-critical if χ′(G)=Δ+1 and χ′(H)

A broom is a tree obtained by subdividing one edge of the star an arbitrary number of times. In (E. Flandrin, T. Kaiser, R. Kužel, H. Li and Z. Ryjacek, Neighborhood Unions and Extremal Spanning Trees, Discrete Math 308 (2008), 2343–2350) Flandrin et al. posed the problem of determining degree conditions that ensure a connected graph G contains a spanning tree that is a broom. In this article, we give one solution to this problem by demonstrating that if G is a connected graph of order with , then G contains a spanning broom. This result is best possible.

A set F of edges in a digraph D is called a directed cut if there exists a nontrivial partition X,Y of VD such that F consists of all directed edges from X to Y. Let i¾?D denote the maximum size of a directed cut of D, and let D1,1 be the set of all digraphs D such that d+v=1 or d-v=1 for any vertex v in D. We show that i¾?Di¾?38|ED|-1 for any connected digraph D∈D1,1, which provides a positive answer to a problem of Lehel, Maffray, and Preissmann. Additionally, we consider triangle-free digraphs in D1,1 and answer another question of theirs.

Let G be a k-connected graph of order n, α: = α(G) the independence number of G, and c(G) the circumference of G. Chvatal and Erdős proved that if α⩽kthen G is hamiltonian. For α⩾k⩾2, Fouquet and Jolivet in 1978 made the conjecture that c(G)⩾k(n+ α − k)/α. Fournier proved that the conjecture is true for α⩽k+ 2 or k = 2 in two different papers. Manoussakis recently proved that the conjecture is true for k = 3. We prove that if G is a k-connected graph, k≥4, of order n and independence number α≥k, then c(G)⩾(k(n+ α − k)/α) − ((k − 3)(k − 4)/2). Consequently, the conjecture of Fouquet and Jolivet holds for k = 4. In addition, we confirm the conjecture for α = k+ 3. Inspired by a result of Kouider, we conjecture that, for every graph G and any two distinct vertices u and v, there is a u − vpath P such that α(G − V(P))⩽α(G) − 1 unless V(G) have a nontrivial partition V1∪V2 satisfying α(G) = α(G[V1]) + α(G[V2]). In this paper, we obtain a partial result regarding this conjecture. Let G be a k-connected graph and k⩾2. While studying the intersection of longest cycles, J. Chen et al. conjectured that, for any two cycles C1 and C2 of G, there are two cycles D1 and D1 such that V(D1)∪V(D2)⊇V(C1)∪V(C2) and |V(D1)∩V(D2)|⩾k. We show that the combination of the above two conjectures implies the conjecture of Fouquet and Jolivet. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:55-76, 2011 © 2011 Wiley Periodicals, Inc.

For any positive integer k, we investigate degree conditions implying that a graph G of order n contains a 2-factor with exactly k components (vertex disjoint cycles). In particular, we prove that for k ≤ (n/4), Ore's classical condition for a graph to be hamiltonian (k = 1) implies that the graph contains a 2-factor with exactly k components. We also obtain a sufficient degree condition for a graph to have k vertex disjoint cycles, at least s of which are 3-cycles and the remaining are 4-cycles for any s ≤ k. © 1997 John Wiley & Sons, Inc.

An independent set S of a graph G is said to be essential if S has a pair of vertices distance two apart in G. We prove that if every essential independent set S of order k ≥ 2 in a k-connected graph of order p satisfies max {deg v:v ϵ S} ≥ ½ p, then g is hamiltonian. This generalizes the result of Fan (J. Combinatorial Theory B37 (1984), 221–227). If we consider the essential independent sets of order k + 1 instead of k in the assumption of the above statement, we can no longer assure the existence a hamiltonian cycle. However, we can still give a lower bound to the length of a longest cycle. © 1996 John Wiley & Sons, Inc.

In 1963, Vizing [Vichysl.Sistemy9 (1963), 30–43] conjectured that γ(G × H) ≥ γ(G)γ(H), where G × H denotes the cartesian product of graphs, and γ(G) is the domination number. In this paper we define the extraction number x(G) and we prove that P2(G) ≤ x(G), and γ(G × H) ≥ x(G)γ(H), where P2(G) is the 2-packing number of G. Though the equality x(G) = γ(G) is proven to hold in several classes of graphs, we construct an infinite family of graphs which do not satisfy this condition. Also, we show the following lower bound: γ(G × H) ≥ γ(G)P2(H) + P2(G)(γ(H) − P2(H)). © 1996 John Wiley & Sons, Inc.

In this paper, we investigate the Hamiltonicity of K1,r-free graphs with some degree conditions. In particular, let G be a k-connected grph of order n≧3 which is K1,4-free. If for every independent set {v0, v1, …, vk} then G is hamiltonian. We use an upper bound for the independence number of K1,r-free graphs to extent the above result to K1,r-free graphs. Hamiltonian connected and, more generally, q-edge hamiltonian properties are studied here as well. © 1995 John Wiley & Sons, Inc.

The irredundant Ramsey number s(m, n) is the smallest p such that for every graph G with p vertices, either G contains an n-element irredundant set or its complement G contains an m-element irredundant set. Cockayne, Hattingh, and Mynhardt have given a computer-assisted proof that s(3, 7) = 18. The purpose of this paper is to give a self-contained proof of this result. © 1995 John Wiley & Sons, Inc.

For several years, the study of neighborhood unions of graphs has given rise to important structural consequences of graphs. In particular, neighborhood conditions that give rise to hamiltonian cycles have been considered in depth. In this paper we generalize these approaches to give a bound on the smallest number of cycles in G containing all the vertices of G. We show that if for all x, y ≅ V(G), |N(x) ∩ N(y)| ≧ 2n/5 + 1, then V(G) is coverable by at most two cycles. Several related results and extensions to t cycles are also given.

In this paper, k + 1 real numbers c1, c2, , ck+1 are found such that the following condition is sufficient for a k-connected graph of order n to be hamiltonian: for each independent vertex set of k + 1 vertices in G. where Si = {v ≅ V:|N(v) ∩ S| = i} for 0 ≦ i ≦ k + 1. Such a set of k + 1 numbers is called an Hk-sequence. A sufficient condition for the existence of Hk-sequences is obtained that generalizes many known results involving sum of degrees, neighborhood unions, and/or neighborhood intersections.

The irredundant Ramsey number s(m, n) is the smallest N such that in every red-blue coloring of the edges of KN, either the blue graph contains an m-element irredundant set or the red graph contains an n-element irredundant set. The definition of the mixed Ramsey number t(m, n) differs from s(m, n) in that the n-element irredundant set is replaced by an n-element independent set. We prove asymptotic lower bounds for s(n, n) and t(m, n) (with m fixed and n large) and a general upper bound for t(3, n). © 1993 John Wiley & Sons, Inc.

Let G be a graph of order n. We show that if G is a 2-connected graph and max{d(u), d(v)} + |N(u) U N(v)| ≥ n for each pair of vertices u, v at distance two, then either G is hamiltonian or G 3Kn/3 U T1 U T2, where n O (mod 3), and T1 and T2 are the edge sets of two vertex disjoint triangles containing exactly one vertex from each Kn/3. This result generalizes both Fan's and Lindquester's results as well as several others.

Let G be a 2-connected graph of order n. We show that if for each pair of nonadjacent vertices x,y ∈ V(G), then G is Hamiltonian.