Article in volume
Authors:
Aida Abiad
Department of Mathematics and Computer Science, Eindhoven University of
Technology, The Netherlands
Department of Mathematics: Analysis, Logic and Discrete Mathematics, Ghent
University, Belgium
Department of Mathematics and Data Science of Vrije Universiteit Brussel, Belgium
email: aidaabiad@gmail.com
Hidde Koerts
Department of Combinatorics and Optimization, University of Waterloo
email: hkoerts@uwaterloo.ca
Title:
On the $k$-independence number of graph products
PDFSource:
Discussiones Mathematicae Graph Theory 44(3) (2024) 983-996
Received: 2022-06-23 , Revised: 2022-11-30 , Accepted: 2022-11-30 , Available online: 2022-12-17 , https://doi.org/10.7151/dmgt.2480
Abstract:
The $k$-independence number of a graph, $\alpha_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
$\alpha_k(G)=\alpha(G^k)$, this, in general, does not hold for most graph
products, and thus the existing bounds for $\alpha$ 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
References:
- 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - P.K. Jha and S. Klavžar, Independence in direct-product graphs, Ars Combin. 50 (1998) 53–60.
- 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 - S. Klavžar, Some new bounds and exact results on the independence number of Cartesian product graphs, Ars Combin. 74 (2005) 173–186.
- M.C. Kong and Y. Zhao, On computing maximum $k$-independent sets, Congr. Numer. 95 (1993) 47–60.
- M.C. Kong and Y. Zhao, Computing $k$-independent sets for regular bipartite graphs, Congr. Numer. 143 (2000) 65–80.
- 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.
- 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 - 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 - 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 - 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 - 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 - 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 - V.G. Vizing, The Cartesian product of graphs, Vyčisl. Sistemy 9 (1963) 30–43.
- 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
Close