Relationship between the rank and the matching number of a graph

摘要

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.