Matching number in relation with maximal-minimal nullity conditions and cyclomatic number by coefficient relations

Abstract

Let G be a simple graph. So called K2 deletion process was recently introduced by Wang. A subgraph G' of G that is obtained as a result of some K i deletion process will be called as a crucial subgroup. Let f (G) and v(G') be the matching numbers of G and G', respectively. In this study, we study the relation between i/(G), v{G') and the coefficients of the characteristic polynomials of G and G'. Several results are obtained on these notions. Moreover, conservation of maximal and minimal nullity conditions after applying Ki deletion process are studied. As a result of this, when G satisfies the maximal or minimal nullity condition, we obtain the conditions for the equality c(G) = c(G') where c(G) and c(G') denote the cyclomatic numbers of G and G', respectively. Finally, for some graphs, we state u{G) in terms of c(G), c(G'), n(G), n(G') and the coefficients of the characteristic polynomials of G and G' where n(G), n(G') are the numbers of vertices of G and G', respectively.