The maximum size of a nonhamiltonian graph with given order and connectivity

Xingzhi Zhan; Leilei Zhang

doi:10.1016/j.disc.2022.113208

The maximum size of a nonhamiltonian graph with given order and connectivity

Xingzhi Zhan
, Leilei Zhang^*

^*此作品的通讯作者

数学科学学院

East China Normal University

科研成果: 期刊稿件 › 文章 › 同行评审

摘要

Motivated by work of Erdős, Ota determined the maximum size g(n,k) of a k-connected nonhamiltonian graph of order n in 1995. But for some pairs n,k, the maximum size is not attained by a graph of connectivity k. For example, g(15,3)=77 is attained by a unique graph of connectivity 7, not 3. In this paper we obtain more precise information by determining the maximum size of a nonhamiltonian graph of order n and connectivity k, and determining the extremal graphs. Consequently we solve the corresponding problem for nontraceable graphs.

源语言	英语
期刊论文编号	113208
期刊	Discrete Mathematics
卷	346
期	1
DOI	https://doi.org/10.1016/j.disc.2022.113208
出版状态	已出版 - 1月 2023

访问文件

10.1016/j.disc.2022.113208

其它文件与链接

链接到 Scopus 的出版物

引用此

@article{ab5aa4ac12da4e918d64b50f6b917d37,

title = "The maximum size of a nonhamiltonian graph with given order and connectivity",

abstract = "Motivated by work of Erd{\H o}s, Ota determined the maximum size g(n,k) of a k-connected nonhamiltonian graph of order n in 1995. But for some pairs n,k, the maximum size is not attained by a graph of connectivity k. For example, g(15,3)=77 is attained by a unique graph of connectivity 7, not 3. In this paper we obtain more precise information by determining the maximum size of a nonhamiltonian graph of order n and connectivity k, and determining the extremal graphs. Consequently we solve the corresponding problem for nontraceable graphs.",

keywords = "Connectivity, Extremal graph, Hamiltonian graph, Size, Traceable graph",

author = "Xingzhi Zhan and Leilei Zhang",

note = "Publisher Copyright: {\textcopyright} 2022 Elsevier B.V.",

year = "2023",

month = jan,

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

language = "英语",

volume = "346",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - The maximum size of a nonhamiltonian graph with given order and connectivity

AU - Zhan, Xingzhi

AU - Zhang, Leilei

PY - 2023/1

Y1 - 2023/1

N2 - Motivated by work of Erdős, Ota determined the maximum size g(n,k) of a k-connected nonhamiltonian graph of order n in 1995. But for some pairs n,k, the maximum size is not attained by a graph of connectivity k. For example, g(15,3)=77 is attained by a unique graph of connectivity 7, not 3. In this paper we obtain more precise information by determining the maximum size of a nonhamiltonian graph of order n and connectivity k, and determining the extremal graphs. Consequently we solve the corresponding problem for nontraceable graphs.

AB - Motivated by work of Erdős, Ota determined the maximum size g(n,k) of a k-connected nonhamiltonian graph of order n in 1995. But for some pairs n,k, the maximum size is not attained by a graph of connectivity k. For example, g(15,3)=77 is attained by a unique graph of connectivity 7, not 3. In this paper we obtain more precise information by determining the maximum size of a nonhamiltonian graph of order n and connectivity k, and determining the extremal graphs. Consequently we solve the corresponding problem for nontraceable graphs.

KW - Connectivity

KW - Extremal graph

KW - Hamiltonian graph

KW - Size

KW - Traceable graph

UR - https://www.scopus.com/pages/publications/85139362640

U2 - 10.1016/j.disc.2022.113208

DO - 10.1016/j.disc.2022.113208

M3 - 文章

AN - SCOPUS:85139362640

SN - 0012-365X

VL - 346

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1

M1 - 113208

ER -

The maximum size of a nonhamiltonian graph with given order and connectivity

摘要

访问文件

其它文件与链接

学术指纹

引用此