A bound for the p-domination number of a graph in terms of its eigenvalue multiplicities

A. Abiad; S. Akbari; M.H. Fakharan; A. Mehdizadeh

doi:10.1016/j.laa.2022.11.008

A bound for the p-domination number of a graph in terms of its eigenvalue multiplicities

A. Abiad (Corresponding author), S. Akbari, M.H. Fakharan, A. Mehdizadeh

Research output: Contribution to journal › Article › Academic › peer-review

69 Downloads (Pure)

Abstract

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 m_G(λ), it holds that γ(G)≤n−m_G(λ). 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.

Original language	English
Pages (from-to)	319-330
Number of pages	12
Journal	Linear Algebra and Its Applications
Volume	658
DOIs	https://doi.org/10.1016/j.laa.2022.11.008
Publication status	Published - 1 Feb 2023

Bibliographical note

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 .

Funding

S. Akbari is partially funded by the Iran National Science Foundation (INSF), grant 96004167 . A. Abiad is partially funded by the Fonds Wetenschappelijk Onderzoek (FWO), grant 1285921N .

Keywords

Adjacency matrix
Eigenvalue multiplicity
Laplacian matrix
p-domination number
Rank
Total domination number

Access to Document

10.1016/j.laa.2022.11.008

pdfFinal published version, 349 KBLicence: CC BY

Cite this

@article{d4a3da4329694f9ba99b31bf2768718d,

title = "A bound for the p-domination number of a graph in terms of its eigenvalue multiplicities",

abstract = "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.",

keywords = "Adjacency matrix, Eigenvalue multiplicity, Laplacian matrix, p-domination number, Rank, Total domination number",

author = "A. Abiad and S. Akbari and M.H. Fakharan and A. Mehdizadeh",

note = "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 . ",

year = "2023",

month = feb,

day = "1",

doi = "10.1016/j.laa.2022.11.008",

language = "English",

volume = "658",

pages = "319--330",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Elsevier",

}

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 -

A bound for the p-domination number of a graph in terms of its eigenvalue multiplicities

Abstract

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this