Traceability of line graphs

Liming Xiong; Minmin Zong

doi:10.1016/j.disc.2008.10.012

Traceability of line graphs

Liming Xiong^*, Minmin Zong

^*Corresponding author for this work

School of Mathematics and Statistics

Research output: Contribution to journal › Article › peer-review

11 Citations (Scopus)

Abstract

Brualdi and Shanny [R.A. Brualdi, R.F. Shanny, Hamiltonian line graphs, J. Graph Theory 5 (1981) 307-314], Clark [L. Clark, On hamitonian line graphs, J. Graph Theory 8 (1984) 303-307] and Veldman [H.J. Veldman, On dominating and spanning circuits in graphs, Discrete Math. 124 (1994) 229-239] gave minimum degree conditions of a line graph guaranteeing the line graph to be hamiltonian. In this paper, we investigate the similar conditions guaranteeing a line graph to be traceable. In particular, we show the following result: let G be a simple graph of order n and L (G) its line graph. If n is sufficiently large and, either δ (L (G)) > 2 ⌊ frac(n - 8, 4) ⌋; or δ (L (G)) > 2 ⌊ frac(n - 20, 10) ⌋ and G is almost bridgeless, then L (G) is traceable. As a byproduct, we also show that every 2-edge-connected triangle-free simple graph with order at most 9 has a spanning trail. These results are all best possible.

Original language	English
Pages (from-to)	3779-3785
Number of pages	7
Journal	Discrete Mathematics
Volume	309
Issue number	12
DOIs	https://doi.org/10.1016/j.disc.2008.10.012
Publication status	Published - 28 Jun 2009

Keywords

Degree sum of adjacent vertices
Dominating trail
Hamiltonian cycle(path)
Line graph
Spanning trail

Access to Document

10.1016/j.disc.2008.10.012

Cite this

@article{12af7e5dfbe845d99fcf848574087fea,

title = "Traceability of line graphs",

abstract = "Brualdi and Shanny [R.A. Brualdi, R.F. Shanny, Hamiltonian line graphs, J. Graph Theory 5 (1981) 307-314], Clark [L. Clark, On hamitonian line graphs, J. Graph Theory 8 (1984) 303-307] and Veldman [H.J. Veldman, On dominating and spanning circuits in graphs, Discrete Math. 124 (1994) 229-239] gave minimum degree conditions of a line graph guaranteeing the line graph to be hamiltonian. In this paper, we investigate the similar conditions guaranteeing a line graph to be traceable. In particular, we show the following result: let G be a simple graph of order n and L (G) its line graph. If n is sufficiently large and, either δ (L (G)) > 2 ⌊ frac(n - 8, 4) ⌋; or δ (L (G)) > 2 ⌊ frac(n - 20, 10) ⌋ and G is almost bridgeless, then L (G) is traceable. As a byproduct, we also show that every 2-edge-connected triangle-free simple graph with order at most 9 has a spanning trail. These results are all best possible.",

keywords = "Degree sum of adjacent vertices, Dominating trail, Hamiltonian cycle(path), Line graph, Spanning trail",

author = "Liming Xiong and Minmin Zong",

year = "2009",

month = jun,

day = "28",

doi = "10.1016/j.disc.2008.10.012",

language = "English",

volume = "309",

pages = "3779--3785",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "12",

}

TY - JOUR

T1 - Traceability of line graphs

AU - Xiong, Liming

AU - Zong, Minmin

PY - 2009/6/28

Y1 - 2009/6/28

N2 - Brualdi and Shanny [R.A. Brualdi, R.F. Shanny, Hamiltonian line graphs, J. Graph Theory 5 (1981) 307-314], Clark [L. Clark, On hamitonian line graphs, J. Graph Theory 8 (1984) 303-307] and Veldman [H.J. Veldman, On dominating and spanning circuits in graphs, Discrete Math. 124 (1994) 229-239] gave minimum degree conditions of a line graph guaranteeing the line graph to be hamiltonian. In this paper, we investigate the similar conditions guaranteeing a line graph to be traceable. In particular, we show the following result: let G be a simple graph of order n and L (G) its line graph. If n is sufficiently large and, either δ (L (G)) > 2 ⌊ frac(n - 8, 4) ⌋; or δ (L (G)) > 2 ⌊ frac(n - 20, 10) ⌋ and G is almost bridgeless, then L (G) is traceable. As a byproduct, we also show that every 2-edge-connected triangle-free simple graph with order at most 9 has a spanning trail. These results are all best possible.

AB - Brualdi and Shanny [R.A. Brualdi, R.F. Shanny, Hamiltonian line graphs, J. Graph Theory 5 (1981) 307-314], Clark [L. Clark, On hamitonian line graphs, J. Graph Theory 8 (1984) 303-307] and Veldman [H.J. Veldman, On dominating and spanning circuits in graphs, Discrete Math. 124 (1994) 229-239] gave minimum degree conditions of a line graph guaranteeing the line graph to be hamiltonian. In this paper, we investigate the similar conditions guaranteeing a line graph to be traceable. In particular, we show the following result: let G be a simple graph of order n and L (G) its line graph. If n is sufficiently large and, either δ (L (G)) > 2 ⌊ frac(n - 8, 4) ⌋; or δ (L (G)) > 2 ⌊ frac(n - 20, 10) ⌋ and G is almost bridgeless, then L (G) is traceable. As a byproduct, we also show that every 2-edge-connected triangle-free simple graph with order at most 9 has a spanning trail. These results are all best possible.

KW - Degree sum of adjacent vertices

KW - Dominating trail

KW - Hamiltonian cycle(path)

KW - Line graph

KW - Spanning trail

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

U2 - 10.1016/j.disc.2008.10.012

DO - 10.1016/j.disc.2008.10.012

M3 - Article

AN - SCOPUS:67349093818

SN - 0012-365X

VL - 309

SP - 3779

EP - 3785

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 12

ER -

Traceability of line graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this