Let G be a graph of order n. We define the distance between two vertices u andv in G, denoted by d（u, v）, as the minimum value of the lengths of all u-v paths. We writeσ<sub>k</sub>（G）=min{∑<sub&g...Let G be a graph of order n. We define the distance between two vertices u andv in G, denoted by d（u, v）, as the minimum value of the lengths of all u-v paths. We writeσ<sub>k</sub>（G）=min{∑<sub>i</sub>=1<sup>k</sup> d（v<sub>i</sub>）|{v<sub>1</sub>, v<sub>2</sub>,…, v<sub>k</sub>} is an independent set in G} and NC2（G）=min {|N（u）∪N（v）| | d（u, v）=2}. We denote by ω（G） the number of components of agraph G. A graph G is called 1-tough if ω（G\S）≤|S| for every subset S of V（G） withω（G\S）】l. By c（G） we denote the length of the longest cycle in G; in particular, G iscalled a Hamiltonian graph if c（G）=n. H.A. Jung proved that every 1-tough graphwith order n≥11 and σ2≥n-4 is Hamiltonian. We generalize it further as follows: ifG is a 1-tough graph and σ3（G）≥n, then c（G）≥min {n,2NC2（G）+4}. Thus, theconjecture of D. Bauer, G. Fan and H.J. Veldman in [2] is completely solved.展开更多
Let G be a graph of order n and X V(G). G is called X-cyclable if G has an X-cycle, i.e., a cycle containing all vertices of X. Define the parameters a(X) = max{|S| S is an independent vertex set in G[X] induced by X...Let G be a graph of order n and X V(G). G is called X-cyclable if G has an X-cycle, i.e., a cycle containing all vertices of X. Define the parameters a(X) = max{|S| S is an independent vertex set in G[X] induced by X}, σk(X) = min{∑ki=1dG(x.i| {x1, x1…, xk} is an independent vertex set in G[X]} and NCk(X) = min{|∪ki=1 NG(xi)| | {x1, x2…,xk} is an independent vertex set in G[X] }. Our main result is as follows: If G is a 1-tough graph and X V(G) with σ3(X)≥ n, then for every integer t ≥ 1, G has a cycle C containing at least min{|X|, (2|X| - n + 3δ + 1 - t), |X| + NCt(X) - a(X)} venices of X, where δ(X) = [σ3(X)]. This result further extends previous results in H.J. Broersma et al. in terms of X-cyclability. We also obtain that if G is a 1-tough graph with σ3 (X) ≥ n, then for every integer t ≥ 1, G has a cycle containing at least min{|X|, (4|X|- 2n+4δ(X) + 1 - 2t), NCt (X) +NCt (X)} vertices of X, where NCt (X) = min{|N(I) ∩X|| I is an independent set of t vertices of X}. Analogous results are established for 2-connected graphs.展开更多
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 research supported by National Natural Science Foundation of China.
文摘Let G be a graph of order n. We define the distance between two vertices u andv in G, denoted by d（u, v）, as the minimum value of the lengths of all u-v paths. We writeσ<sub>k</sub>（G）=min{∑<sub>i</sub>=1<sup>k</sup> d（v<sub>i</sub>）|{v<sub>1</sub>, v<sub>2</sub>,…, v<sub>k</sub>} is an independent set in G} and NC2（G）=min {|N（u）∪N（v）| | d（u, v）=2}. We denote by ω（G） the number of components of agraph G. A graph G is called 1-tough if ω（G\S）≤|S| for every subset S of V（G） withω（G\S）】l. By c（G） we denote the length of the longest cycle in G; in particular, G iscalled a Hamiltonian graph if c（G）=n. H.A. Jung proved that every 1-tough graphwith order n≥11 and σ2≥n-4 is Hamiltonian. We generalize it further as follows: ifG is a 1-tough graph and σ3（G）≥n, then c（G）≥min {n,2NC2（G）+4}. Thus, theconjecture of D. Bauer, G. Fan and H.J. Veldman in [2] is completely solved.
基金the Natural Science Foundation of Yunnan Province.
文摘Let G be a graph of order n and X V(G). G is called X-cyclable if G has an X-cycle, i.e., a cycle containing all vertices of X. Define the parameters a(X) = max{|S| S is an independent vertex set in G[X] induced by X}, σk(X) = min{∑ki=1dG(x.i| {x1, x1…, xk} is an independent vertex set in G[X]} and NCk(X) = min{|∪ki=1 NG(xi)| | {x1, x2…,xk} is an independent vertex set in G[X] }. Our main result is as follows: If G is a 1-tough graph and X V(G) with σ3(X)≥ n, then for every integer t ≥ 1, G has a cycle C containing at least min{|X|, (2|X| - n + 3δ + 1 - t), |X| + NCt(X) - a(X)} venices of X, where δ(X) = [σ3(X)]. This result further extends previous results in H.J. Broersma et al. in terms of X-cyclability. We also obtain that if G is a 1-tough graph with σ3 (X) ≥ n, then for every integer t ≥ 1, G has a cycle containing at least min{|X|, (4|X|- 2n+4δ(X) + 1 - 2t), NCt (X) +NCt (X)} vertices of X, where NCt (X) = min{|N(I) ∩X|| I is an independent set of t vertices of X}. Analogous results are established for 2-connected graphs.
基金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.
