SOME VARIATIONS OF PERFECT GRAPHS

被引：2

作者：

Dettlaff, Magda ^{[1
]}

Lemanska, Magdalena ^{[1
]}

Semanisin, Gabriel ^{[2
]}

Zuazua, Rita ^{[3
]}

机构：

[1] Gdansk Univ Technol, Fac Appl Phys & Math, Ul Narutowicza 11-12, PL-80233 Gdansk, Poland

[2] Safarik Univ, Inst Comp Sci, Jesenna 5, Kosice 04154, Slovakia

[3] Univ Nacl Autonoma Mexico, Fac Sci, Ave Univ 3000, Mexico City, DF, Mexico

来源：

DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2016年 / 36卷 / 03期

关键词：

k-path vertex cover; distance k-domination number; perfect graphs; DOMINATION;

D O I：

10.7151/dmgt.1880

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We consider (psi(k) - gamma(k-1))-perfect graphs, i.e., graphs G for which psi(k)(H) = gamma(k-1)(H) for any induced subgraph H of G, where psi(k) and gamma(k-1) are the k-path vertex cover number and the distance (k - 1) -domination number, respectively. We study (psi(k) - gamma(k-1))-perfect paths, cycles and complete graphs for k >= 2. Moreover, we provide a complete characterisation of (psi(2) - gamma(1))-perfect graphs describing the set of its forbidden induced subgraphs and providing the explicit characterisation of the structure of graphs belonging to this family.

引用

页码：661 / 668

页数：8

共 9 条

[1]

[Anonymous], 1961, Wissenschaftliche Zeitschrift

[2]

Brandstadt A., 1999, MONOGRAPHS DISCRETE, DOI [10.1137/1.9780898719796, DOI 10.1137/1.9780898719796]

[3] Minimum k-path vertex cover [J].

Bresar, Bostjan ;

Kardos, Frantisek ;

Katrenic, Jan ;

Semanisin, Gabriel .

DISCRETE APPLIED MATHEMATICS, 2011, 159 (12) :1189-1195

[4] On weakly connected domination in graphs II [J].

Domke, GS ;

Hattingh, JH ;

Markus, LR .

DISCRETE MATHEMATICS, 2005, 305 (1-3) :112-122

[5]

Haynes TW, 1998, Fundamentals of domination in graphs, V1st, DOI [DOI 10.1201/9781482246582, 10.1201/9781482246582]

[6]

Henning M.A., 1991, J. Combin. Inform. System Sci, V16, P11

[7]

HENNING MA, 1994, MATH PANNON, V5, P69

[8] ON GRAPHS WITH EQUAL DOMINATION AND COVERING NUMBERS [J].

VOLKMANN, L .

DISCRETE APPLIED MATHEMATICS, 1994, 51 (1-2) :211-217

[9]

Zverovich I. E., 2003, Discussiones Mathematicae Graph Theory, V23, P159, DOI 10.7151/dmgt.1192

← 1 →