Partially ordering the class of invertible trees

DOI10.1016/J.EJC.2019.103019MaRDI QIDQ2011139zbMATH OpenOpenAlexFDO

Authors Krystal Guo

Publication date 28 November 2019

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.07181

zbMATH Keywords

adjacency matrixbipartite graphperfect matchingspartially ordered setsleast positive eigenvalueMöbius inversion

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Trees (05C05)

Abstract: A tree T is invertible if and only if T has a perfect matching. Godsil considers an invertible tree T and finds that the inverse of the adjacency matrix of T has entries in {0, 1, -1} and is the signed adjacency matrix of a graph which contains T. In this paper, we give a new proof of this theorem, which gives rise to a partial ordering relation on the class of all invertible trees on 2n vertices. In particular, we show that given an invertible tree T whose inverse graph has strictly more edges, we can remove an edge from T and add another edge to obtain an invertible tree T' whose median eigenvalue is strictly greater. This extends naturally to a partial ordering. We characterize the maximal and minimal elements of this poset and explore the implications about the median eigenvalues of invertible trees.

Recommendations

• Inverses of trees
• Inverting non-invertible labeled trees
• On graphs with signed inverses
• On the inverse and the dual index of a tree
• On nonsingular trees and a reciprocal eigenvalue property

Cites work

• scientific article; zbMATH DE number 428989 (Why is no real title available?)
• scientific article; zbMATH DE number 3681810 (Why is no real title available?)
• scientific article; zbMATH DE number 3547309 (Why is no real title available?)
• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• A new graph product and its spectrum
• Graph invertibility
• Graph invertibility and median eigenvalues
• HOMO-LUMO maps for chemical graphs
• Inverses of bipartite graphs
• Inverses of trees
• Median eigenvalues and the HOMO-LUMO index of graphs
• Median eigenvalues of bipartite graphs
• On nonsingular trees and a reciprocal eigenvalue property
• On some graphs which possess inverses
• On the eigenvalues of trees
• Signed graphs
• Solution to a problem of C. D. Godsil regarding bipartite graphs with unique perfect matching
• Strongly self-dual graphs

Cited in

(2)

• Graph invertibility and median eigenvalues
• Inverses of trees

This page was built for publication: Partially ordering the class of invertible trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2011139)