Hamiltonian Extendable Graphs

Xiaojing Yang; Liming Xiong

doi:10.7151/dmgt.2308

Hamiltonian Extendable Graphs

Xiaojing Yang, Liming Xiong

School of Mathematics and Statistics

Beijing Institute of Technology

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

Abstract

A graph is called Hamiltonian extendable if there exists a Hamiltonian path between any two nonadjacent vertices. In this paper, we give an explicit formula of the minimum number of edges for Hamiltonian extendable graphs and we also characterize the degree sequence for Hamiltonian extendable graphs with minimum number of edges. Besides, we completely characterize the pairs of forbidden subgraphs for 2-connected graphs to be Hamiltonian extendable.

Original language	English
Pages (from-to)	843-859
Number of pages	17
Journal	Discussiones Mathematicae - Graph Theory
Volume	42
Issue number	3
DOIs	https://doi.org/10.7151/dmgt.2308
Publication status	Published - 1 Aug 2022

Keywords

Hamiltonian extendable
forbidden subgraph

Access to Document

10.7151/dmgt.2308

Cite this

@article{8134e63c69204324b65ae3d6e2734275,

title = "Hamiltonian Extendable Graphs",

abstract = "A graph is called Hamiltonian extendable if there exists a Hamiltonian path between any two nonadjacent vertices. In this paper, we give an explicit formula of the minimum number of edges for Hamiltonian extendable graphs and we also characterize the degree sequence for Hamiltonian extendable graphs with minimum number of edges. Besides, we completely characterize the pairs of forbidden subgraphs for 2-connected graphs to be Hamiltonian extendable.",

keywords = "Hamiltonian extendable, forbidden subgraph",

author = "Xiaojing Yang and Liming Xiong",

note = "Publisher Copyright: {\textcopyright} 2020 Xiaojing Yang et al.",

year = "2022",

month = aug,

day = "1",

doi = "10.7151/dmgt.2308",

language = "English",

volume = "42",

pages = "843--859",

journal = "Discussiones Mathematicae - Graph Theory",

issn = "1234-3099",

publisher = "University of Zielona Gora",

number = "3",

}

TY - JOUR

T1 - Hamiltonian Extendable Graphs

AU - Yang, Xiaojing

AU - Xiong, Liming

PY - 2022/8/1

Y1 - 2022/8/1

N2 - A graph is called Hamiltonian extendable if there exists a Hamiltonian path between any two nonadjacent vertices. In this paper, we give an explicit formula of the minimum number of edges for Hamiltonian extendable graphs and we also characterize the degree sequence for Hamiltonian extendable graphs with minimum number of edges. Besides, we completely characterize the pairs of forbidden subgraphs for 2-connected graphs to be Hamiltonian extendable.

AB - A graph is called Hamiltonian extendable if there exists a Hamiltonian path between any two nonadjacent vertices. In this paper, we give an explicit formula of the minimum number of edges for Hamiltonian extendable graphs and we also characterize the degree sequence for Hamiltonian extendable graphs with minimum number of edges. Besides, we completely characterize the pairs of forbidden subgraphs for 2-connected graphs to be Hamiltonian extendable.

KW - Hamiltonian extendable

KW - forbidden subgraph

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

U2 - 10.7151/dmgt.2308

DO - 10.7151/dmgt.2308

M3 - Article

AN - SCOPUS:85083050710

SN - 1234-3099

VL - 42

SP - 843

EP - 859

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

IS - 3

ER -

Hamiltonian Extendable Graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this