A cycle C of a graph G is a m-distance-dominating cycle if for all vertices of . Defining denotes the minimum value of the degree sum of any k independent vertices of G. In this paper, we prove that if G is a 3-connec...A cycle C of a graph G is a m-distance-dominating cycle if for all vertices of . Defining denotes the minimum value of the degree sum of any k independent vertices of G. In this paper, we prove that if G is a 3-connected graph on n vertices, and if , then every longest cycle is m-distance-dominating cycles.展开更多
Let σk（G） denote the minimum degree sum of k independent vertices in G and α（G） denote the number of the vertices of a maximum independent set of G. In this paper we prove that if G is a 4-connected graph of ord...Let σk（G） denote the minimum degree sum of k independent vertices in G and α（G） denote the number of the vertices of a maximum independent set of G. In this paper we prove that if G is a 4-connected graph of order n and σ5（G） 〉 n ＋ 3σ（G） ＋ 11, then G is Hamiltonian.展开更多
For a vertex set{u<sub>1</sub>,u<sub>2</sub>,…,u<sub>k</sub>}of a graph G with n vertices,let s（G;{u<sub>1</sub>,u<sub>2</sub>,…,u<sub>k</sub>...For a vertex set{u<sub>1</sub>,u<sub>2</sub>,…,u<sub>k</sub>}of a graph G with n vertices,let s（G;{u<sub>1</sub>,u<sub>2</sub>,…,u<sub>k</sub>}）=Σ<sub>1</sub>≤i≤j≤k<sup>|N（u<sub>i</sub>）UN（u<sub>j</sub>）|</sup>, NC<sub>k</sub>.=min{s（G;{x<sub>1</sub>,…,x<sub>k</sub>}）:{x<sub>1</sub>,…,x<sub>k</sub>}is an independent set}. In this paper,we shall prove that if G is 3-connected and NC<sub>4</sub>≥3n,then G is either a hamiltonian or Petersen graph.This generalizes some results on the neighborhood union conditions for hamiltonian graphs.展开更多
A tree with at most m leaves is called an m-ended tree.Kyaw proved that every connected K1,4-free graph withσ4(G)n-1 contains a spanning 3-ended tree.In this paper we obtain a result for k-connected K1,4-free graphs ...A tree with at most m leaves is called an m-ended tree.Kyaw proved that every connected K1,4-free graph withσ4(G)n-1 contains a spanning 3-ended tree.In this paper we obtain a result for k-connected K1,4-free graphs with k 2.Let G be a k-connected K1,4-free graph of order n with k 2.Ifσk+3(G)n+2k-2,then G contains a spanning 3-ended tree.展开更多
Let G be a graph. An independent set Y in G is called an essential independent set (or essential set for simplicity) if there is {yi , y2} Y such that dist(y1 , y2) - 2. For integer t > 0, let It(G) = {Y| Y is an i...Let G be a graph. An independent set Y in G is called an essential independent set (or essential set for simplicity) if there is {yi , y2} Y such that dist(y1 , y2) - 2. For integer t > 0, let It(G) = {Y| Y is an independent set of G, |Y| = t}, It(G) = {Y|Y is an essential set of G, |Y| = t}. For ∈E It(G), let si(y) = |{v|v ∈V(G), |N(v) n Y| = i}|(i = 0, 1,…, t). Let X, Y g V(G). Define dist(X, Y) = dist(u, v), n(Y) = |{v|v ∈V(G), dist({v}, Y) ≤ 2}|. A non-negative rational sequence (a1，a2,…, ak+1) (k ≥2) is called an LTW-sequence, if it satisfies 1) a1 ≤ 1; 2) for arbitrary i1, i2,…，ih. ∈{2,3,……, k + 1}, The main new results of this paper are as follows: Let (a1， a2，… ak+1) be all LTW-sequence, and k ≥ 2. If G is a k-connected graph, and then G has a Hamilton cycle; if G is a (k + 1)-connected graph and for each then G is Hamilton-connected. The existing results are generalized by these since Ik+1(G) is replaced by I(G). We introduce a new technique of T-insertion in this paper， by using the T-vertex inserting lemmas we give a unified proof for a graph to be hamiltonian or Hamilton-connected.展开更多
Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u.For any UV(G),let N(U)=∪_~u∈U N(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgra...Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u.For any UV(G),let N(U)=∪_~u∈U N(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgraph isomorphic to K_~1,3 .One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng,et al.: Let G be a 2-connected claw-free graph of order n,and d(u)+d(v)+d(w)≥n-2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that,for any three positive integers s,t and w,such that if G is a (s+t+w-1)-connected claw-free graph of order n,and d(S)+d(T)+d(W)>n-(s+t+w) for every three disjoint independent vertex sets S,T,W with |S|=s,|T|=t,|W|=w,and S∪T∪W is also independent,then G is Hamiltonian.Other related results are obtained too.展开更多
文摘A cycle C of a graph G is a m-distance-dominating cycle if for all vertices of . Defining denotes the minimum value of the degree sum of any k independent vertices of G. In this paper, we prove that if G is a 3-connected graph on n vertices, and if , then every longest cycle is m-distance-dominating cycles.
基金Supported by NNSF of China (Grant No. 60373012)supported by NSFC (Grant No. 10601044)XJEDU2006S05
文摘Let σk（G） denote the minimum degree sum of k independent vertices in G and α（G） denote the number of the vertices of a maximum independent set of G. In this paper we prove that if G is a 4-connected graph of order n and σ5（G） 〉 n ＋ 3σ（G） ＋ 11, then G is Hamiltonian.
基金Supported by the National Natural Science Foundation of ChinaSupported also by the Post-doctoral Foundation of China
文摘For a vertex set{u<sub>1</sub>,u<sub>2</sub>,…,u<sub>k</sub>}of a graph G with n vertices,let s（G;{u<sub>1</sub>,u<sub>2</sub>,…,u<sub>k</sub>}）=Σ<sub>1</sub>≤i≤j≤k<sup>|N（u<sub>i</sub>）UN（u<sub>j</sub>）|</sup>, NC<sub>k</sub>.=min{s（G;{x<sub>1</sub>,…,x<sub>k</sub>}）:{x<sub>1</sub>,…,x<sub>k</sub>}is an independent set}. In this paper,we shall prove that if G is 3-connected and NC<sub>4</sub>≥3n,then G is either a hamiltonian or Petersen graph.This generalizes some results on the neighborhood union conditions for hamiltonian graphs.
基金supported by Scientific Research Fund of Hubei Provincial Education Department (Grant No. Q20141609)National Natural Science Foundation of China (Grant Nos. 11371162 and 11271149)Wuhan Textile University (2012)
文摘A tree with at most m leaves is called an m-ended tree.Kyaw proved that every connected K1,4-free graph withσ4(G)n-1 contains a spanning 3-ended tree.In this paper we obtain a result for k-connected K1,4-free graphs with k 2.Let G be a k-connected K1,4-free graph of order n with k 2.Ifσk+3(G)n+2k-2,then G contains a spanning 3-ended tree.
文摘Let G be a graph. An independent set Y in G is called an essential independent set (or essential set for simplicity) if there is {yi , y2} Y such that dist(y1 , y2) - 2. For integer t > 0, let It(G) = {Y| Y is an independent set of G, |Y| = t}, It(G) = {Y|Y is an essential set of G, |Y| = t}. For ∈E It(G), let si(y) = |{v|v ∈V(G), |N(v) n Y| = i}|(i = 0, 1,…, t). Let X, Y g V(G). Define dist(X, Y) = dist(u, v), n(Y) = |{v|v ∈V(G), dist({v}, Y) ≤ 2}|. A non-negative rational sequence (a1，a2,…, ak+1) (k ≥2) is called an LTW-sequence, if it satisfies 1) a1 ≤ 1; 2) for arbitrary i1, i2,…，ih. ∈{2,3,……, k + 1}, The main new results of this paper are as follows: Let (a1， a2，… ak+1) be all LTW-sequence, and k ≥ 2. If G is a k-connected graph, and then G has a Hamilton cycle; if G is a (k + 1)-connected graph and for each then G is Hamilton-connected. The existing results are generalized by these since Ik+1(G) is replaced by I(G). We introduce a new technique of T-insertion in this paper， by using the T-vertex inserting lemmas we give a unified proof for a graph to be hamiltonian or Hamilton-connected.
文摘Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u.For any UV(G),let N(U)=∪_~u∈U N(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgraph isomorphic to K_~1,3 .One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng,et al.: Let G be a 2-connected claw-free graph of order n,and d(u)+d(v)+d(w)≥n-2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that,for any three positive integers s,t and w,such that if G is a (s+t+w-1)-connected claw-free graph of order n,and d(S)+d(T)+d(W)>n-(s+t+w) for every three disjoint independent vertex sets S,T,W with |S|=s,|T|=t,|W|=w,and S∪T∪W is also independent,then G is Hamiltonian.Other related results are obtained too.
