Radius and subpancyclicity in line graphs

Liming Xiong; Qiuxin Wu; Ming Chu Li

doi:10.1016/j.disc.2007.09.050

Radius and subpancyclicity in line graphs

Liming Xiong, Qiuxin Wu, Ming Chu Li^*

^*Corresponding author for this work

School of Mathematics and Statistics

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

1 Citation (Scopus)

Abstract

A graph is called subpancyclic if it contains cycles of length from 3 to its circumference. Let G be a graph with min {d (u) + d (v) : u v ∈ E (G)} ≥ 8. In this paper, we prove that if one of the following holds: the radius of G is at most ⌊ frac(Δ (G), 2) ⌋; G has no subgraph isomorphic to Y_{Δ (G) + 2}; the circumference of G is at most Δ (G) + 1; the length of a longest path is at most Δ (G) + 1, then the line graph L (G) is subpancyclic and these conditions are all best possible even under the condition that L (G) is hamiltonian.

Original language	English
Pages (from-to)	5325-5333
Number of pages	9
Journal	Discrete Mathematics
Volume	308
Issue number	23
DOIs	https://doi.org/10.1016/j.disc.2007.09.050
Publication status	Published - 6 Dec 2008

Keywords

(sub)pancyclic graph
Diameter
Line graph
Maximum degree
Radius

Access to Document

10.1016/j.disc.2007.09.050

Cite this

@article{b8bedb1b17a14f93bb9ba1363ef5dc61,

title = "Radius and subpancyclicity in line graphs",

abstract = "A graph is called subpancyclic if it contains cycles of length from 3 to its circumference. Let G be a graph with min \{d (u) + d (v) : u v ∈ E (G)\} ≥ 8. In this paper, we prove that if one of the following holds: the radius of G is at most ⌊ frac(Δ (G), 2) ⌋; G has no subgraph isomorphic to YΔ (G) + 2; the circumference of G is at most Δ (G) + 1; the length of a longest path is at most Δ (G) + 1, then the line graph L (G) is subpancyclic and these conditions are all best possible even under the condition that L (G) is hamiltonian.",

keywords = "(sub)pancyclic graph, Diameter, Line graph, Maximum degree, Radius",

author = "Liming Xiong and Qiuxin Wu and Li, \{Ming Chu\}",

year = "2008",

month = dec,

day = "6",

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

language = "English",

volume = "308",

pages = "5325--5333",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "23",

}

TY - JOUR

T1 - Radius and subpancyclicity in line graphs

AU - Xiong, Liming

AU - Wu, Qiuxin

AU - Li, Ming Chu

PY - 2008/12/6

Y1 - 2008/12/6

N2 - A graph is called subpancyclic if it contains cycles of length from 3 to its circumference. Let G be a graph with min {d (u) + d (v) : u v ∈ E (G)} ≥ 8. In this paper, we prove that if one of the following holds: the radius of G is at most ⌊ frac(Δ (G), 2) ⌋; G has no subgraph isomorphic to YΔ (G) + 2; the circumference of G is at most Δ (G) + 1; the length of a longest path is at most Δ (G) + 1, then the line graph L (G) is subpancyclic and these conditions are all best possible even under the condition that L (G) is hamiltonian.

AB - A graph is called subpancyclic if it contains cycles of length from 3 to its circumference. Let G be a graph with min {d (u) + d (v) : u v ∈ E (G)} ≥ 8. In this paper, we prove that if one of the following holds: the radius of G is at most ⌊ frac(Δ (G), 2) ⌋; G has no subgraph isomorphic to YΔ (G) + 2; the circumference of G is at most Δ (G) + 1; the length of a longest path is at most Δ (G) + 1, then the line graph L (G) is subpancyclic and these conditions are all best possible even under the condition that L (G) is hamiltonian.

KW - (sub)pancyclic graph

KW - Diameter

KW - Line graph

KW - Maximum degree

KW - Radius

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

U2 - 10.1016/j.disc.2007.09.050

DO - 10.1016/j.disc.2007.09.050

M3 - Article

AN - SCOPUS:53049093308

SN - 0012-365X

VL - 308

SP - 5325

EP - 5333

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 23

ER -

Radius and subpancyclicity in line graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this