首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Essential edge connectivity of line graphs
Authors:Yehong Shao
Institution:Arts and Science, Ohio University Southern, Ironton, OH 45638, USA
Abstract:Let G be a graph and L(G) be its line graph. In 1969, Chartrand and Stewart proved that κ(L(G))2κ(G)?2, where κ(G) and κ(L(G)) denote the edge connectivity of G and L(G) respectively. We show a similar relationship holds for the essential edge connectivity of G and L(G), written κe(G) and κe(L(G)), respectively. In this note, it is proved that if L(G) is not a complete graph and G does not have a vertex of degree two, then κe(L(G))2κe(G)?2. An immediate corollary is that κ(L2(G))2κ(L(G))?2 for such graphs G, where the vertex connectivity of the line graph L(G) and the second iterated line graph L2(G) are written as κ(L(G)) and κ(L2(G)) respectively.
Keywords:Edge connectivity  Essential edge connectivity  Iterated line graph
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号