کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4656695 | 1632977 | 2016 | 16 صفحه PDF | دانلود رایگان |

A signed graph is a pair (G,Σ)(G,Σ), where G=(V,E)G=(V,E) is a graph (in which parallel edges are permitted, but loops are not) with V={1,…,n}V={1,…,n} and Σ⊆EΣ⊆E. The edges in Σ are called odd and the other edges even. By S(G,Σ)S(G,Σ) we denote the set of all real symmetric n×nn×n matrices A=[ai,j]A=[ai,j] with ai,j<0ai,j<0 if i and j are adjacent and all edges between i and j are even, ai,j>0ai,j>0 if i and j are adjacent and all edges between i and j are odd, and ai,j=0ai,j=0 if i≠ji≠j and i and j are non-adjacent. The parameter ν(G,Σ)ν(G,Σ) of a signed graph (G,Σ)(G,Σ) is the largest nullity of any positive semidefinite matrix A∈S(G,Σ)A∈S(G,Σ) that has the Strong Arnold Property. By K3= we denote the signed graph obtained from (K3,∅)(K3,∅) by adding to each even edge an odd edge in parallel. In this paper, we prove that a signed graph (G,Σ)(G,Σ) has ν(G,Σ)≤2ν(G,Σ)≤2 if and only if (G,Σ)(G,Σ) has no minor isomorphic to (K4,E(K4))(K4,E(K4)) or K3=.
Journal: Journal of Combinatorial Theory, Series B - Volume 116, January 2016, Pages 440–455