Article in press
Authors:
Title:
Some results on the $k$-alliance and domination of graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-03-02 , Revised: 2024-10-04 , Accepted: 2024-10-12 , Available online: 2024-11-09 , https://doi.org/10.7151/dmgt.2568
Abstract:
For a graph $G$ of order $n$ and real number $a\geq-1$, let $\rho_{i}^{a}(G)$
be the $i$-th largest eigenvalue of $A_a(G):=aD(G)+A(G)$, where $A(G)$ and
$D(G)$ are the adjacency matrix and the diagonal degree matrix of $G$.
In this paper, we investigate connections of the eigenvalues of $A_a(G)$ to
the alliances and domination parameters of $G$ including defensive $k$-alliance
number, global offensive $k$-alliance number, total domination
number and signed domination number. Our results in this paper
provide a unified approach to study the alliances and domination in
a graph by its eigenvalues of associated matrices. We derive two
lower bounds for the defensive $k$-alliance number of $G$ based on
the parameter $\rho_{2}^{a}(G)$. Moreover, we establish a
lower bound for the global offensive $k$-alliance number of $G$ in
relation to $\rho_{n}^{a}(G)$. Additionally, we also deduce
the lower bounds for $\rho_{2}^{a}(G)$ based on its total and signed
domination numbers, as well as upper bounds for $\rho_{n}^{a}(G)$,
respectively. Those results generalize the corresponding
known results on $a=-1$ due to Fernau, Rodríguez-Velázquez and
Sigarreta (2004), Rodríguez-Velázquez, Yero and Sigarreta (2009)
and Shi, Kang and Wu (2010), respectively.
Keywords:
total (signed) domination number, defensive (global offensive) $k$-alliance number, eigenvalue, bound
References:
- AIM Minimum Rank–-Special Graphs Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (2008) 1628–1648.
https://doi.org/10.1016/j.laa.2007.10.009 - B. Brešar, M.G. Cornet, T. Dravec and M.A. Henning, Bounds on zero forcing using $($upper$)$ total domination and minimum degree, Bull. Malays. Math. Sci. Soc. 47 (2024) 143.
https://doi.org/10.1007/s40840-024-01744-x - A.E. Brouwer and W.H. Haemers, Spectra of Graphs (Springer, New York, NY, 2012).
https://doi.org/10.1007/978-1-4614-1939-6 - H.-Z. Chen, J. Li and W.C. Shiu, Some results on the $A_{\alpha}$-eigenvalues of a graph, Linear Multilinear Algebra 71 (2023) 2998–3012.
https://doi.org/10.1080/03081087.2022.2135676 - H.-Z. Chen, J. Li and S.-J. Xu, Spectral bounds for the zero forcing number of a graph, Discuss. Math. Graph Theory 44 (2024) 971–982.
https://doi.org/10.7151/dmgt.2482 - E.J. Cockayne, R.M. Dawes and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211–219.
https://doi.org/10.1002/net.3230100304 - D. Cvetković, P. Rowlinson and S. Simić, An Introduction to the Theory of Graph Spectra (Cambridge University Press, 2010).
https://doi.org/10.1017/CBO9780511801518 - F. Dong, J. Ge and Y. Yang, Upper bounds on the signed edge domination number of a graph, Discrete Math. 344 (2021) 112201.
https://doi.org/10.1016/j.disc.2020.112201 - J.E. Dunbar, S.T. Hedetniemi, M.A. Henning and P.J. Slater, Signed domination number of a graph, in: Graph Theory, Combinatorics, and Applications (John Wiley & Sons, New York, 1995) 311–322.
- O. Favaron, G. Fricke, W. Goddard, S.M. Hedetniemi, S.T. Hedetniemi, P. Kristiansen, R.C. Laskar and R.D. Skaggs, Offensive alliances in graphs, Discuss. Math. Graph Theory 24 (2004) 263–275.
https://doi.org/10.7151/dmgt.1230 - L. Feng, G. Yu and X.-D. Zhang, Spectral radius of graphs with given matching number, Linear Algebra Appl. 422 (2007) 133–138.
https://doi.org/10.1016/j.laa.2006.09.014 - H. Fernau, J.A. Rodríguez-Velázquez and J.M. Sigarreta, Offensive $r$-alliances in graphs, Discrete Appl. Math. 157 (2009) 177–182.
https://doi.org/10.1016/j.dam.2008.06.001 - C.D. Godsil and M.W. Newman, Eigenvalue bounds for independent sets, J. Combin. Theory Ser. B 98 (2008) 721–734.
https://doi.org/10.1016/j.jctb.2007.10.007 - W.H. Haemers, Hoffman's ratio bound, Linear Algebra Appl. 617 (2021) 215–219.
https://doi.org/10.1016/j.laa.2021.02.010 - J. Har, A note on Laplacian eigenvalues and domination, Linear Algebra Appl. 449 (2014) 115-118.
https://doi.org/10.1016/j.laa.2014.02.025 - J. Harant and S. Richter, A new eigenvalue bound for independent sets, Discrete Math. 338 (2015) 1763–1765.
https://doi.org/10.1016/j.disc.2014.12.008 - T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (CRC Press, Boca Raton, 1998).
https://doi.org/10.1201/9781482246582 - T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Topics in Domination in Graphs, Dev. Math. 64 (Springer, Cham, 2020).
https://doi.org/10.1007/978-3-030-51117-3 - M. A. Henning, Graphs with large total domination number, J. Graph Theory 35 (2000) 21–45.
https://doi.org/10.1002/1097-0118(200009)35:1<21::AID-JGT3>3.0.CO;2-F - T. Kalinowski, N. Kam\u{c}ev and B. Sudakov, The zero forcing number of graphs, SIAM J. Discrete Math. 33 (2019) 95–115.
https://doi.org/10.1137/17M1133051 - P. Kristiansen, S.M. Hedetniemi and S.T. Hedetniemi, Alliances in graphs, J. Combin. Math. Combin. Comput. 48 (2004) 157–177.
- R. Li, The $k$-domination number and bounds for the Laplacian eigenvalues of graphs, Util. Math. 79 (2009) 189–192.
https://utilitasmathematica.com/index.php/Index/article/view/631 - H. Liu and M. Lu, Bounds of signless Laplacian spectrum of graphs based on the $k$-domination number, Linear Algebra Appl. 440 (2014) 83–89.
https://doi.org/10.1016/j.laa.2013.10.020 - M. Lu, H. Liu and F. Tian, Bounds of Laplacian spectrum of graphs based on the domination number, Linear Algebra Appl. 402 (2005) 390–396.
https://doi.org/10.1016/j.laa.2005.01.006 - V. Nikiforov, Bounds on graph eigenvalues I, Linear Algebra Appl. 420 (2007) 667–671.
https://doi.org/10.1016/j.laa.2006.08.020 - J.A. Rodríguez-Velázquez and J.M. Sigarreta, Spectral study of alliances in graphs, Discuss. Math. Graph Theory 27 (2007) 143–157.
https://doi.org/10.7151/dmgt.1351 - J.A. Rodríguez-Velázquez, I.G. Yero and J.M. Sigarreta, Defensive $k$-alliances in graphs, Appl. Math. Lett. 22 (2009) 96–100.
https://doi.org/10.1016/j.aml.2008.02.012 - W. Shi, L. Kang and S. Wu, Bounds on Laplacian eigenvalues related to total and signed domination of graphs, Czechoslovak Math. J. 60 (2010) 315–325.
https://doi.org/10.1007/s10587-010-0035-1 - J.M. Sigarreta, S. Bermudo and H. Fernau, On the complement graph and defensive $k$-alliances, Discrete Appl. Math. 157 (2009) 1687–1695.
https://doi.org/10.1016/j.dam.2008.12.006 - E. Vatandoost and F. Ramezani, On the domination and signed domination numbers of zero-divisor graph, Electron. J. Graph Theory Appl. (EJGTA) 4 (2016) 148–156.
https://doi.org/10.5614/ejgta.2016.4.2.3 - W. Zhang, The maximum spectral radius of $t$-connected graphs with bounded matching number, Discrete Math. 345 (2022) 112775.
https://doi.org/10.1016/j.disc.2021.112775 - W. Zhang, J. Wang, W. Wang and S. Ji, On the zero forcing number and spectral radius of graphs, Electron. J. Combin. 29 (2022) #P1.33.
https://doi.org/10.37236/10638
Close