Longest Cycles in 2-Connected Quasi-Claw-Free Graphs
Received:June 04, 2012  Revised:July 07, 2013
Key Words: quasi-claw-free graph   claw-free graph.
Fund Project:Supported by the National Natural Science Foundation of China (Grant No.60673046).
 Author Name Affiliation Xiaodong CHEN College of Science, Liaoning University of Technology, Liaoning 121001, P. R. China Mingchu LI School of Softsware, Dalian University of Technology, Liaoning 116024, P. R. China Xin MA Basic Science Department, Shenyang Urban Construction University, Liaoning 110167, P. R. China
Hits: 2704
A graph $G$ is called quasi-claw-free if it satisfies the property: $d(x,y)=2\Rightarrow$ there exists a vertex $u\in N(x)\cap N(y)$ such that $N[u]\subseteq N[x]\cup N[y]$. In this paper, we show that every 2-connected quasi-claw-free graph of order $n$ with $G\notin \mathcal{F}$ contains a cycle of length at least min$\{3\delta+2,n\}$, where $\mathcal{F}$ is a family of graphs.