检索结果-南通市图书馆

On hamiltonicity of 2-connected claw-free graphs

在线全文

学校读者我要写书评

暂无评论

Applied Mathematics(A Journal of Chinese Universities) 2012年第2期27卷 234-242页

作者： TIAN Run-li XIONG Li-ming Department of Mathematics Beijing Institute of TechnologyBeijing 100081China Department of Mathematics Jiangxi Normal UniversityNanchang 330022China

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 *** 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.

关键词： claw-free graph Hamiltonian closure the hourglass property the single k-cycle property.

Clique-Transversal Sets in 4-Regular claw-free graphs

在线全文

学校读者我要写书评

暂无评论

Acta Mathematica Sinica,English Series 2011年第5期27卷 883-890页

作者： Er Fang SHAN Li Ying KANG Department of Mathematics Shanghai University Shanghai 200444 P. R. China

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.

关键词： Clique-transversal set claw-free graph line graph regular graph

NEIGHBORHOOD UNION OF INDEPENDENT SETS AND HAMILTONICITY OF claw-free graphS

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Applied Mathematics(A Journal of Chinese Universities) 2005年第1期20卷 121-126页

作者： XuXinping Dept.ofMath.＆Comput.Sci. JiangsuInstituteofEducationNanjing210013China.

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 *** any UV(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 *** related results are obtained too.

关键词： Hamiltonicity claw-free graph independent set neighborhood union vertex insertion.

Hamiltonian Cycles in Regular 2-Connected claw-free graphs

在线全文

学校读者我要写书评

暂无评论

Transactions of Tianjin University 2003年第4期9卷 273-278页

作者：李明楚 School of Electronic Information Engineering

A known result by Jackson Bill is that every 2-connected k-regular graph on at most 3k vertices is Hamiltonian. In this paper,it is proved that every 2-connected k-regular claw-free graph on at most 5k(k≥10)vertices is Hamiltonian. Moreover, the bound 5k is best possible. A counterexample of a 2-connected k-regular claw-free non-Hamiltonian graph on 5k+1 vertices is given, and it is conjectured that every 3-connected k-regular claw-free graph on at most 12k-7 vertices is Hamiltonian.

关键词： Hamiltonian cycle regular claw-free graph circumference

On the Clique-Transversal Number in(claw,K_4 )-free 4-Regular graphs

在线全文

学校读者我要写书评

暂无评论

Acta Mathematica Sinica,English Series 2014年第3期30卷 505-516页

作者： Ding Guo WANG Er Fang SHAN Zuo Song LIANG Department of Mathematics Shanghai University College of Mathematics Science Chongqing Normal University School of Management Shanghai University

A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of *** clique-transversal number,denoted by τC（G）,is the minimum cardinality of a clique-transversal set 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 ***,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].

关键词： graph clique-transversal set clique 4-regular graph claw-free graph

A Property of claw-free graphs

在线全文

学校读者我要写书评

暂无评论

Chinese Quarterly Journal of Mathematics 2011年第3期26卷 445-447页

作者： LU Xiao-xu LI Jin WU Min Department of Mathematics and Physics Zhengzhou Institute of Aeronautical Industry Management Zhengzhou 450015 China Zhengzhou Railway Vocational and Technical College Zhengzhou 450052 China Kaifeng Gongyuan Road East Street Elementary School Kaifeng 475001 China

In this paper we consider a property of claw-free *** 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.

关键词： IM-extendable vertex-deletable IM-extendable claw-free graph

Hamiltonicity,neighborhood union and square graphs of claw-free graphs

在线全文

学校读者我要写书评

暂无评论

Journal of Southeast University(English Edition) 2004年第2期20卷 251-255页

作者：徐新萍江苏教育学院数学系南京210013

Let G be a graph, the square graph G 2 of G is a graph satisfying V(G 2)=V(G) and E(G 2)=E(G)∪｛uv: dist G(u, v)=2｝ . In this paper, we use the technique of vertex insertion on l -connected ( l=k or k+1, k≥2 ) claw-free graphs to provide a unified proof for G to be Hamiltonian, 1 -Hamiltonian or Hamiltonian-connected. The sufficient conditions are expressed by the inequality concerning ∑ k i=0N(Y i) and n(Y) in G for each independent set Y=｛y 0, y 1, …, y k｝ of the square graph of G , where b ( 0

关键词： Hamiltonicity claw-free graph neighborhood union vertex insertion square graph

Some New Results on Double Domination in graphs

在线全文

学校读者我要写书评

暂无评论

Journal of Mathematical Research and Exposition 2005年第3期25卷 451-456页

作者：陈学刚孙良汕头大学数学系广东汕头515063 北京理工大学数学系北京100081

Each vertex of a graph G = （V, E） is said to dominate every vertex in its closed neighborhood. A set S C V is a double dominating set for G if each vertex in V is dominated by at least two vertices in S. The smallest cardinality of a double dominating set is called the double dominating number dd（G）. In this paper, new relationships between dd（G） and other domination parameters are explored and some results of [1] are extended. Furthermore, we give the Nordhaus-Gaddum-type results for double dominating number.

关键词： double domination number claw-free graph connected domination number.

Characterizations of Cycle-Forced 2-Connected claw-free Cubic graphs

在线全文

学校读者我要写书评

暂无评论

Chinese Quarterly Journal of Mathematics 2022年第4期37卷 432-440页

作者： ZHANG Yi-ran WANG Xiu-mei School of Mathematics and Statistics Zhengzhou UniversityZhengzhou 450001China

Let G be a graph and C be an arbitrary even cycle of *** graph G is called a cycle-forced graph if G-V(C)has a unique perfect *** C is an arbitrary induced even cycle of G,G is called an induced-cycle-forced *** G-V(C)has no perfect matching,G is said to be *** paper gives characterizations of these three type of graphs in the class of 2-connected claw-free cubic graphs.

关键词： Perfect matching Cubic graph claw-free graph Cycle-forced graph