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

被引：0

作者：

Zhan, Xingzhi ^{[1
]}

Zhang, Leilei ^{[1
]}

机构：

[1] East China Normal Univ, Dept Math, Shanghai 200241, Peoples R China

来源：

DISCRETE MATHEMATICS | 2023年 / 346卷 / 01期

关键词：

Connectivity; Hamiltonian graph; Traceable graph; Size; Extremal graph;

D O I：

10.1016/j.disc.2022.113208

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Motivated by work of Erdos, 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.(c) 2022 Elsevier B.V. All rights reserved.

引用

页数：8

共 10 条

[1] [Anonymous], 1972, J. Combin. Theory, DOI DOI 10.1016/0095-8956(72)90020-2
[2] Bondy J.A., 1969, STUDIA SCI MATH HUNG, P473
[3] Bondy J.A., 2008, GRADUATE TEXTS MATH, V244, DOI DOI 10.1007/978-1-84628-970-5
[4] VARIATIONS ON HAMILTONIAN THEME
BONDY, JA
[J]. CANADIAN MATHEMATICAL BULLETIN, 1972, 15 (01): : 57 - &
[5] Chvatal V., 1972, DISCRETE MATH, V2, P111, DOI DOI 10.1016/0012-365X(72)90079-9
[6] Erdos P., 1962, PUBL MATH I HUNGER A, V7, P227
[7] Sufficient spectral conditions on Hamiltonian and traceable graphs
Liu, Ruifang
Shiu, Wai Chee
Xue, Jie
[J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2015, 467 : 254 - 266
[8] Ore O., 1961, Ann. Mat. Pura Appl., V55, P315
[9] CYCLES THROUGH PRESCRIBED VERTICES WITH LARGE DEGREE SUM
OTA, K
[J]. DISCRETE MATHEMATICS, 1995, 145 (1-3) : 201 - 210
[10] West D. B., 2001, INTRO GRAPH THEORY

← 1 →