Edge Degree Conditions for 2-Iterated Line Graphs to Be Traceable

Yingmin Shangguan; Monica Mengyu Wang; Liming Xiong

doi:10.3390/axioms11100540

Edge Degree Conditions for 2-Iterated Line Graphs to Be Traceable

Yingmin Shangguan, Monica Mengyu Wang, Liming Xiong^*

^*Corresponding author for this work

School of Mathematics and Statistics

Beijing Institute of Technology

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

Abstract

The line graph (Formula presented.) of G has (Formula presented.) as its vertex set, and two vertices are adjacent in (Formula presented.) if and only if the corresponding edges share a common end vertex in G. Let (Formula presented.). We show that, if (Formula presented.) and n is sufficiently large, then either (Formula presented.) is traceable or the Veldman’s reduction (Formula presented.) is one of well-defined classes of exceptional graphs. Furthermore, if (Formula presented.) and n is sufficiently large, then (Formula presented.) is traceable. The bound (Formula presented.) is sharp. As a byproduct, we characterize the structure of a connected graph with a non-traceable 2-iterated line graph.

Original language	English
Article number	540
Journal	Axioms
Volume	11
Issue number	10
DOIs	https://doi.org/10.3390/axioms11100540
Publication status	Published - Oct 2022

Keywords

edge degree conditions
hamilton path
iterated line graph

Access to Document

10.3390/axioms11100540

Cite this

@article{eb5f45f3d62246728d91b1a3ea5858de,

title = "Edge Degree Conditions for 2-Iterated Line Graphs to Be Traceable",

abstract = "The line graph (Formula presented.) of G has (Formula presented.) as its vertex set, and two vertices are adjacent in (Formula presented.) if and only if the corresponding edges share a common end vertex in G. Let (Formula presented.). We show that, if (Formula presented.) and n is sufficiently large, then either (Formula presented.) is traceable or the Veldman{\textquoteright}s reduction (Formula presented.) is one of well-defined classes of exceptional graphs. Furthermore, if (Formula presented.) and n is sufficiently large, then (Formula presented.) is traceable. The bound (Formula presented.) is sharp. As a byproduct, we characterize the structure of a connected graph with a non-traceable 2-iterated line graph.",

keywords = "edge degree conditions, hamilton path, iterated line graph",

author = "Yingmin Shangguan and Wang, {Monica Mengyu} and Liming Xiong",

note = "Publisher Copyright: {\textcopyright} 2022 by the authors.",

year = "2022",

month = oct,

doi = "10.3390/axioms11100540",

language = "English",

volume = "11",

journal = "Axioms",

issn = "2075-1680",

publisher = "Multidisciplinary Digital Publishing Institute (MDPI)",

number = "10",

}

TY - JOUR

T1 - Edge Degree Conditions for 2-Iterated Line Graphs to Be Traceable

AU - Shangguan, Yingmin

AU - Wang, Monica Mengyu

AU - Xiong, Liming

PY - 2022/10

Y1 - 2022/10

N2 - The line graph (Formula presented.) of G has (Formula presented.) as its vertex set, and two vertices are adjacent in (Formula presented.) if and only if the corresponding edges share a common end vertex in G. Let (Formula presented.). We show that, if (Formula presented.) and n is sufficiently large, then either (Formula presented.) is traceable or the Veldman’s reduction (Formula presented.) is one of well-defined classes of exceptional graphs. Furthermore, if (Formula presented.) and n is sufficiently large, then (Formula presented.) is traceable. The bound (Formula presented.) is sharp. As a byproduct, we characterize the structure of a connected graph with a non-traceable 2-iterated line graph.

AB - The line graph (Formula presented.) of G has (Formula presented.) as its vertex set, and two vertices are adjacent in (Formula presented.) if and only if the corresponding edges share a common end vertex in G. Let (Formula presented.). We show that, if (Formula presented.) and n is sufficiently large, then either (Formula presented.) is traceable or the Veldman’s reduction (Formula presented.) is one of well-defined classes of exceptional graphs. Furthermore, if (Formula presented.) and n is sufficiently large, then (Formula presented.) is traceable. The bound (Formula presented.) is sharp. As a byproduct, we characterize the structure of a connected graph with a non-traceable 2-iterated line graph.

KW - edge degree conditions

KW - hamilton path

KW - iterated line graph

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

U2 - 10.3390/axioms11100540

DO - 10.3390/axioms11100540

M3 - Article

AN - SCOPUS:85140407040

SN - 2075-1680

VL - 11

JO - Axioms

JF - Axioms

IS - 10

M1 - 540

ER -

Edge Degree Conditions for 2-Iterated Line Graphs to Be Traceable

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this