| Longest Paths and Cycles in Connected Claw-Free Graphs |
| |
| 作者姓名： | 李明楚 李旭东 |
| |
| 作者单位： | SchoolofElectronicInformationEngineering,TianjinUniversity,Tianjin300072,China |
| |
| 基金项目： | SupportedbytheprojectT2 3ofLiuHuiCenterforAppliedMathe maticsofNankaiUniversityandTianjinUniversity，andNationalNaturalScienceFoundationofChina(No 90 4 12 0 0 7) |
| |
| 摘 要： | A graph is called claw-free if it does not contain a claw as its induced subgraph. In this paper, we prove the following results : 1 ) If G is a 2-connected claw-free graph on n vertices, then for any vertex υ and any two distinct vertices x and y in V(G) - |υ| , G has a path containing v and all neighbors of v and connecting x and y;2) Let C be the longest cycle in a 3-connected claw-free graph G and H a component of G - C,and if H is connected but not 2-connected, then there exist nonadjacent vertices u and v in H such that |V(C)| ≥3(d(u) d(u)) -2.
|
| 关 键 词： | 最长路径 周期 爪自由图 哈密顿函数 |
Longest Paths and Cycles in Connected Claw-Free Graphs |
| |
| LI Ming-chu,LI Xu-dong.Longest Paths and Cycles in Connected Claw-Free Graphs[J].Transactions of Tianjin University,2004,10(3):221-224. |
| |
| Authors: | LI Ming-chu LI Xu-dong |
| |
| Abstract: | A graph is called claw-free if it does not contain a claw as its induced subgraph.In this paper, we prove the following results:1)If G is a 2-connected claw-free graph on n vertices,then for any vertex v and any two distinct vertices x and y in V(G)-{v},G has a path containing v and all neighbors of v and connecting x and y;2) Let C be the longest cycle in a 3-connected claw-free graph G and H a component of G-C,and if H is connected but not 2-connected,then there exist nonadjacent vertices u and v in H such that |V(C)|≥3(d(u)+d(v))-2. |
| |
| Keywords: | longest path cycle claw-free graph |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
