Graph invertibility and median eigenvalues

详细信息    查看全文

• 作者：Dong Ye^a ; ^{dong.ye@mtsu.edu" class="auth_mail" title="E-mail the corresponding author} ; Yujun Yang^b ; ^{yangyj@yahoo.com" class="auth_mail" title="E-mail the corresponding author} ; Bholanath Mandal^c ; ^{bmandal@chem.buruniv.ac" class="auth_mail" title="E-mail the corresponding author} ; Douglas J. Klein^d ; ^{kleind@tamug.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：05C50
• 刊名：Linear Algebra and its Applications
• 出版年：2017
• 出版时间：15 January 2017
• 年：2017
• 卷：513
• 期：Complete
• 页码：304-323
• 全文大小：506 K

文摘

Let 24379516304931&_mathId=si1.gif&_user=111111111&_pii=S0024379516304931&_rdoc=1&_issn=00243795&md5=38cfe5da467027570a25d2f202437231" title="Click to view the MathML source">(G,w)$(G,w)$ be a weighted graph with a weight-function 24379516304931&_mathId=si2.gif&_user=111111111&_pii=S0024379516304931&_rdoc=1&_issn=00243795&md5=2259127a96dbe93eb21e165d0df21276" title="Click to view the MathML source">w:E(G)→R\{0}$w:E(G)\to \mathbb{R}\backslash \{0\}$. A weighted graph 24379516304931&_mathId=si1.gif&_user=111111111&_pii=S0024379516304931&_rdoc=1&_issn=00243795&md5=38cfe5da467027570a25d2f202437231" title="Click to view the MathML source">(G,w)$(G,w)$ is invertible to a new weighted graph if its adjacency matrix is invertible. Graph inverses have combinatorial interests and can be applied to bound median eigenvalues of graphs such as have physical meanings. In this paper, we characterize the inverse of a weighted graph based on its Sachs subgraphs that are spanning subgraphs with only 24379516304931&_mathId=si3.gif&_user=111111111&_pii=S0024379516304931&_rdoc=1&_issn=00243795&md5=d2b13e009f6df1626bbf11c2d7acedb5" title="Click to view the MathML source">K₂mrow>Kmrow><mrow>2mrow> 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 24379516304931&_mathId=si4.gif&_user=111111111&_pii=S0024379516304931&_rdoc=1&_issn=00243795&md5=c074177110dde23b3e3d473ac5da10ca" title="Click to view the MathML source">[−1,1]$[-1,1]$.