کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656695 1632977 2016 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Signed graphs whose signed Colin de Verdière parameter is two
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Signed graphs whose signed Colin de Verdière parameter is two
چکیده انگلیسی

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=.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 116, January 2016, Pages 440–455
نویسندگان
, , , ,