A graph is called traceable if it contains a Hamilton path, i.e., a path passing through all the vertices. Let G be a graph on n vertices. G is called claw-o-1-heavy if every induced claw(K_(1,3)) of G has a pair of n...A graph is called traceable if it contains a Hamilton path, i.e., a path passing through all the vertices. Let G be a graph on n vertices. G is called claw-o-1-heavy if every induced claw(K_(1,3)) of G has a pair of nonadjacent vertices with degree sum at least n-1 in G. In this paper we show that a claw-o-1-heavy graph G is traceable if we impose certain additional conditions on G involving forbidden induced subgraphs.展开更多
For non-negative integers i,j and k, we denote the generalized net as Ni,j,k, which is a triangle with disjoint paths of length i, j and k, attached to distinct vertices of the triangle. In this paper, we prove that e...For non-negative integers i,j and k, we denote the generalized net as Ni,j,k, which is a triangle with disjoint paths of length i, j and k, attached to distinct vertices of the triangle. In this paper, we prove that every 3-connected {K1,3,N8-i,i,1}-free graph is hamiltonian, where 1〈i〈4.展开更多
A graph is claw-free if it contains no induced subgraph isomorphic to a K1,3.This paper studies hamiltonicity in 3-connected claw-free graphs.Four generation of Shepherd’s result[4] are obtained.For example,we show t...A graph is claw-free if it contains no induced subgraph isomorphic to a K1,3.This paper studies hamiltonicity in 3-connected claw-free graphs.Four generation of Shepherd’s result[4] are obtained.For example,we show that if G is.3-connected claw-free graph and(1)if for each vertex V the set of venices at distance three from v doesn’tcontain and independent subset of size three,then G is hamiltonian;(2) if G contains no induced subgraph with degree sequence(1,1,1,2,2,2,3,3,3),so that ear vertel of degree is adjacent to a vertex of degree i + 1 for i=1,2,then G is hamiltonoan. Furthermore,we obtain a generalization of both(1) and(2),in which the graphs F1 and F2coatain an the known forbidded subgraphs given in[3] as indeced subgraphs.展开更多
The planar Ramsey number PR (H1, H2) is the smallest integer n such that any planar graph on n vertices contains a copy of H1 or its complement contains a copy of H2. It is known that the Ramsey number R(K4 -e, K6) = ...The planar Ramsey number PR (H1, H2) is the smallest integer n such that any planar graph on n vertices contains a copy of H1 or its complement contains a copy of H2. It is known that the Ramsey number R(K4 -e, K6) = 21, and the planar Ramsey numbers PR(K4 - e, Kl) for l ≤ 5 are known. In this paper, we give the lower bounds on PR (K4 ? e, Kl) and determine the exact value of PR (K4 - e, K6).展开更多
All bipartite graphs whose third largest Laplacian eigenvalue is less than 3 have been characterized by Zhang. In this paper, all connected non-bipartite graphs with third largest Laplacian eigenvalue less than three ...All bipartite graphs whose third largest Laplacian eigenvalue is less than 3 have been characterized by Zhang. In this paper, all connected non-bipartite graphs with third largest Laplacian eigenvalue less than three are determined.展开更多
基金Supported by the National Natural Science Foundation of China(No.11601429,11671320 and U1803263)the Fundamental Research Funds for the Central Universities(No.3102018zy035)
文摘A graph is called traceable if it contains a Hamilton path, i.e., a path passing through all the vertices. Let G be a graph on n vertices. G is called claw-o-1-heavy if every induced claw(K_(1,3)) of G has a pair of nonadjacent vertices with degree sum at least n-1 in G. In this paper we show that a claw-o-1-heavy graph G is traceable if we impose certain additional conditions on G involving forbidden induced subgraphs.
基金Supported by the National Natural Science Foundation of China(No.11371162 and No.11271149)A project of Shandong Province Higher Educational Science and Technology Program(No.J15LI52)Science and Technology Development Project of Shandong Province(No.2014GGX101033)
文摘For non-negative integers i,j and k, we denote the generalized net as Ni,j,k, which is a triangle with disjoint paths of length i, j and k, attached to distinct vertices of the triangle. In this paper, we prove that every 3-connected {K1,3,N8-i,i,1}-free graph is hamiltonian, where 1〈i〈4.
文摘A graph is claw-free if it contains no induced subgraph isomorphic to a K1,3.This paper studies hamiltonicity in 3-connected claw-free graphs.Four generation of Shepherd’s result[4] are obtained.For example,we show that if G is.3-connected claw-free graph and(1)if for each vertex V the set of venices at distance three from v doesn’tcontain and independent subset of size three,then G is hamiltonian;(2) if G contains no induced subgraph with degree sequence(1,1,1,2,2,2,3,3,3),so that ear vertel of degree is adjacent to a vertex of degree i + 1 for i=1,2,then G is hamiltonoan. Furthermore,we obtain a generalization of both(1) and(2),in which the graphs F1 and F2coatain an the known forbidded subgraphs given in[3] as indeced subgraphs.
基金supported by NSFSD(No.BS2010SF017,Y2008A04)NNSFC(No.11101245)+1 种基金Foundation of Education Committee of Shandong Province(J07YH03)Foundation of Shandong Institute of Business and Technology(2011QF073)
文摘The planar Ramsey number PR (H1, H2) is the smallest integer n such that any planar graph on n vertices contains a copy of H1 or its complement contains a copy of H2. It is known that the Ramsey number R(K4 -e, K6) = 21, and the planar Ramsey numbers PR(K4 - e, Kl) for l ≤ 5 are known. In this paper, we give the lower bounds on PR (K4 ? e, Kl) and determine the exact value of PR (K4 - e, K6).
基金Supported by National Natural Science Foundation of China(No.10371075 and No.10531070)
文摘All bipartite graphs whose third largest Laplacian eigenvalue is less than 3 have been characterized by Zhang. In this paper, all connected non-bipartite graphs with third largest Laplacian eigenvalue less than three are determined.
