Graph invertibility and median eigenvalues

DOI10.1016/J.LAA.2016.10.020zbMATH Open1350.05057arXiv1506.04054OpenAlexW2963729450MaRDI QIDQ344913FDOQ344913

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)

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]$.

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

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

zbMATH Keywords

weighted graphsgraph inversemedian eigenvalues

Mathematics Subject Classification ID

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

Cites Work

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

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
• A note on median eigenvalues of subcubic graphs
• On the eigenvalues distribution in threshold 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)