On the inertia set of a signed tree with loops

详细信息    查看全文

• 作者：Marina Arav ; Hein van der Holst ; ¹ ; ^{hvanderholst@gsu.edu" class="auth_mail" title="E-mail the corresponding author} ; John Sinkovic
• 关键词：05C22 ; 05C50 ; 15A03
• 刊名：Linear Algebra and its Applications
• 出版年：2016
• 出版时间：1 December 2016
• 年：2016
• 卷：510
• 期：Complete
• 页码：361-372
• 全文大小：306 K

文摘

A signed graph is a pair (G,Σ)$(G,\mathrm{\Sigma })$, where G=(V,E)$G=(V,E)$ is a graph (in which parallel edges and loops are permitted) with V={1,…,n}$V=\{1,\dots ,n\}$ and Σ⊆E$\mathrm{\Sigma }\subseteq E$. The edges in Σ are called odd edges and the other edges of E   even. By S(G,Σ)$S(G,\mathrm{\Sigma })$ we denote the set of all n×n$n\times n$ real symmetric matrices A=[a_i,j]$A=[a_{i,j}]$ such that if a_i,j<0$a_{i,j}<0$, then among the edges connecting i and j  , there must be at least one even edge; if a_i,j>0$a_{i,j}>0$, then among the edges connecting i and j  , there must be at least one odd edge; and if ccdf816b2c88febbbfa9" title="Click to view the MathML source">a_i,j=0$a_{i,j}=0$, then either there must be at least one odd edge and at least one even edge connecting i and j, or there are no edges connecting i and j  . (Here we allow i=j$i=j$.) For a real symmetric matrix A, the partial inertia of A   is the pair (p,q)$(p,q)$, where p and q are the number of positive and negative eigenvalues of A  , respectively. If (G,Σ)$(G,\mathrm{\Sigma })$ is a signed graph, we define the inertia set of (G,Σ)$(G,\mathrm{\Sigma })$ as the set of the partial inertias of all matrices A∈S(G,Σ)$A\in S(G,\mathrm{\Sigma })$. By MR(G,Σ)$\mathrm{MR}(G,\mathrm{\Sigma })$ we denote max⁡{rank(A)|A∈S(G,Σ)}$\max \{\mathrm{rank}(A)|A\in S(G,\mathrm{\Sigma })\}$. We say that a signed graph (G,Σ)$(G,\mathrm{\Sigma })$ satisfies the Northeast Property if for each (p,q)$(p,q)$ with p+q<MR(G,Σ)$p+q<\mathrm{MR}(G,\mathrm{\Sigma })$ in the inertia set of (G,Σ)$(G,\mathrm{\Sigma })$, also (p+1,q),(p,q+1)$(p+1,q),(p,q+1)$ belong to the inertia set of (G,Σ)$(G,\mathrm{\Sigma })$.

In this paper, we show that if (G,Σ)$(G,\mathrm{\Sigma })$ is a signed graph, where G   is a tree with possibly loops attached at some of the vertices, then (G,Σ)$(G,\mathrm{\Sigma })$ satisfies the Northeast Property. Furthermore, we present a formula for calculating the inertia set of a signed graph (G,Σ)$(G,\mathrm{\Sigma })$, where G is a tree with possibly loops attached at some of the vertices.