On the Nullity of Bipartite Graphs |
| |
Authors: | G R Omidi |
| |
Institution: | (1) Department of Mathematical Sciences, Isfahan University of Technology, Isfahan, 84156-83111, Iran;(2) School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O.Box:19395-5746, Tehran, Iran |
| |
Abstract: | The nullity of a graph is the multiplicity of the eigenvalue zero in its spectrum. We obtain some lower bounds for the nullity
of graphs and we then find the nullity of bipartite graphs with no cycle of length a multiple of 4 as a subgraph. Among bipartite
graphs on n vertices, the star has the greatest nullity (equal to n − 2). We generalize this by showing that among bipartite graphs with n vertices, e edges and maximum degree Δ which do not have any cycle of length a multiple of 4 as a subgraph, the greatest nullity is .
G. R. Omidi: This research was in part supported by a grant from IPM (No.87050016). |
| |
Keywords: | Nullity of a graph Maximum matchings Bipartite graphs |
本文献已被 SpringerLink 等数据库收录! |
|