Complexity results on k-independence in some graph products

被引：0

作者：

Cappelle, Marcia ^{[1
]}

Coelho, Erika ^{[1
]}

Mortosa, Otavio ^{[1
]}

Nascimento, Julliano ^{[1
]}

机构：

[1] Univ Fed Goias, Inst Informat, Goiania, Brazil

来源：

RAIRO-OPERATIONS RESEARCH | 2024年 / 58卷 / 03期

关键词：

Independence number; k-independent set; Cartesian product; complementary prism; DOMINATION NUMBER; COMPLEMENTARY;

D O I：

10.1051/ro/2024098

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

For a positive integer k, a subset S of vertices of a graph G is k-independent if each vertex in S has at most k - 1 neighbors in S. We consider k-independent sets in two graph products: Cartesian and complementary prism. We show that the problem of determining k-independence remains NP-complete even for Cartesian products and complementary prisms. Furthermore, we present results on k-independence in the Cartesian product of two paths, known as grid graphs.

引用

页码：2367 / 2378

页数：12

共 35 条

[1] Abay-Asmerom G., 2011, Discussiones Mathematicae Graph Theory, V31, P25
[2] Barbosa RM, 2018, ARS COMBINATORIA, V137, P283
[3] BERGE C., 1985, GRAPHS
[4] Blidia M., 2008, Discuss. Math, V28, P151
[5] Bondy J. A., 1976, Graph theory with applications
[6] On the independence graph of a graph
Bresar, B
Zmazek, B
[J]. DISCRETE MATHEMATICS, 2003, 272 (2-3) : 263 - 268
[7] Remarks on k-Clique, k-Independent Set and 2-Contamination in Complementary Prisms
Camargo, Priscila P.
Souza, Ueverton S.
Nascimento, Julliano R.
[J]. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2021, 32 (01) : 37 - 52
[8] Caro Y., 2012, Electron. J. Comb, P33
[9] Chellali M., 2010, Discuss. Math. Graph Theory, P265
[10] k-Domination and k-Independence in Graphs: A Survey
Chellali, Mustapha
Favaron, Odile
Hansberg, Adriana
Volkmann, Lutz
[J]. GRAPHS AND COMBINATORICS, 2012, 28 (01) : 1 - 55

← 1 2 3 4 →