On the minimum vertex cover of generalized Petersen graphs

被引：2

作者：

Jin, Dannielle D. D. ^{[1
]}

Wang, David G. L. ^{[1
,2
]}

机构：

[1] Beijing Inst Technol, Sch Math & Stat, Beijing 102488, Peoples R China

[2] Beijing Inst Technol, Beijing Key Lab MCAACI, Beijing 102488, Peoples R China

来源：

DISCRETE APPLIED MATHEMATICS | 2019年 / 266卷

基金：

中国国家自然科学基金;

关键词：

Generalized Petersen graph; Independent set; Minimum vertex cover; I-GRAPHS; NUMBER; ENUMERATION;

D O I：

10.1016/j.dam.2018.12.011

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

It is known that any vertex cover of the generalized Petersen graph P(n, k) has size at least n. Behsaz, Hatami and Mahmoodian characterized such graphs with minimum vertex cover numbers n and n + 1, and those with k <= 3. For k >= 4 and n >= 2k + 2, we prove that if the 2-adic valuation of n is less than or equal to that of k, then the minimum vertex cover number of P(n, k) equals n + 2 if and only if n is an element of {2k + 2, 3k - 1, 3k + 1}. (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：309 / 318

页数：10

共 24 条

[1] THE CLASSIFICATION OF HAMILTONIAN GENERALIZED PETERSEN GRAPHS [J].

ALSPACH, B .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1983, 34 (03) :293-312

[2]

[Anonymous], 1993, The Petersen Graph

[3]

Behsaz B, 2008, AUSTRALAS J COMB, V40, P253

[4] On the domination number of the generalized Petersen graphs [J].

Behzad, Arash ;

Behzad, Mehdi ;

Praeger, Cheryl E. .

DISCRETE MATHEMATICS, 2008, 308 (04) :603-610

[5] I-graphs and the corresponding configurations [J].

Boben, M ;

Pisanski, T ;

Zitnik, A .

JOURNAL OF COMBINATORIAL DESIGNS, 2005, 13 (06) :406-424

[6] EVERY GENERALIZED PETERSEN GRAPH HAS A TAIT COLORING [J].

CASTAGNA, F ;

PRINS, G .

PACIFIC JOURNAL OF MATHEMATICS, 1972, 40 (01) :53-&

[7] SELF-DUAL CONFIGURATIONS AND REGULAR GRAPHS [J].

COXETER, HSM .

BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1950, 56 (05) :413-455

[8] On the odd girth and the circular chromatic number of generalized Petersen graphs [J].

Daneshgar, Amir ;

Madani, Meysam .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 33 (03) :897-923

[9] On the hardness of approximating minimum vertex cover [J].

Dinur, I ;

Safra, S .

ANNALS OF MATHEMATICS, 2005, 162 (01) :439-485

[10]

Fox J, 2012, ARS COMBINATORIA, V103, P439

← 1 2 3 →