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.展开更多
In this paper,we survey known results on color-critical graphs in special graph classes.A graph is k-critical if its chromatic number is k but any proper subgraph of it has chromatic number less than k.For a family H ...In this paper,we survey known results on color-critical graphs in special graph classes.A graph is k-critical if its chromatic number is k but any proper subgraph of it has chromatic number less than k.For a family H of graphs,a graph is H-free if it does not contain H as an induced subgraph for every H∈H.A graph class is hereditary if it is H-free for some set H of graphs,and the graphs in H are called forbidden induced subgraphs for the class.We will focus on the characterization problem and the finiteness problem for hereditary graph classes that can be defined by one or two forbidden induced subgraphs.The characterization problem seeks a complete characterization of k-critical graphs in a given graph class and the finiteness problem asks if the number of k-critical graphs in a given class is finite.We shall survey results for both problems with an emphasis on how the results develop over the time and on the techniques used for proving results in the area.We also list important open problems and give some conjectures.展开更多
Two new hereditary classes of P 5-free graphs where the stability number can be found in polynomial time are proposed.They generalize several known results.
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.展开更多
For non-negative integers i,j and k,let N i,j,k be the graph obtained by identifying end vertices of three disjoint paths of lengths i,j and k to the vertices of a triangle.In this paper,we prove that every 3-connecte...For non-negative integers i,j and k,let N i,j,k be the graph obtained by identifying end vertices of three disjoint paths of lengths i,j and k to the vertices of a triangle.In this paper,we prove that every 3-connected {K1,3,N3,3,3 }-free graph is Hamiltonian.This result is sharp in the sense that for any integer i>3,there exist infinitely many 3-connected {K1,3,Ni,3,3 }-free non-Hamiltonian graphs.展开更多
The eccentricity matrix of a graph is obtained from the distance matrix by keeping the entries that are largest in their row or column,and replacing the remaining entries by zero.This matrix can be interpreted as an o...The eccentricity matrix of a graph is obtained from the distance matrix by keeping the entries that are largest in their row or column,and replacing the remaining entries by zero.This matrix can be interpreted as an opposite to the adjacency matrix,which is on the contrary obtained from the distance matrix by keeping only the entries equal to 1.In the paper,we determine graphs having the second largest eigenvalue of eccentricity matrix less than 1.展开更多
Broersma and Veldman proved that every 2-connected claw-free and P6-free graph is hamil- tonian. Chen et al. extended this result by proving every 2-connected claw-heavy and P6-free graph is hamiltonian. On the other ...Broersma and Veldman proved that every 2-connected claw-free and P6-free graph is hamil- tonian. Chen et al. extended this result by proving every 2-connected claw-heavy and P6-free graph is hamiltonian. On the other hand, Li et al. constructed a class of 2-connected graphs which are claw-heavy and P6-o-heavy but not hamiltonian. In this paper, we further give some Ore-type degree conditions restricting to induced copies of P6 of a 2-connected claw-heavy graph that can guarantee the graph to be hamiltonian. This improves some previous related results.展开更多
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.展开更多
文摘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.
文摘In this paper,we survey known results on color-critical graphs in special graph classes.A graph is k-critical if its chromatic number is k but any proper subgraph of it has chromatic number less than k.For a family H of graphs,a graph is H-free if it does not contain H as an induced subgraph for every H∈H.A graph class is hereditary if it is H-free for some set H of graphs,and the graphs in H are called forbidden induced subgraphs for the class.We will focus on the characterization problem and the finiteness problem for hereditary graph classes that can be defined by one or two forbidden induced subgraphs.The characterization problem seeks a complete characterization of k-critical graphs in a given graph class and the finiteness problem asks if the number of k-critical graphs in a given class is finite.We shall survey results for both problems with an emphasis on how the results develop over the time and on the techniques used for proving results in the area.We also list important open problems and give some conjectures.
基金The first author was supported by DIMACS Summer2 0 0 3Award
文摘Two new hereditary classes of P 5-free graphs where the stability number can be found in polynomial time are proposed.They generalize several known results.
基金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.
基金supported by National Natural Science Foundation of China (Grant Nos.11071096 and 11271149)Hubei Provincial Department of Education (Grant No. D20111110)Jinan Science and Technology Bureau (Grant No. 20110205)
文摘For non-negative integers i,j and k,let N i,j,k be the graph obtained by identifying end vertices of three disjoint paths of lengths i,j and k to the vertices of a triangle.In this paper,we prove that every 3-connected {K1,3,N3,3,3 }-free graph is Hamiltonian.This result is sharp in the sense that for any integer i>3,there exist infinitely many 3-connected {K1,3,Ni,3,3 }-free non-Hamiltonian graphs.
基金supported by the Special Fund for Taishan Scholars Projectthe IC Program of Shandong Institutions of Higher Learning For Youth Innovative Talents+1 种基金supported by the National Natural Science Foundation of China (Grant No. 12371353)supported by the Science Fund of the Republic of Serbia grant number 7749676:Spectrally Constrained Signed Graphs with Applications in Coding Theory and Control Theory–SCSG-ctct
文摘The eccentricity matrix of a graph is obtained from the distance matrix by keeping the entries that are largest in their row or column,and replacing the remaining entries by zero.This matrix can be interpreted as an opposite to the adjacency matrix,which is on the contrary obtained from the distance matrix by keeping only the entries equal to 1.In the paper,we determine graphs having the second largest eigenvalue of eccentricity matrix less than 1.
基金Supported by NSFC(Grant No.11271300)the Natural Science Foundation of Shaanxi Province(Grant No.2016JQ1002)the Project NEXLIZ–CZ.1.07/2.3.00/30.0038
文摘Broersma and Veldman proved that every 2-connected claw-free and P6-free graph is hamil- tonian. Chen et al. extended this result by proving every 2-connected claw-heavy and P6-free graph is hamiltonian. On the other hand, Li et al. constructed a class of 2-connected graphs which are claw-heavy and P6-o-heavy but not hamiltonian. In this paper, we further give some Ore-type degree conditions restricting to induced copies of P6 of a 2-connected claw-heavy graph that can guarantee the graph to be hamiltonian. This improves some previous related results.
基金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.
