On the nullity number of graphs

Mustapha Aouchiche; Pierre Hansen

doi:10.5614/ejgta.2017.5.2.14

On the nullity number of graphs

Mustapha Aouchiche, Pierre Hansen

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

7 Citations (Scopus)

Abstract

The paper discusses bounds on the nullity number of graphs. It is proved in [B. Cheng and B. Liu, On the nullity of graphs. Electron. J. Linear Algebra 16 (2007) 60-67] that η ≤ n-D, where η, n and D denote the nullity number, the order and the diameter of a connected graph, respectively. We first give a necessary condition on the extremal graphs corresponding to that bound, and then we strengthen the bound itself using the maximum clique number. In addition, we prove bounds on the nullity using the number of pendant neighbors in a graph. One of those bounds is an improvement of a known bound involving the domination number.

Original language	English
Pages (from-to)	335-346
Number of pages	12
Journal	Electronic Journal of Graph Theory and Applications
Volume	5
Issue number	2
DOIs	https://doi.org/10.5614/ejgta.2017.5.2.14
Publication status	Published - 2017
Externally published	Yes

Keywords

Adjacency matrix
Diameter
Domination number
Matching number
Nullity number
Pendant neighbor

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.5614/ejgta.2017.5.2.14

Cite this

@article{80e9931be4e94ca09d9004a5dc7b517b,

title = "On the nullity number of graphs",

abstract = "The paper discusses bounds on the nullity number of graphs. It is proved in [B. Cheng and B. Liu, On the nullity of graphs. Electron. J. Linear Algebra 16 (2007) 60-67] that η ≤ n-D, where η, n and D denote the nullity number, the order and the diameter of a connected graph, respectively. We first give a necessary condition on the extremal graphs corresponding to that bound, and then we strengthen the bound itself using the maximum clique number. In addition, we prove bounds on the nullity using the number of pendant neighbors in a graph. One of those bounds is an improvement of a known bound involving the domination number.",

keywords = "Adjacency matrix, Diameter, Domination number, Matching number, Nullity number, Pendant neighbor",

author = "Mustapha Aouchiche and Pierre Hansen",

year = "2017",

doi = "10.5614/ejgta.2017.5.2.14",

language = "English",

volume = "5",

pages = "335--346",

journal = "Electronic Journal of Graph Theory and Applications",

issn = "2338-2287",

publisher = "Indonesian Combinatorics Society",

number = "2",

}

TY - JOUR

T1 - On the nullity number of graphs

AU - Aouchiche, Mustapha

AU - Hansen, Pierre

PY - 2017

Y1 - 2017

N2 - The paper discusses bounds on the nullity number of graphs. It is proved in [B. Cheng and B. Liu, On the nullity of graphs. Electron. J. Linear Algebra 16 (2007) 60-67] that η ≤ n-D, where η, n and D denote the nullity number, the order and the diameter of a connected graph, respectively. We first give a necessary condition on the extremal graphs corresponding to that bound, and then we strengthen the bound itself using the maximum clique number. In addition, we prove bounds on the nullity using the number of pendant neighbors in a graph. One of those bounds is an improvement of a known bound involving the domination number.

AB - The paper discusses bounds on the nullity number of graphs. It is proved in [B. Cheng and B. Liu, On the nullity of graphs. Electron. J. Linear Algebra 16 (2007) 60-67] that η ≤ n-D, where η, n and D denote the nullity number, the order and the diameter of a connected graph, respectively. We first give a necessary condition on the extremal graphs corresponding to that bound, and then we strengthen the bound itself using the maximum clique number. In addition, we prove bounds on the nullity using the number of pendant neighbors in a graph. One of those bounds is an improvement of a known bound involving the domination number.

KW - Adjacency matrix

KW - Diameter

KW - Domination number

KW - Matching number

KW - Nullity number

KW - Pendant neighbor

UR - http://www.scopus.com/inward/record.url?scp=85031930938&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85031930938&partnerID=8YFLogxK

U2 - 10.5614/ejgta.2017.5.2.14

DO - 10.5614/ejgta.2017.5.2.14

M3 - Article

AN - SCOPUS:85031930938

SN - 2338-2287

VL - 5

SP - 335

EP - 346

JO - Electronic Journal of Graph Theory and Applications

JF - Electronic Journal of Graph Theory and Applications

IS - 2

ER -

On the nullity number of graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this