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

^*Corresponding author for this work

Discrete Mathematics and Mathematical Programming

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

2 Citations (Scopus)

123 Downloads (Pure)

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 - 2002

Keywords

Line graph
Path
Subpancyclicity
Degree sum

Access to Document

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

Xiong2002degreeFinal published version, 114 KBLicence: Other

Cite this

@article{532ac29278364a9ea0817c3af5f28a27,

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 = "Line graph, Path, Subpancyclicity, Degree sum",

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

year = "2002",

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

language = "English",

volume = "242",

pages = "255--267",

journal = "Discrete mathematics",

issn = "0012-365X",

publisher = "Elsevier",

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

Y1 - 2002

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 - Line graph

KW - Path

KW - Subpancyclicity

KW - Degree sum

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

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

M3 - Article

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

Fingerprint

Cite this