Graph invertibility and median eigenvalues

DOI10.1016/J.LAA.2016.10.020MaRDI QIDQ344913zbMATH OpenOpenAlexFDO

Authors Dong Ye, Yujun Yang, Bholanath Mandal, Douglas J. Klein

Publication date 25 November 2016

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

weighted graphsgraph inversemedian eigenvalues

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Signed and weighted graphs (05C22)

Abstract: Let $(G,w)$ be a weighted graph with a weight-function $$. A weighted graph $(G,w)$ is invertible to a new weighted graph if its adjacency matrix is invertible. A graph inverse has combinatorial interest and can be applied to bound median eigenvalues of a graph such as have physical meanings in Quatumn Chemistry. In this paper, we characterize the inverse of a weighted graph based on its Sachs subgraphs that are spanning subgraphs with only $K_2$ or cycles (or loops) as components. The characterization can be used to find the inverse of a weighted graph based on its structures instead of its adjacency matrix. If a graph has its spectra split about the origin, i.e., half of eigenvalues are positive and half of them are negative, then its median eigenvalues can be bounded by estimating the largest and smallest eigenvalues of its inverse. We characterize graphs with a unique Sachs subgraph and prove that these graphs has their spectra split about the origin if they have a perfect matching. As applications, we show that the median eigenvalues of stellated graphs of trees and corona graphs belong to different halves of the interval $[-1,1]$.

Recommendations

• Inverses of weighted graphs
• On the inverse of a class of weighted graphs
• On The Inverse Of A Class Of Bipartite Graphs With Unique Perfect Matchings
• Partially ordering the class of invertible trees
• On graphs with signed inverses

Cites work

• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• A mathematical bibliography of signed and gain graphs and allied areas
• Acyclic molecules with greatest HOMO-LUMO separation
• Eigenvalues of saturated hydrocarbons
• Graph invertibility
• HOMO-LUMO maps for chemical graphs
• Inverses of trees
• Inverses of triangular matrices and bipartite graphs
• Irredundance in inflated graphs
• Matching theory
• Maximal energy graphs
• Median eigenvalues and the HOMO-LUMO index of graphs
• Median eigenvalues of bipartite planar graphs
• Median eigenvalues of bipartite subcubic graphs
• Motzkin numbers
• Signed graphs
• Solution to a problem of C. D. Godsil regarding bipartite graphs with unique perfect matching
• The Determinant of the Adjacency Matrix of a Graph
• The spectrum of infinite regular line graphs
• Treediagonal matrices and their inverses
• Which Nonnegative Matrices Are Self-Inverse?

Cited in

(15)

• Inverting non-invertible labeled trees
• Partially ordering the class of invertible trees
• On the Moore-Penrose pseudo-inversion of block symmetric matrices and its application in the graph theory
• Group inverses of weighted trees
• Group inverses of a class of corona networks
• On unimodular graphs with a unique perfect matching
• Inverses of non-bipartite unicyclic graphs with a unique perfect matching
• On the inverse of unicyclic 3-coloured digraphs
• On the eigenvalues distribution in threshold graphs
• A note on median eigenvalues of subcubic graphs
• Strongly self-inverse weighted graphs
• On invertible non-bipartite unicyclic graphs with a unique perfect matching and their smallest positive eigenvalues
• Qualitative, statistical, and extreme properties of spectral indices of signable pseudo-invertible graphs
• On a construction of integrally invertible graphs and their spectral properties
• Complex matrix inversion via real matrix inversions

This page was built for publication: Graph invertibility and median eigenvalues

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