The spanning connectivity of line graphs

Po-Yi Huang, Lih Hsing Hsu

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

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
Volume24
Issue number9
DOIs
Publication statusPublished - 2011 Sep 1

Fingerprint

Line Graph
Container
Hamiltonians
Containers
Connectivity
Hamiltonian Connected
Edge-connectivity
Levenberg-Marquardt
Connected graph
Generalise
Disjoint Paths
Fans
Distinct
Graph in graph theory

All Science Journal Classification (ASJC) codes

  • Applied Mathematics

Cite this

Huang, Po-Yi ; Hsu, Lih Hsing. / The spanning connectivity of line graphs. In: Applied Mathematics Letters. 2011 ; Vol. 24, No. 9. pp. 1614-1617.
@article{6ef32e5ceab64ffb9221e6e923ac9639,
title = "The spanning connectivity of line graphs",
abstract = "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.",
author = "Po-Yi Huang and Hsu, {Lih Hsing}",
year = "2011",
month = "9",
day = "1",
doi = "10.1016/j.aml.2011.04.013",
language = "English",
volume = "24",
pages = "1614--1617",
journal = "Applied Mathematics Letters",
issn = "0893-9659",
publisher = "Elsevier Limited",
number = "9",

}

The spanning connectivity of line graphs. / Huang, Po-Yi; Hsu, Lih Hsing.

In: Applied Mathematics Letters, Vol. 24, No. 9, 01.09.2011, p. 1614-1617.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The spanning connectivity of line graphs

AU - Huang, Po-Yi

AU - Hsu, Lih Hsing

PY - 2011/9/1

Y1 - 2011/9/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=79956140335&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79956140335&partnerID=8YFLogxK

U2 - 10.1016/j.aml.2011.04.013

DO - 10.1016/j.aml.2011.04.013

M3 - Article

VL - 24

SP - 1614

EP - 1617

JO - Applied Mathematics Letters

JF - Applied Mathematics Letters

SN - 0893-9659

IS - 9

ER -