Moore–Penrose inverse of incidence matrix of graphs with complete and cyclic blocks

• Published in: Discrete mathematics 2019-01, Vol.342 (1), p.10-17
• Main Authors: Azimi, A., Bapat, R.B., Estaji, E.
• Format: Article
• Language: English
• Subjects: Block graph; Cut vertex; Moore–Penrose inverse
• ISSN: 0012-365X; 1872-681X
• DOI: 10.1016/j.disc.2018.09.020

Let Γ be a graph with n vertices, where each edge is given an orientation and let Q be the vertex–edge incidence matrix of Γ. Suppose that Γ has a cut-vertex v and Γ−v=Γ[V1]∪Γ[V2]. We obtain a relation between the Moore–Penrose inverse of the incidence matrix of Γ and of the incidence matrices of the induced subgraphs Γ[V1∪{v}] and Γ[V2∪{v}]. The result is used to give a combinatorial interpretation of the Moore–Penrose inverse of the incidence matrix of a graph whose blocks are either cliques or cycles. Moreover we obtain a description of minors of the Moore–Penrose inverse of the incidence matrix when the rows are indexed by cut-edges. The results generalize corresponding results for trees in the literature.