Geodesic
On the $k$-independence number of graph products
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 983-996

Voir la notice de l'article provenant de la source Library of Science

The k-independence number of a graph, α_k(G), is the maximum size of a set of vertices at pairwise distance greater than k, or alternatively, the independence number of the k-th power graph G^k. Although it is known that α_k(G)=α(G^k), this, in general, does not hold for most graph products, and thus the existing bounds for α of graph products cannot be used. In this paper we present sharp upper bounds for the k-independence number of several graph products. In particular, we focus on the Cartesian, tensor, strong, and lexicographic products. Some of the bounds previously known in the literature for k=1 follow as corollaries of our main results.
Keywords: graph products, $k$-independence number, Cartesian graph product, tensor graph product, strong graph product, lexicographic graph product 
@article{DMGT_2024_44_3_a9,
     author = {Abiad, Aida and Koerts, Hidde},
     title = {On the $k$-independence number of graph products},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {983--996},
     publisher = {mathdoc},
     volume = {44},
     number = {3},
     year = {2024},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a9/}
}
TY  - JOUR
AU  - Abiad, Aida
AU  - Koerts, Hidde
TI  - On the $k$-independence number of graph products
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 983
EP  - 996
VL  - 44
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a9/
LA  - en
ID  - DMGT_2024_44_3_a9
ER  - 
%0 Journal Article
%A Abiad, Aida
%A Koerts, Hidde
%T On the $k$-independence number of graph products
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 983-996
%V 44
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a9/
%G en
%F DMGT_2024_44_3_a9
Abiad, Aida; Koerts, Hidde. On the $k$-independence number of graph products. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 983-996. http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a9/