Relationship between the rank and the matching number of a graph

Zhimin Feng, Jing Huang, Shuchao Li and Xiaobing Luo

Applied Mathematics and Computation, 2019, vol. 354, issue C, 411-421

Abstract: Given a simple graph G, let A(G) be its adjacency matrix and α′(G) be its matching number. The rank of G, written as r(G), refers to the rank of A(G). In this paper, some relations between the rank and the matching number of a graph are studied. Firstly, it is proved that −2d(G)⩽r(G)−2α′(G)⩽No, where d(G) and No are, respectively, the dimension of cycle space and the number of odd cycles of G. Secondly, sharp lower bounds on both r(G)−α′(G) and r(G)/α′(G) are determined. All the corresponding extremal graphs are characterized, respectively.

Keywords: Rank; Nullity; Matching number (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300319301596
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:354:y:2019:i:c:p:411-421

DOI: 10.1016/j.amc.2019.02.055

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().