The spanning connectivity of line graphs

Po Yi Huang, Lih Hsing Hsu

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)


A k-container of G between u and v, C(u,v), is a set of k internally disjoint paths between u and v. A k*-container C(u,v) of G is a k-container if it contains all vertices of G. A graph G is k *-connected if there exists a k*-container between any two distinct vertices. Thus, every 1*-connected graph is Hamiltonian connected. Moreover, every 2*-connected graph is Hamiltonian. Zhan proved that G=L(M) is Hamiltonian connected if the edge-connectivity of M is at least 4. In this paper, we generalize this result by proving G=L(M) is k*-connected if the edge-connectivity of M is at least max2k,4. We also generalize our result into spanning fan-connectivity.

Original languageEnglish
Pages (from-to)1614-1617
Number of pages4
JournalApplied Mathematics Letters
Issue number9
Publication statusPublished - 2011 Sep

All Science Journal Classification (ASJC) codes

  • Applied Mathematics

Fingerprint Dive into the research topics of 'The spanning connectivity of line graphs'. Together they form a unique fingerprint.

Cite this