
arXiv: 2205.15840
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.
Correction in Section 6, and minor edits
lexicographic graph product, Cartesian graph prod-uct, k-independence number, Graph operations (line graphs, products, etc.), graph products, lexicographic graph prod-uct, tensor graph product, strong graph product, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Cartesian graph product, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, graph products, -independence number, Cartesian graph product, tensor graph product, strong graph product, lexicographic graph product, Combinatorics (math.CO), \(k\)-independence number, Mathematics
lexicographic graph product, Cartesian graph prod-uct, k-independence number, Graph operations (line graphs, products, etc.), graph products, lexicographic graph prod-uct, tensor graph product, strong graph product, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Cartesian graph product, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, graph products, -independence number, Cartesian graph product, tensor graph product, strong graph product, lexicographic graph product, Combinatorics (math.CO), \(k\)-independence number, Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
