Large degree vertices in longest cycles of graphs, II

被引：2

作者：

Li, Binlong ^{[1
]}

Xiong, Liming ^{[2
,3
]}

Yin, Jun ^{[4
]}

机构：

[1] Northwestern Polytech Univ, Dept Appl Math, 0, Xian 710072, Shaanxi, Peoples R China

[2] Beijing Inst Technol, Sch Math & Stat, Beijing 100081, Peoples R China

[3] Beijing Inst Technol, Beijing Key Lab MCAACI, Beijing 100081, Peoples R China

[4] Qinghai Normal Univ, Sch Comp Sci, Xining 810008, Qinghai, Peoples R China

来源：

ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS | 2019年 / 7卷 / 02期

关键词：

longest cycle; connectivity; independent number; large degree vertex;

D O I：

10.5614/ejgta.2019.7.2.7

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper, we consider the least integer d such that every k-connected graph G of order n (and of independent number alpha) has a longest cycle containing all vertices of degree at least d. We completely determine the d when k = 2. We propose a conjecture for those k-connected graph, where k >= 3.

引用

页码：277 / 299

页数：23

共 14 条

[1] CYCLES THROUGH SPECIFIED VERTICES
BOLLOBAS, B
BRIGHTWELL, G
[J]. COMBINATORICA, 1993, 13 (02) : 147 - 155
[2] Bondy J.A., 2008, GTM
[3] METHOD IN GRAPH THEORY
BONDY, JA
CHVATAL, V
[J]. DISCRETE MATHEMATICS, 1976, 15 (02) : 111 - 135
[4] Chvatal V., 1972, Discrete Math, V2, P111, DOI DOI 10.1016/0012-365X(72)90079-9
[5] Dirac G. A., 1952, Proc. London Math. Soc, V3, P69, DOI DOI 10.1112/PLMS/S3-2.1.69
[6] On cycles through a given vertex in multipartite tournaments
Guo, YB
Pinkernell, A
Volkmann, L
[J]. DISCRETE MATHEMATICS, 1997, 164 (1-3) : 165 - 170
[7] Harant J., 2008, DISCUSS MATH GRAPH T, V28, P441
[8] LARGE DEGREE VERTICES IN LONGEST CYCLES OF GRAPHS, I
Li, Binlong
Xiong, Liming
Yin, Jun
[J]. DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2016, 36 (02) : 363 - 382
[9] Forbidden subgraphs for longest cycles to contain vertices with large degrees
Li, Binlong
Zhang, Shenggui
[J]. DISCRETE MATHEMATICS, 2015, 338 (10) : 1681 - 1689
[10] Li BL, 2013, ELECTRON J GRAPH THE, V1, P1

← 1 2 →