Geodesic
On the $k$-independence number of graph products
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 983-996 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2024},
     volume = {44},
     number = {3},
     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
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
%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/

[1] A. Abiad, S.M. Cioabă and M. Tait, Spectral bounds for the k-independence number of a graph, Linear Algebra Appl. 510 (2016) 160–170. https://doi.org/10.1016/j.laa.2016.08.024

[2] A. Abiad, G. Coutinho and M.A. Fiol, On the k-independence number of graphs, Discrete Math. 342 (2019) 2875–2885. https://doi.org/10.1016/j.disc.2019.01.016

[3] A. Abiad, G. Coutinho, M.A. Fiol, B.D. Nogueira and S. Zeijlemaker, Optimization of eigenvalue bounds for the independence and chromatic number of graph powers, Discrete Math. 345 (2022) 112706. https://doi.org/10.1016/j.disc.2021.112706

[4] G. Atkinson and A. Frieze, On the b-independence number of sparse random graphs, Combin. Probab. Comput. 13 (2004) 295-309. https://doi.org/10.1017/S0963548304006108

[5] M. Basavaraju, L.S. Chandran, D. Rajendraprasad and A. Ramaswamy, Rainbow connection number of graph power and graph products, Graphs Combin. 30 (2014) 1363–1382. https://doi.org/10.1007/s00373-013-1355-3

[6] M. Beis, W. Duckworth and M. Zito, Large k-independent sets of regular graphs, Electron. Notes Discrete Math. 19 (2005) 321–327. https://doi.org/10.1016/j.endm.2005.05.043

[7] K.Ch. Das and J.-M. Guo, Laplacian eigenvalues of the second power of a graph, Discrete Math. 313 (2013) 626–634. https://doi.org/10.1016/j.disc.2012.12.009

[8] M. DeVos, J. McDonald and D. Scheide, Average degree in graph powers, J. Graph Theory 72 (2013) 7–18. https://doi.org/10.1002/jgt.21628

[9] W. Duckworth and M. Zito, Large 2-independent sets of regular graphs, Electron. Notes Theor. Comput. Sci. 78 (2003) 223-235. https://doi.org/10.1016/S1571-0661(04)81015-6

[10] M.A. Fiol, A new class of polynomials from the spectrum of a graph, and its application to bound the k-independence number, Linear Algebra Appl. 605 (2020) 1–20. https://doi.org/10.1016/j.laa.2020.07.009

[11] P. Firby and J. Haviland, Independence and average distance in graphs, Discrete Appl. Math. 75 (1997) 27–37. https://doi.org/10.1016/S0166-218X(96)00078-9

[12] D. Geller and S. Stahl, The chromatic number and other functions of the lexicographic product, J. Combin. Theory Ser. B 19 (1975) 87–95. https://doi.org/10.1016/0095-8956(75)90076-3

[13] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Second Edition (Boca Raton, CRC Press, Inc., 2011). https://doi.org/10.1201/b10959

[14] M. Hota, M. Pal and T.K. Pal, An efficient algorithm for finding a maximum weight k-independent set on trapezoid graphs, Comput. Optim. Appl. 18 (2001) 49–62. https://doi.org/10.1023/A:1008791627588

[15] P.K. Jha and S. Klavžar, Independence in direct-product graphs, Ars Combin. 50 (1998) 53–60.

[16] P.K. Jha and G. Slutzki, Independence numbers of product graphs, Appl. Math. Lett. 7 (1994) 91–94. https://doi.org/10.1016/0893-9659(94)90018-3

[17] S. Klavžar, Some new bounds and exact results on the independence number of Cartesian product graphs, Ars Combin. 74 (2005) 173–186.

[18] M.C. Kong and Y. Zhao, On computing maximum k-independent sets, Congr. Numer. 95 (1993) 47–60.

[19] M.C. Kong and Y. Zhao, Computing k-independent sets for regular bipartite graphs, Congr. Numer. 143 (2000) 65–80.

[20] F. Kramer and H. Kramer, Un probleme de coloration des sommets d'un graphe, C.R. Acad. Sci. Paris, Ser. A 268 (1969) 46–48.

[21] F. Kramer and H. Kramer, Ein Färbungsproblem der Knotenpunkte eines Graphen bezüglich der Distanz p, Rev. Roumaine Math. Pures Appl. 14 (1969) 1031–1038. https://doi.org/10.13140/RG.2.2.24729.83047

[22] F. Kramer and H. Kramer, A survey on the distance-colouring of graphs, Discrete Math. 308 (2008) 422–426. https://doi.org/10.1016/j.disc.2006.11.059

[23] Z. Li and B. Wu, The k-independence number of t-connected graphs, Appl. Math. Comput. 409 (2021) 126412. https://doi.org/10.1016/j.amc.2021.126412

[24] S. O, Y. Shi and Z. Taoqiu, Sharp upper bounds on the k-independence number in graphs with given minimum and maximum degree, Graphs Combin. 37 (2021) 393–408. https://doi.org/10.1007/s00373-020-02244-y

[25] E. Sonnemann and O. Krafft, Independence numbers of product graphs, J. Combin. Theory Ser. B 17 (1974) 133–142. https://doi.org/10.1016/0095-8956(74)90081-1

[26] S. Špacapan, The k-independence number of direct products of graphs and Hedetniemi's conjecture, European J. Combin. 32 (2011) 1377–1383. https://doi.org/10.1016/j.ejc.2011.07.002

[27] V.G. Vizing, The Cartesian product of graphs, Vyčisl. Sistemy 9 (1963) 30–43.

[28] P. Wocjan, C. Elphick and A. Abiad, Spectral upper bound on the quantum k-independence number of a graph, Electron. J. Linear Algebra 38 (2022) 331–338. https://doi.org/10.13001/ela.2022.6675