New Local Conditions for a Graph to be Hamiltonian

For a vertex w of a graph G the ball of radius 2 centered at w is the subgraph of G induced by the set M₂(w) of all vertices whose distance from w does not exceed 2. We prove the following theorem: Let G be a connected graph where every ball of radius 2 is 2-connected and d(u)+d(v)≥|M₂(w)|−1 for every induced path uwv. Then either G is hamiltonian or for some p≥2 where ∨ denotes join. As a corollary we obtain the following local analogue of a theorem of Nash-Williams: A connected r-regular graph G is hamiltonian if every ball of radius 2 is 2-connected and for each vertex w of G. Supported by the Swedish Research Council (VR)     

On circuits and pancyclic line graphs

Clark proved that L(G) is hamiltonian if G is a connected graph of order n ≥ 6 such that deg u + deg v ≥ n – 1 – p(n) for every edge uv of G, where p(n) = 0 if n is even and p(n) = 1 if n is odd. Here it is shown that the bound n – 1 – p(n) can be decreased to (2n + 1)/3 if every bridge of G is incident with a vertex of degree 1, which is a necessary condition for hamiltonicity of L(G). Moreover, the conclusion that L(G) is hamiltonian can be strengthened to the conclusion that L(G) is pancyclic. Lesniak-Foster and Williamson proved that G contains a spanning closed trail if |V(G)| = n ≥ 6, δ(G) ≥ 2 and deg u + deg v ≥ n – 1 for every pair of nonadjacent vertices u and v. The bound n – 1 can be decreased to (2n + 3)/3 if G is connected and bridgeless, which is necessary for G to have a spanning closed trail.     

Long paths through four vertices in a 2‐connected graph

Let G be a 2‐connected graph, let u and v be distinct vertices in V(G), and let X be a set of at most four vertices lying on a common (u, v)‐path in G. If deg(x) ≥ d for all x ∈ V(G) \ {u, v}, then there is a (u, v)‐path P in G with X ⊂ V(P) and |E(P)| ≥ d. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 55–65, 2000     

Long cycles passing through a specified edge in a 3-connected graph

We prove the following theorem: For a connected noncomplete graph G, let τ(G): = min{d_G(u) + d_G(v)|d_G(u, v) = 2}. Suppose G is a 3-connected noncomplete graph. Then through each edge of G there passes a cycle of length ≥ min{|V(G)|, τ (G) − 1}. © 1997 John Wiley & Sons, Inc.     

A characterization of panconnected graphs satisfying a local ore-type condition

It is well known that a graph G of order p ≥ 3 is Hamilton-connected if d(u) + d(v) ≥ p + 1 for each pair of nonadjacent vertices u and v. In this paper we consider connected graphs G of order at least 3 for which d(u) + d(v) ≥ |N(u) ∪ N(v) ∪ N(w)| + 1 for any path uwv with uv ∉ E(G), where N(x) denote the neighborhood of a vertex x. We prove that a graph G satisfying this condition has the following properties: (a) For each pair of nonadjacent vertices x, y of G and for each integer k, d(x, y) ≤ k ≤ |V(G)| − 1, there is an x − y path of length k. (b) For each edge xy of G and for each integer k (excepting maybe one k η {3,4}) there is a cycle of length k containing xy. Consequently G is panconnected (and also edge pancyclic) if and only if each edge of G belongs to a triangle and a quadrangle. Our results imply some results of Williamson, Faudree, and Schelp. © 1996 John Wiley & Sons, Inc.     

Relative length of long paths and cycles in graphs with large degree sums

For a graph G, p(G) denotes the order of a longest path in G and c(G) the order of a longest cycle. We show that if G is a connected graph n ≥ 3 vertices such that d(u) + d(v) + d(w) ≧ n for all triples u, v, w of independent vertices, then G satisfies c(G) ≥ p(G) – 1, or G is in one of six families of exceptional graphs. This generalizes results of Bondy and of Bauer, Morgana, Schmeichel, and Veldman. © 1995, John Wiley & Sons, Inc.     

Edge disjoint Hamilton cycles in graphs

Let G be a graph of order n and k ≥ 0 an integer. It is conjectured in [8] that if for any two vertices u and v of a 2(k + 1)‐connected graph G,d _G (u,v) = 2 implies that max{d(u;G), d(v;G)} ≥ (n/2) + 2k, then G has k + 1 edge disjoint Hamilton cycles. This conjecture is true for k = 0, 1 (see cf. [3] and [8]). It will be proved in this paper that the conjecture is true for every integer k ≥ 0. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 8–20, 2000     

On local connectivity of graphs with given clique number

For a vertex v of a graph G, we denote by d(v) the degree of v. The local connectivity κ(u, v) of two vertices u and v in a graph G is the maximum number of internally disjoint u –v paths in G, and the connectivity of G is defined as κ(G)=min{κ(u, v)|u, v∈V(G)}. Clearly, κ(u, v)?min{d(u), d(v)} for all pairs u and v of vertices in G. Let δ(G) be the minimum degree of G. We call a graph G maximally connected when κ(G)=δ(G) and maximally local connected when for all pairs u and v of distinct vertices in G. In 2006, Hellwig and Volkmann (J Graph Theory 52 (2006), 7–14) proved that a connected graph G with given clique number ω(G)?p of order n(G) is maximally connected when As an extension of this result, we will show in this work that these conditions even guarantee that G is maximally local connected. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 192–197, 2010     

Minimum implicit degree condition restricted to claws for hamiltonian cycles

Let id(v) denote the implicit degree of a vertex v in a graph G. We define G to be implicit 1-heavy (implicit 2-heavy) if at least one (two) of the end vertices of each induced claw has (have) implicit degree at least n/2. In this paper, we prove that: (a) Let G be a 2-connected graph of order n ≥ 3. If G is implicit 2-heavy and |N(u) ∩ N(v)| ≥ 2 for every pair of vertices u and v with d(u, v) = 2 and max{id(u), id(v)} < n/2, then G is hamiltonian. (b) Let G be a 3-connected graph of order n ≥ 3. If G is implicit 1-heavy and |N(u) ∩ N(v)| ≥ 2 for each pair of vertices u and v with d(u, v) = 2 and max{id(u), id(v)} < n/2, then G is hamiltonian.     

Subpancyclicity of line graphs and degree sums along paths

A graph is called subpancyclic if it contains a cycle of length ? for each ? between 3 and the circumference of the graph. We show that if G is a connected graph on n?146 vertices such that d(u)+d(v)+d(x)+d(y)>(n+10/2) for all four vertices u,v,x,y of any path P=uvxy in G, then the line graph L(G) is subpancyclic, unless G is isomorphic to an exceptional graph. Moreover, we show that this result is best possible, even under the assumption that L(G) is hamiltonian. This improves earlier sufficient conditions by a multiplicative factor rather than an additive constant.     

A Note on L（2, 1）-labelling of Trees

An L(2,1)-labelling of a graph G is a function from the vertex set V (G) to the set of all nonnegative integers such that |f(u) f(v)| ≥ 2 if d G (u,v)=1 and |f(u) f(v)| ≥ 1 if d G (u,v)=2.The L(2,1)-labelling problem is to find the smallest number,denoted by λ(G),such that there exists an L(2,1)-labelling function with no label greater than it.In this paper,we study this problem for trees.Our results improve the result of Wang [The L(2,1)-labelling of trees,Discrete Appl.Math.154 (2006) 598-603].     

Centers to centroids in graphs

For S ? V(G) the S-center and S-centroid of G are defined as the collection of vertices u ∈ V(G) that minimize e_s(u) = max {d(u, v): v ∈ S} and d_s(u) = ∑_u∈S d(u, v), respectively. This generalizes the standard definition of center and centroid from the special case of S = V(G). For 1 ? k ?|V(G)| and u ∈ V(G) let r_k(u) = max {∑_s∈S d(u, s): S ? V(G), |S| = k}. The k-centrum of G, denoted C(G; k), is defined to be the subset of vertices u in G for which r_k(u) is a minimum. This also generalizes the standard definitions of center and centroid since C(G; 1) is the center and C(G; |V(G)|) is the centroid. In this paper the structure of these sets for trees is examined. Generalizations of theorems of Jordan and Zelinka are included.     

On Properties of a Graph that Depend on its Distance Function

If G is a connected graph with distance function d, then by a step in G is meant an ordered triple (u, x, v) of vertices of G such that d(u, x) = 1 and d(u, v) = d(x, v) + 1. A characterization of the set of all steps in a connected graph was published by the present author in 1997. In Section 1 of this paper, a new and shorter proof of that characterization is presented. A stronger result for a certain type of connected graphs is proved in Section 2.     

Degree bounds for the circumference of 3‐connected graphs

Let C be a longest cycle in the 3‐connected graph G and let H be a component of G ? V(C) such that |V(H)| ≥ 3. We supply estimates of the form |C| ≥ 2d(u) + 2d(v) ? α(4 ≤ α ≤ 8), where u,v are suitably chosen non‐adjacent vertices in G. Also the exceptional classes for α = 6,7,8 are characterized. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Mutually Independent Hamiltonian Connectivity of (n, k)-Star Graphs

A graph G is hamiltonian connected if there exists a hamiltonian path joining any two distinct nodes of G. Two hamiltonian paths and of G from u to v are independent if u = u ₁ = v ₁, v = u _v(G) = v _v(G) , and u _i ≠ v _i for every 1 < i < v(G). A set of hamiltonian paths, {P ₁, P ₂, . . . , P _k }, of G from u to v are mutually independent if any two different hamiltonian paths are independent from u to v. A graph is k mutually independent hamiltonian connected if for any two distinct nodes u and v, there are k mutually independent hamiltonian paths from u to v. The mutually independent hamiltonian connectivity of a graph G, IHP(G), is the maximum integer k such that G is k mutually independent hamiltonian connected. Let n and k be any two distinct positive integers with n–k ≥ 2. We use S _n,k to denote the (n, k)-star graph. In this paper, we prove that IHP(S _n,k ) = n–2 except for S _4,2 such that IHP(S _4,2) = 1.      

Hamiltonian Connected Claw-Free Graphs

A well-known result by O. Ore is that every graph of order n with d(u)+d(v)n+1 for any pair of nonadjacent vertices u and v is hamiltonian connected (i.e., for every pair of vertices, there is a hamiltonian path joining them). In this paper, we show that every 3-connected claw-free graph G on at most 5–8 vertices is hamiltonian connected, where denotes the minimum degree in G. This result generalizes several previous results.Acknowledgments. The author would like to thank the referee for his important suggestions and careful corrections.Final version received: March 12, 2003Supported by the project of Nature Science Funds of China     

On the Existence of a Long Path Between Specified Vertices in a 2-Connected Graph

 Let G be a 2-connected graph with maximum degree Δ (G)≥d, and let x and y be distinct vertices of G. Let W be a subset of V(G)−{x, y} with cardinality at most d−1. Suppose that max{d _G(u), d _G(v)}≥d for every pair of vertices u and v in V(G)−({x, y}∪W) with d _G(u,v)=2. Then x and y are connected by a path of length at least d−|W|. Received: February 5, 1998 Revised: April 13, 1998     

Neighborhood unions and hamilton cycles

Let G be a graph on n vertices and N₂(G) denote the minimum size of N(u) ∪ N(v) taken over all pairs of independent vertices u, v of G. We show that if G is 3-connected and N₂(G) ? ½(n + 1), then G has a Hamilton cycle. We show further that if G is 2-connected and N₂(G) ? ½(n + 3), then either G has a Hamilton cycle or else G belongs to one of three families of exceptional graphs.     

A new sufficient condition for Hamiltonian graphs

The study of Hamiltonian graphs began with Dirac’s classic result in 1952. This was followed by that of Ore in 1960. In 1984 Fan generalized both these results with the following result: If G is a 2-connected graph of order n and max{d(u),d(v)}≥n/2 for each pair of vertices u and v with distance d(u,v)=2, then G is Hamiltonian. In 1991 Faudree–Gould–Jacobson–Lesnick proved that if G is a 2-connected graph and |N(u)∪N(v)|+δ(G)≥n for each pair of nonadjacent vertices u,v∈V(G), then G is Hamiltonian. This paper generalizes the above results when G is 3-connected. We show that if G is a 3-connected graph of order n and max{|N(x)∪N(y)|+d(u),|N(w)∪N(z)|+d(v)}≥n for every choice of vertices x,y,u,w,z,v such that d(x,y)=d(y,u)=d(w,z)=d(z,v)=d(u,v)=2 and where x,y and u are three distinct vertices and w,z and v are also three distinct vertices (and possibly |{x,y}∩{w,z}| is 1 or 2), then G is Hamiltonian.     

The Number of Independent Sets in a Graph with Small Maximum Degree

Let ind(G) be the number of independent sets in a graph G. We show that if G has maximum degree at most 5 then