TY - JOUR
T1 - A bound for the p-domination number of a graph in terms of its eigenvalue multiplicities
AU - Abiad, A.
AU - Akbari, S.
AU - Fakharan, M.H.
AU - Mehdizadeh, A.
N1 - Funding Information:
S. Akbari is partially funded by the Iran National Science Foundation (INSF), grant 96004167 .
Funding Information:
A. Abiad is partially funded by the Fonds Wetenschappelijk Onderzoek (FWO), grant 1285921N .
PY - 2023/2/1
Y1 - 2023/2/1
N2 - Let G be a connected graph of order n with domination number γ(G). Wang, Yan, Fang, Geng and Tian [Linear Algebra Appl. 607 (2020), 307-318] showed that for any Laplacian eigenvalue λ of G with multiplicity mG(λ), it holds that γ(G)≤n−mG(λ). Using techniques from the theory of star sets, in this work we prove that the same bound holds when λ is an arbitrary adjacency eigenvalue of a non-regular graph, and we characterize the cases of equality. Moreover, we show a result that gives a relationship between start sets and the p-domination number, and we apply it to extend the aforementioned spectral bound to the p-domination number using the adjacency and Laplacian eigenvalue multiplicities.
AB - Let G be a connected graph of order n with domination number γ(G). Wang, Yan, Fang, Geng and Tian [Linear Algebra Appl. 607 (2020), 307-318] showed that for any Laplacian eigenvalue λ of G with multiplicity mG(λ), it holds that γ(G)≤n−mG(λ). Using techniques from the theory of star sets, in this work we prove that the same bound holds when λ is an arbitrary adjacency eigenvalue of a non-regular graph, and we characterize the cases of equality. Moreover, we show a result that gives a relationship between start sets and the p-domination number, and we apply it to extend the aforementioned spectral bound to the p-domination number using the adjacency and Laplacian eigenvalue multiplicities.
KW - Adjacency matrix
KW - Eigenvalue multiplicity
KW - Laplacian matrix
KW - p-domination number
KW - Rank
KW - Total domination number
UR - http://www.scopus.com/inward/record.url?scp=85142444162&partnerID=8YFLogxK
U2 - 10.1016/j.laa.2022.11.008
DO - 10.1016/j.laa.2022.11.008
M3 - Article
AN - SCOPUS:85142444162
SN - 0024-3795
VL - 658
SP - 319
EP - 330
JO - Linear Algebra and Its Applications
JF - Linear Algebra and Its Applications
ER -