“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 7907
School of Mathematics
  Title:   The kernels of the incidence matrices of graphs revisited
1.  S. Akbari
2.  N. Ghareghani
3.  G. B. Khosrovshahi
4.  H. R. Maimani
  Status:   Published
  Journal: Linear Algebra Appl.
  Vol.:  414
  Year:  2006
  Pages:   617-625
  Supported by:  IPM
In this paper we study the structure of some special bases for the null space of the incidence matrix of a graph. Recently it was shown that if G is a graph with no cut vertex, then G has a {−1,0,1}-basis. We generalize this result showing that the statement remains valid for every graph with no cut edge. For the null space of any bipartite graph, we construct {−1,0,1}-basis. For any bipartite graph we obtain the support sizes of all elements in the null space of its incidence matrix. Among other things, we prove that for a graph G, there exists a {−1,1}-vector for the null space of G if and only if the degree of any vertex of G is even and G has an even number of edges.

Download TeX format
back to top
scroll left or right