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.     

Survey of Double Vertex Graphs

 Let G be a (V,E) graph of order p≥2. The double vertex graph U ₂ (G) is the graph whose vertex set consists of all 2-subsets of V such that two distinct vertices {x,y} and {u,v} are adjacent if and only if |{x,y}∩{u,v}|=1 and if x=u, then y and v are adjacent in G. For this class of graphs we discuss the regularity, eulerian, hamiltonian, and bipartite properties of these graphs. A generalization of this concept is n-tuple vertex graphs, defined in a manner similar to double vertex graphs. We also review several recent results for n-tuple vertex graphs. Received: October, 2001 Final version received: September 20, 2002 Dedicated to Frank Harary on the occasion of his Eightieth Birthday and the Manila International Conference held in his honor     

Pan-connectedness of graphs with large neighborhood unions

Let G be a simple graph with n vertices. For any v ? V(G){v \in V(G)} , let N(v)={u ? V(G): uv ? E(G)}{N(v)=\{u \in V(G): uv \in E(G)\}} , NC(G) = min{|N(u) èN(v)|: u, v ? V(G){NC(G)= \min \{|N(u) \cup N(v)|: u, v \in V(G)} and uv \not ? E(G)}{uv \not \in E(G)\}} , and NC₂(G) = min{|N(u) èN(v)|: u, v ? V(G){NC_2(G)= \min\{|N(u) \cup N(v)|: u, v \in V(G)} and u and v has distance 2 in E(G)}. Let l ≥ 1 be an integer. A graph G on n ≥ l vertices is [l, n]-pan-connected if for any u, v ? V(G){u, v \in V(G)} , and any integer m with l ≤ m ≤ n, G has a (u, v)-path of length m. In 1998, Wei and Zhu (Graphs Combinatorics 14:263–274, 1998) proved that for a three-connected graph on n ≥ 7 vertices, if NC(G) ≥ n − δ(G) + 1, then G is [6, n]-pan-connected. They conjectured that such graphs should be [5, n]-pan-connected. In this paper, we prove that for a three-connected graph on n ≥ 7 vertices, if NC ₂(G) ≥ n − δ(G) + 1, then G is [5, n]-pan-connected. Consequently, the conjecture of Wei and Zhu is proved as NC ₂(G) ≥ NC(G). Furthermore, we show that the lower bound is best possible and characterize all 2-connected graphs with NC ₂(G) ≥ n − δ(G) + 1 which are not [4, n]-pan-connected.     

A sufficient degree condition for a graph to contain all trees of size <Emphasis Type="Italic">k</Emphasis>

The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d _G (x) + d _G (y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d _G (u) ≥ k.     

Computation of Topological Indices of Some Graphs

Let G=(V,E) be a simple connected graph with vertex set V and edge set E. The Wiener index of G is defined by W(G)=∑_{x,y}⊆V d(x,y), where d(x,y) is the length of the shortest path from x to y. The Szeged index of G is defined by Sz(G)=∑ _e=uv∈E n _u (e|G)n _v (e|G), where n _u (e|G) (resp. n _v (e|G)) is the number of vertices of G closer to u (resp. v) than v (resp. u). The Padmakar–Ivan index of G is defined by PI(G)=∑ _e=uv∈E [n _eu (e|G)+n _ev (e|G)], where n _eu (e|G) (resp. n _ev (e|G)) is the number of edges of G closer to u (resp. v) than v (resp. u). In this paper we find the above indices for various graphs using the group of automorphisms of G. This is an efficient method of finding these indices especially when the automorphism group of G has a few orbits on V or E. We also find the Wiener indices of a few graphs which frequently arise in mathematical chemistry using inductive methods.     

One sufficient condition for Hamiltonian graphs involving distances

In 1990 G. T. Chen proved that if G is a 2-connected graph of order n and 2|N(x) ∪ N(y)| + d(x) + d(y) ≥ 2n − 1 for each pair of nonadjacent vertices x, y ∈ V (G), then G is Hamiltonian. In this paper we prove that if G is a 2-connected graph of order n and 2|N(x) ∪ N(y)| + d(x)+d(y) ≥ 2n−1 for each pair of nonadjacent vertices x, y ∈ V (G) such that d(x, y) = 2, then G is Hamiltonian.     

Longest Paths and Longest Cycles in Graphs with Large Degree Sums

 Let p(G) and c(G) denote the number of vertices in a longest path and a longest cycle, respectively, of a finite, simple graph G. Define σ₄(G)=min{d(x ₁)+d(x ₂)+ d(x ₃)+d(x ₄) | {x ₁,…,x ₄} is independent in G}. In this paper, the difference p(G)−c(G) is considered for 2-connected graphs G with σ₄(G)≥|V(G)|+3. Among others, we show that p(G)−c(G)≤2 or every longest path in G is a dominating path. Received: August 28, 2000 Final version received: May 23, 2002     

Up-embeddability via girth and the degree-sum of adjacent vertices

Let G be a simple graph of order n and girth g. For any two adjacent vertices u and v of G, if d _G (u) + d _G (v) ⩾ n − 2g + 5 then G is up-embeddable. In the case of 2-edge-connected (resp. 3-edge-connected) graph, G is up-embeddable if d _G (u) + d _G (v) ⩾ n − 2g + 3 (resp. d _G (u) + d _G (v) ⩾ n − 2g −5) for any two adjacent vertices u and v of G. Furthermore, the above three lower bounds are all shown to be tight. This work was supported by National Natural Science Foundation of China (Grant No. 10571013)     

Up-Embeddability of a Graph by Order and Girth

Let G be a connected graph of order n and girth g. If d_G(u) + d_G(v) ≥ n − 2g + 5 for any two non-adjacent vertices u and v, then G is up-embeddable. Further more, the lower bound is best possible. Similarly the result of k-edge connected simple graph with girth g is also obtained, k = 2,3. Partially supported by the Postdoctoral Seience Foundation of Central South University and NNSFC under Grant No. 10751013.     

On the Structure of Graphs with Bounded Asteroidal Number

 A set A⊆V of the vertices of a graph G=(V,E) is an asteroidal set if for each vertex a∈A, the set A\{a} is contained in one component of G−N[a]. The maximum cardinality of an asteroidal set of G, denoted by an (G), is said to be the asteroidal number of G. We investigate structural properties of graphs of bounded asteroidal number. For every k≥1, an (G)≤k if and only if an (H)≤k for every minimal triangulation H of G. A dominating target is a set D of vertices such that D∪S is a dominating set of G for every set S such that G[D∪S] is connected. We show that every graph G has a dominating target with at most an (G) vertices. Finally, a connected graph G has a spanning tree T such that d _T (x,y)−d _G (x,y)≤3·|D|−1 for every pair x,y of vertices and every dominating target D of G. Received: July 3, 1998 Final version received: August 10, 1999     

Degree Sums,Connectivity and Dominating Cycles in Graphs

Let G be a graph of order n with connectivity κ≥3 and let α be the independence number of G. Set σ₄(G)= min{∑⁴ _{i =1} d(x _i ):{x ₁,x ₂,x ₃,x ₄} is an independent set of G}. In this paper, we will prove that if σ₄(G)≥n+2κ, then there exists a longest cycle C of G such that V(G−C) is an independent set of G. Furthermore, if the minimum degree of G is at least α, then G is hamiltonian. Received: July 31, 1998?Final version received: October 4, 2000     

A 2-factor with Short Cycles Passing Through Specified Independent Vertices in Graph

For a graph G, we define σ₂(G) := min{d(u) + d(v)|u, v ≠ ∈ E(G), u ≠ v}. Let k ≥ 1 be an integer and G be a graph of order n ≥ 3k. We prove if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k of length at most four such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k. And show if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k, V(C ₁) ∪...∪ V(C _k ) = V(G), and |C _i | ≤ 4 for all 1 ≤ i ≤ k − 1. The condition of degree sum σ₂(G) ≥ n + k − 1 is sharp. Received: December 20, 2006. Final version received: December 12, 2007.     

Partial Parity (g,f )-Factors and Subgraphs Covering Given Vertex Subsets

 Let G be a graph and W a subset of V(G). Let g,f:V(G)→Z be two integer-valued functions such that g(x)≤f(x) for all x∈V(G) and g(y)≡f(y) (mod 2) for all y∈W. Then a spanning subgraph F of G is called a partial parity (g,f)-factor with respect to W if g(x)≤deg _F (x)≤f(x) for all x∈V(G) and deg _F (y)≡f(y) (mod 2) for all y∈W. We obtain a criterion for a graph G to have a partial parity (g,f)-factor with respect to W. Furthermore, by making use of this criterion, we give some necessary and sufficient conditions for a graph G to have a subgraph which covers W and has a certain given property. Received: June 14, 1999?Final version received: August 21, 2000     

On the Wiener Index of Graphs

The Wiener index of a graph G is defined as W(G)=∑ _u,v d _G (u,v), where d _G (u,v) is the distance between u and v in G and the sum goes over all the pairs of vertices. In this paper, we first present the 6 graphs with the first to the sixth smallest Wiener index among all graphs with n vertices and k cut edges and containing a complete subgraph of order n−k; and then we construct a graph with its Wiener index no less than some integer among all graphs with n vertices and k cut edges.     

How Close to Regular Must a Semicomplete Multipartite Digraph Be to Secure Hamiltonicity?

 Let D be a semicomplete multipartite digraph, with partite sets V ₁, V ₂,…, V _c, such that |V ₁|≤|V ₂|≤…≤|V _c|. Define f(D)=|V(D)|−3|V _c|+1 and . We define the irregularity i(D) of D to be max|d ⁺(x)−d ⁻(y)| over all vertices x and y of D (possibly x=y). We define the local irregularity i _l(D) of D to be max|d ⁺(x)−d ⁻(x)| over all vertices x of D and we define the global irregularity of D to be i _g(D)=max{d ⁺(x),d ⁻(x) : x∈V(D)}−min{d ⁺(y),d ⁻(y) : y∈V(D)}. In this paper we show that if i _g(D)≤g(D) or if i _l(D)≤min{f(D), g(D)} then D is Hamiltonian. We furthermore show how this implies a theorem which generalizes two results by Volkmann and solves a stated problem and a conjecture from [6]. Our result also gives support to the conjecture from [6] that all diregular c-partite tournaments (c≥4) are pancyclic, and it is used in [9], which proves this conjecture for all c≥5. Finally we show that our result in some sense is best possible, by giving an infinite class of non-Hamiltonian semicomplete multipartite digraphs, D, with i _g(D)=i(D)=i _l(D)=g(D)+?≤f(D)+1. Revised: September 17, 1998     

The Convexity Number of a Graph

 For two vertices u and v of a connected graph G, the set I[u,v] consists of all those vertices lying on a u−v shortest path in G, while for a set S of vertices of G, the set I[S] is the union of all sets I[u,v] for u,v∈S. A set S is convex if I[S]=S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. The clique number ω(G) is the maximum cardinality of a clique in G. If G is a connected graph of order n that is not complete, then n≥3 and 2≤ω(G)≤con(G)≤n−1. It is shown that for every triple l,k,n of integers with n≥3 and 2≤l≤k≤n−1, there exists a noncomplete connected graph G of order n with ω(G)=l and con(G)=k. Other results on convex numbers are also presented. Received: August 19, 1998 Final version received: May 17, 2000     

Conditional Resolvability of Honeycomb and Hexagonal Networks

Given a graph G = (V, E), a set W í V{W \subseteq V} is said to be a resolving set if for each pair of distinct vertices u, v ? V{u, v \in V} there is a vertex x in W such that d(u, x) 1 d(v, x){d(u, x) \neq d(v, x)} . The resolving number of G is the minimum cardinality of all resolving sets. In this paper, conditions are imposed on resolving sets and certain conditional resolving parameters are studied for honeycomb and hexagonal networks.     

A Degree Sum Condition Concerning the Connectivity and the Independence Number of a Graph

Let G be a graph and S ⊂ V(G). We denote by α(S) the maximum number of pairwise nonadjacent vertices in S. For x, y ∈ V(G), the local connectivity κ(x, y) is defined to be the maximum number of internally-disjoint paths connecting x and y in G. We define . In this paper, we show that if κ(S) ≥ 3 and for every independent set {x ₁, x ₂, x ₃, x ₄} ⊂ S, then G contains a cycle passing through S. This degree condition is sharp and this gives a new degree sum condition for a 3-connected graph to be hamiltonian.     

Long cycles passing through a specified path in a graph

For a graph G and an integer k ≥ 1, let ς_k(G) = d_G(v_i): {v₁, …, v_k} is an independent set of vertices in G}. Enomoto proved the following theorem. Let s ≥ 1 and let G be a (s + 2)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, ς₂(G) − s} passing through any path of length s. We generalize this result as follows. Let k ≥ 3 and s ≥ 1 and let G be a (k + s − 1)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, − s} passing through any path of length s. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 177–184, 1998     

Cycles in Partially Square Graphs

. In this work we consider finite undirected simple graphs. If G=(V,E) is a graph we denote by α(G) the stability number of G. For any vertex x let N[x] be the union of x and the neighborhood N(x). For each pair of vertices ab of G we associate the set J(a,b) as follows. J(a,b)={u∈N[a]∩N[b]∣N(u)⊆N[a]∪N[b]}. Given a graph G, its partially squareG ^* is the graph obtained by adding an edge uv for each pair u,v of vertices of G at distance 2 whenever J(u,v) is not empty. In the case G is a claw-free graph, G ^* is equal to G ². If G is k-connected, we cover the vertices of G by at most ⌈α(G ^*)/k⌉ cycles, where α(G ^*) is the stability number of the partially square graph of G. On the other hand we consider in G ^* conditions on the sum of the degrees. Let G be any 2-connected graph and t be any integer (t≥2). If ∑ _{x ∈ S} deg _G (x)≥|G|, for every t-stable set S⊆V(G) of G ^* then the vertex set of G can be covered with t−1 cycles. Different corollaries on covering by paths are given. Received: January 22, 1997 Final version received: February 15, 2000