A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G. The clique-transversal number, denoted τ c (G), is the minimum cardinality of a clique-transversal set in G. In th...A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G. The clique-transversal number, denoted τ c (G), is the minimum cardinality of a clique-transversal set in G. In this paper we present the bounds on the clique-transversal number for regular graphs and characterize the extremal graphs achieving the lower bound. Also, we give the sharp bounds on the clique-transversal number for claw-free cubic graphs and we characterize the extremal graphs achieving the lower bound.展开更多
In this paper it is shown that every connected claw-free graph G contains connected [a, max{a + 2, b}]-factors if it has [a, b]-factors, where a, b are integers and b ≥ a ≥ 1.
A clique-transversal set D of a graph C is a set of vertices of G such that D meets all cliques of G. The clique-transversal number, denoted by To（G）, is the minimum cardinality of a clique- transversal set in G. In...A clique-transversal set D of a graph C is a set of vertices of G such that D meets all cliques of G. The clique-transversal number, denoted by To（G）, is the minimum cardinality of a clique- transversal set in G. In this paper we give the exact value of the clique-transversal number for the line graph of a complete graph. Also, we give a lower bound on the clique-transversal number for 4-regular claw-free graphs and characterize the extremal graphs achieving the lower bound.展开更多
A graph G has the hourglass property if every induced hourglass S（a tree with a degree sequence 22224） contains two non-adjacent vertices which have a common neighbor in G-V（S）.For an integer k≥4,a graph G has th...A graph G has the hourglass property if every induced hourglass S（a tree with a degree sequence 22224） contains two non-adjacent vertices which have a common neighbor in G-V（S）.For an integer k≥4,a graph G has the single k-cycle property if every edge of G,which does not lie in a triangle,lies in a cycle C of order at most k such that C has at least「｜V（C） /2」 edges which do not lie in a triangle,and they are not adjacent.In this paper,we show that every hourglass-free claw-free graph G of δ（G） ≥3 with the single 7-cycle property is Hamiltonian and is best possible;we also show that every claw-free graph G of δ（G） ≥3 with the hourglass property and with single 6-cycle property is Hamiltonian.展开更多
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.展开更多
M. Matthews and D. Sumner proved that if G is a 2-connected claw-free graph of order n, then c(G) min{2δb + 4, n}. In this paper, we prove that if G is a,2-connected claw-free graph on n venices, then c(G) min{3δ + ...M. Matthews and D. Sumner proved that if G is a 2-connected claw-free graph of order n, then c(G) min{2δb + 4, n}. In this paper, we prove that if G is a,2-connected claw-free graph on n venices, then c(G) min{3δ + 2, n} or G belongs to one exceptional class of graphs.展开更多
In this paper we consider a property of claw-free graphs.We show that if d(u)+ d(v)≥ν(G)+2k+3,for every two nonadjacent vertices u and v,then G is 2k-vertex-deletable IM-extendable,whereν(G)=|V(G)|.And the bound is...In this paper we consider a property of claw-free graphs.We show that if d(u)+ d(v)≥ν(G)+2k+3,for every two nonadjacent vertices u and v,then G is 2k-vertex-deletable IM-extendable,whereν(G)=|V(G)|.And the bound is tight.展开更多
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 graph is said to be claw-free if it does not contain an induced subgraph isomorphic to K_（1,3）. Let s and k be two integers with 0≤s≤k and let G be a claw-free graph of order n. In this paper, we investigate cli...A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to K_（1,3）. Let s and k be two integers with 0≤s≤k and let G be a claw-free graph of order n. In this paper, we investigate clique partition problems in claw-free graphs. It is proved that if n≥3 s ＋4（k-s） and d（x）＋ d（y）≥n-2 s ＋2 k ＋1 for any pair of non-adjacent vertices x, y of G, then G contains s disjoint K3 s and k-s disjoint K4 s such that all of them are disjoint. Moreover, the degree condition is sharp in some cases.展开更多
The degree d(H)of a subgraph H of a graph G is|u∈∪V(H)N(u)-V(H)|,where N(u)denotes the neighbor set of the vertex u of G.In this paper,we prove the following result on the condition of the degrees of subgraphs.Let G...The degree d(H)of a subgraph H of a graph G is|u∈∪V(H)N(u)-V(H)|,where N(u)denotes the neighbor set of the vertex u of G.In this paper,we prove the following result on the condition of the degrees of subgraphs.Let G be a 2-connected claw-free graph of order n with minimum degreeδ(G)≥3.If for any three non-adjacent subgraphs H1,H2,H3 that are isomorphic to K1,K1,K2,respectively,there is d(H1)+d(H2)+d(H3)≥n+3,then for each pair of vertices u,v∈G that is not a cut set,there exists a Hamilton path between u and v.展开更多
A graph is called claw-free if it contains no induced subgrapn lsomorpmc to K1,3. Matthews and Sumner proved that a 2-connected claw-free graph G is Hamiltonian if every vertex of it has degree at least （[V（G）I - 2...A graph is called claw-free if it contains no induced subgrapn lsomorpmc to K1,3. Matthews and Sumner proved that a 2-connected claw-free graph G is Hamiltonian if every vertex of it has degree at least （[V（G）I - 2）/3. At the workshop CSzC （Novy Smokovec, 1993）, Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies of N （the graph obtained from a triangle by adding three disjoint pendant edges）. Fujisawa and Yamashita showed that the degree condition of Matthews and Sumner can be restricted only to end-vertices of induced copies of Z1 （the graph obtained from a triangle by adding one pendant edge）. Our main result in this paper is a characterization of all graphs H such that a 2-connected claw-free graph G is Hamiltonian if eachend-vertex of every induced copy of H in G has degree at least IV（G）I/3 ＋ 1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.end-vertex of every induced copy of H in G has degree at least IV（G）I/3 ＋ 1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.展开更多
A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G.The clique-transversal number,denoted by τC（G）,is the minimum cardinality of a clique-transversal set in G.In thi...A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G.The clique-transversal number,denoted by τC（G）,is the minimum cardinality of a clique-transversal set in G.In this paper,we first present a lower bound on τC（G） and characterize the extremal graphs achieving the lower bound for a connected（claw,K4）-free 4-regular graph G.Furthermore,we show that for any 2-connected（claw,K4）-free 4-regular graph G of order n,its clique-transversal number equals to [n/3].展开更多
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.展开更多
The induced matching cover number of a graph G without isolated vertices, denoted by imc(G),is the minimum integer k such that G has k induced matchings {M1,M2,···,Mk}such that,V(M1)∪V(M2)∪··...The induced matching cover number of a graph G without isolated vertices, denoted by imc(G),is the minimum integer k such that G has k induced matchings {M1,M2,···,Mk}such that,V(M1)∪V(M2)∪···∪V(Mk)covers V(G).This paper shows that,if G is a 3-regular claw-free graph,then imc(G)∈{2,3}.展开更多
基金the National Nature Science Foundation of China (Grant Nos.10571117,60773078)the Hong Kong Polytechnic University (Grant No.G-YX69) Shuguang Plan of Shanghai Education Development Foundation (Grant No.06SG42)
文摘A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G. The clique-transversal number, denoted τ c (G), is the minimum cardinality of a clique-transversal set in G. In this paper we present the bounds on the clique-transversal number for regular graphs and characterize the extremal graphs achieving the lower bound. Also, we give the sharp bounds on the clique-transversal number for claw-free cubic graphs and we characterize the extremal graphs achieving the lower bound.
基金the National Natural Science Foundation of China.
文摘In this paper it is shown that every connected claw-free graph G contains connected [a, max{a + 2, b}]-factors if it has [a, b]-factors, where a, b are integers and b ≥ a ≥ 1.
基金Supported by National Natural Science Foundation of China （Grant No. 60773078）, the PuJiang Project of Shanghai （Grant No. 09PJ1405000） and Key Disciplines of Shanghai Municipality （Grant No. $30104）
文摘A clique-transversal set D of a graph C is a set of vertices of G such that D meets all cliques of G. The clique-transversal number, denoted by To（G）, is the minimum cardinality of a clique- transversal set in G. In this paper we give the exact value of the clique-transversal number for the line graph of a complete graph. Also, we give a lower bound on the clique-transversal number for 4-regular claw-free graphs and characterize the extremal graphs achieving the lower bound.
基金Supported by the National Natural Science Foundation of China(11071016 and 11171129)the Beijing Natural Science Foundation(1102015)
文摘A graph G has the hourglass property if every induced hourglass S（a tree with a degree sequence 22224） contains two non-adjacent vertices which have a common neighbor in G-V（S）.For an integer k≥4,a graph G has the single k-cycle property if every edge of G,which does not lie in a triangle,lies in a cycle C of order at most k such that C has at least「｜V（C） /2」 edges which do not lie in a triangle,and they are not adjacent.In this paper,we show that every hourglass-free claw-free graph G of δ（G） ≥3 with the single 7-cycle property is Hamiltonian and is best possible;we also show that every claw-free graph G of δ（G） ≥3 with the hourglass property and with single 6-cycle property is Hamiltonian.
基金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.
文摘M. Matthews and D. Sumner proved that if G is a 2-connected claw-free graph of order n, then c(G) min{2δb + 4, n}. In this paper, we prove that if G is a,2-connected claw-free graph on n venices, then c(G) min{3δ + 2, n} or G belongs to one exceptional class of graphs.
基金Supported by the National Natural Sciences Youth Foundation(10901144)
文摘In this paper we consider a property of claw-free graphs.We show that if d(u)+ d(v)≥ν(G)+2k+3,for every two nonadjacent vertices u and v,then G is 2k-vertex-deletable IM-extendable,whereν(G)=|V(G)|.And the bound is tight.
文摘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.
基金Supported by the National Natural Science Foundation of China(Grant No.11271230,11671232)
文摘A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to K_（1,3）. Let s and k be two integers with 0≤s≤k and let G be a claw-free graph of order n. In this paper, we investigate clique partition problems in claw-free graphs. It is proved that if n≥3 s ＋4（k-s） and d（x）＋ d（y）≥n-2 s ＋2 k ＋1 for any pair of non-adjacent vertices x, y of G, then G contains s disjoint K3 s and k-s disjoint K4 s such that all of them are disjoint. Moreover, the degree condition is sharp in some cases.
基金supported by the National Natural Science Foundation of China(No.11871398)the Natural Science Basic Research Plan in Shaanxi Province of China(Program No.2018JM1032)+1 种基金the Fundamental Research Funds for the Central Universities(No.3102019ghjd003)the Seed Foundation of Innovation and Creation for Graduate Students in Northwestern Polytechnical University(No.ZZ2019031)
文摘The degree d(H)of a subgraph H of a graph G is|u∈∪V(H)N(u)-V(H)|,where N(u)denotes the neighbor set of the vertex u of G.In this paper,we prove the following result on the condition of the degrees of subgraphs.Let G be a 2-connected claw-free graph of order n with minimum degreeδ(G)≥3.If for any three non-adjacent subgraphs H1,H2,H3 that are isomorphic to K1,K1,K2,respectively,there is d(H1)+d(H2)+d(H3)≥n+3,then for each pair of vertices u,v∈G that is not a cut set,there exists a Hamilton path between u and v.
基金Supported by NSFC(Grant Nos.11271300 and 11571135)the project NEXLIZ–CZ.1.07/2.3.00/30.0038+1 种基金the project P202/12/G061 of the Czech Science Foundation and by the European Regional Development Fund(ERDF)the project NTIS-New Technologies for Information Society,European Centre of Excellence,CZ.1.05/1.1.00/02.0090
文摘A graph is called claw-free if it contains no induced subgrapn lsomorpmc to K1,3. Matthews and Sumner proved that a 2-connected claw-free graph G is Hamiltonian if every vertex of it has degree at least （[V（G）I - 2）/3. At the workshop CSzC （Novy Smokovec, 1993）, Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies of N （the graph obtained from a triangle by adding three disjoint pendant edges）. Fujisawa and Yamashita showed that the degree condition of Matthews and Sumner can be restricted only to end-vertices of induced copies of Z1 （the graph obtained from a triangle by adding one pendant edge）. Our main result in this paper is a characterization of all graphs H such that a 2-connected claw-free graph G is Hamiltonian if eachend-vertex of every induced copy of H in G has degree at least IV（G）I/3 ＋ 1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.end-vertex of every induced copy of H in G has degree at least IV（G）I/3 ＋ 1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.
基金Supported by National Nature Science Foundation of China(Grant Nos.11171207 and 10971131)
文摘A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G.The clique-transversal number,denoted by τC（G）,is the minimum cardinality of a clique-transversal set in G.In this paper,we first present a lower bound on τC（G） and characterize the extremal graphs achieving the lower bound for a connected（claw,K4）-free 4-regular graph G.Furthermore,we show that for any 2-connected（claw,K4）-free 4-regular graph G of order n,its clique-transversal number equals to [n/3].
基金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 the National Natural Science Foundation of China（10771179）
文摘The induced matching cover number of a graph G without isolated vertices, denoted by imc(G),is the minimum integer k such that G has k induced matchings {M1,M2,···,Mk}such that,V(M1)∪V(M2)∪···∪V(Mk)covers V(G).This paper shows that,if G is a 3-regular claw-free graph,then imc(G)∈{2,3}.
