Degree sums and subpancyclicity in line graphs

Liming Xiong; H. J. Broersma; C. Hoede; Xueliang Li

doi:10.1016/S0012-365X(00)00468-4

Degree sums and subpancyclicity in line graphs

Liming Xiong, H. J. Broersma, C. Hoede, Xueliang Li

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

2 Citations (Scopus)

Abstract

A graph is called subpancyclic if it contains a cycle of length k for each k between 3 and the circumference of the graph. In this paper, we show that if the degree sum of the vertices along each 2-path of a graph G exceeds (n + 6)/2, or if the degree sum of the vertices along each 3-path of G exceeds (2n + 16)/3, then its line graph L(G) is subpancyclic. Simple examples show that these bounds are best possible. Our results shed some light on the content of a famous Metaconjecture of Bondy.

Original language	English
Pages (from-to)	255-267
Number of pages	13
Journal	Discrete Mathematics
Volume	242
Issue number	1-3
DOIs	https://doi.org/10.1016/S0012-365X(00)00468-4
Publication status	Published - 1 Jun 2002
Externally published	Yes

Keywords

Degree sum
Line graph
Path
Subpancyclicity

Access to Document

10.1016/S0012-365X(00)00468-4

Cite this

@article{ce2024edb35e415196f2d69ee2235b59,

title = "Degree sums and subpancyclicity in line graphs",

abstract = "A graph is called subpancyclic if it contains a cycle of length k for each k between 3 and the circumference of the graph. In this paper, we show that if the degree sum of the vertices along each 2-path of a graph G exceeds (n + 6)/2, or if the degree sum of the vertices along each 3-path of G exceeds (2n + 16)/3, then its line graph L(G) is subpancyclic. Simple examples show that these bounds are best possible. Our results shed some light on the content of a famous Metaconjecture of Bondy.",

keywords = "Degree sum, Line graph, Path, Subpancyclicity",

author = "Liming Xiong and Broersma, {H. J.} and C. Hoede and Xueliang Li",

year = "2002",

month = jun,

day = "1",

doi = "10.1016/S0012-365X(00)00468-4",

language = "English",

volume = "242",

pages = "255--267",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Degree sums and subpancyclicity in line graphs

AU - Xiong, Liming

AU - Broersma, H. J.

AU - Hoede, C.

AU - Li, Xueliang

PY - 2002/6/1

Y1 - 2002/6/1

N2 - A graph is called subpancyclic if it contains a cycle of length k for each k between 3 and the circumference of the graph. In this paper, we show that if the degree sum of the vertices along each 2-path of a graph G exceeds (n + 6)/2, or if the degree sum of the vertices along each 3-path of G exceeds (2n + 16)/3, then its line graph L(G) is subpancyclic. Simple examples show that these bounds are best possible. Our results shed some light on the content of a famous Metaconjecture of Bondy.

AB - A graph is called subpancyclic if it contains a cycle of length k for each k between 3 and the circumference of the graph. In this paper, we show that if the degree sum of the vertices along each 2-path of a graph G exceeds (n + 6)/2, or if the degree sum of the vertices along each 3-path of G exceeds (2n + 16)/3, then its line graph L(G) is subpancyclic. Simple examples show that these bounds are best possible. Our results shed some light on the content of a famous Metaconjecture of Bondy.

KW - Degree sum

KW - Line graph

KW - Path

KW - Subpancyclicity

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

U2 - 10.1016/S0012-365X(00)00468-4

DO - 10.1016/S0012-365X(00)00468-4

M3 - Article

AN - SCOPUS:33646070633

SN - 0012-365X

VL - 242

SP - 255

EP - 267

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Degree sums and subpancyclicity in line graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this