Longest Paths and Cycles in Connected Claw-Free Graphs  

Longest Paths and Cycles in Connected Claw-Free Graphs

在线阅读下载全文

作  者:李明楚 李旭东 

机构地区:[1]School of Electronic Information Engineering, Tianjin University, Tianjin 300072, China

出  处:《Transactions of Tianjin University》2004年第3期221-224,共4页天津大学学报(英文版)

基  金: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 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.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.

关 键 词:longest path CYCLE claw-free  graph 

分 类 号:O185[理学—数学]

 

参考文献:

正在载入数据...

 

二级参考文献:

正在载入数据...

 

耦合文献:

正在载入数据...

 

引证文献:

正在载入数据...

 

二级引证文献:

正在载入数据...

 

同被引文献:

正在载入数据...

 

相关期刊文献:

正在载入数据...

相关的主题
相关的作者对象
相关的机构对象