Signed graphs whose signed Colin de Verdière parameter is two

详细信息    查看全文

• 作者：Marina Arav ; Frank J. Hall ; Zhongshan Li ; Hein van der Holst ^{hvanderholst@gsu.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Signed graphs ; Symmetric matrix ; Nullity ; Excluded minors
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：116
• 期：Complete
• 页码：440-455
• 全文大小：391 K

文摘

A signed graph is a pair formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001148&_mathId=si1.gif&_user=111111111&_pii=S0095895615001148&_rdoc=1&_issn=00958956&md5=dfb7f118c27e21649c1254e60de77656" title="Click to view the MathML source">(G,Σ)flow="scroll">false">(G,Σfalse">), where formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001148&_mathId=si2.gif&_user=111111111&_pii=S0095895615001148&_rdoc=1&_issn=00958956&md5=c324ff4d649d2076cd70d9b58e7f18f4" title="Click to view the MathML source">G=(V,E)flow="scroll">G=false">(V,Efalse">) is a graph (in which parallel edges are permitted, but loops are not) with formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001148&_mathId=si3.gif&_user=111111111&_pii=S0095895615001148&_rdoc=1&_issn=00958956&md5=c29291cd165cbe05aa5187a786428104" title="Click to view the MathML source">V={1,…,n}flow="scroll">V=false">{1,…,nfalse">} and formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001148&_mathId=si4.gif&_user=111111111&_pii=S0095895615001148&_rdoc=1&_issn=00958956&md5=3d255cab5d808b76a0c166c23bd9f42d" title="Click to view the MathML source">Σ⊆Eflow="scroll">Σ⊆E. The edges in Σ are called odd and the other edges even. By formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001148&_mathId=si5.gif&_user=111111111&_pii=S0095895615001148&_rdoc=1&_issn=00958956&md5=ebacfef6709d8fb66b45dc2e94b53d53" title="Click to view the MathML source">S(G,Σ)flow="scroll">Sfalse">(G,Σfalse">) we denote the set of all real symmetric formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001148&_mathId=si6.gif&_user=111111111&_pii=S0095895615001148&_rdoc=1&_issn=00958956&md5=714002ee3b7e543c0119e907a73af1f6" title="Click to view the MathML source">n×nflow="scroll">n×n matrices formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001148&_mathId=si7.gif&_user=111111111&_pii=S0095895615001148&_rdoc=1&_issn=00958956&md5=b53a2c465fc16de54a857cc998df8270" title="Click to view the MathML source">A=[a_i,j]flow="scroll">A=false">[ai,jfalse">] with formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001148&_mathId=si8.gif&_user=111111111&_pii=S0095895615001148&_rdoc=1&_issn=00958956&md5=6b1bb023140d3ddaea1f53778368dca1" title="Click to view the MathML source">a_i,j<0flow="scroll">ai,j<0 if i and j are adjacent and all edges between i and j   are even, formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001148&_mathId=si9.gif&_user=111111111&_pii=S0095895615001148&_rdoc=1&_issn=00958956&md5=0024952c7061fd273ee6d16ecd7b90d0" title="Click to view the MathML source">a_i,j>0flow="scroll">ai,j>0 if i and j are adjacent and all edges between i and j   are odd, and formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001148&_mathId=si10.gif&_user=111111111&_pii=S0095895615001148&_rdoc=1&_issn=00958956&md5=904b876f13d5443d9ba32d88ba34b3b1" title="Click to view the MathML source">a_i,j=0flow="scroll">ai,j=0 if formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001148&_mathId=si11.gif&_user=111111111&_pii=S0095895615001148&_rdoc=1&_issn=00958956&md5=9b6bab7f8799656b521be5f66a2ed470" title="Click to view the MathML source">i≠jflow="scroll">i≠j and i and j   are non-adjacent. The parameter formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001148&_mathId=si12.gif&_user=111111111&_pii=S0095895615001148&_rdoc=1&_issn=00958956&md5=a600710b351ca3d2e2a4707f8c5924dd" title="Click to view the MathML source">ν(G,Σ)flow="scroll">νfalse">(G,Σfalse">) of a signed graph formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001148&_mathId=si1.gif&_user=111111111&_pii=S0095895615001148&_rdoc=1&_issn=00958956&md5=dfb7f118c27e21649c1254e60de77656" title="Click to view the MathML source">(G,Σ)flow="scroll">false">(G,Σfalse">) is the largest nullity of any positive semidefinite matrix formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001148&_mathId=si13.gif&_user=111111111&_pii=S0095895615001148&_rdoc=1&_issn=00958956&md5=7e9c0cec26811744efbaef51ea7a05a8" title="Click to view the MathML source">A∈S(G,Σ)flow="scroll">A∈Sfalse">(G,Σfalse">) that has the Strong Arnold Property. By f&_user=111111111&_pii=S0095895615001148&_rdoc=1&_issn=00958956&md5=6dfd1a787b7154c0e2ab375ea39ab1da">f" data-inlimgeid="1-s2.0-S0095895615001148-si14.gif">flow="scroll">K3= we denote the signed graph obtained from formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001148&_mathId=si15.gif&_user=111111111&_pii=S0095895615001148&_rdoc=1&_issn=00958956&md5=78443afdd88cbe2068e4460e055e4b80" title="Click to view the MathML source">(K₃,∅)flow="scroll">false">(K3,∅false">) by adding to each even edge an odd edge in parallel. In this paper, we prove that a signed graph formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001148&_mathId=si1.gif&_user=111111111&_pii=S0095895615001148&_rdoc=1&_issn=00958956&md5=dfb7f118c27e21649c1254e60de77656" title="Click to view the MathML source">(G,Σ)flow="scroll">false">(G,Σfalse">) has formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001148&_mathId=si16.gif&_user=111111111&_pii=S0095895615001148&_rdoc=1&_issn=00958956&md5=d2fa9df331180a521fa72dc723a8ee82" title="Click to view the MathML source">ν(G,Σ)≤2flow="scroll">νfalse">(G,Σfalse">)≤2 if and only if formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001148&_mathId=si1.gif&_user=111111111&_pii=S0095895615001148&_rdoc=1&_issn=00958956&md5=dfb7f118c27e21649c1254e60de77656" title="Click to view the MathML source">(G,Σ)flow="scroll">false">(G,Σfalse">) has no minor isomorphic to formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001148&_mathId=si17.gif&_user=111111111&_pii=S0095895615001148&_rdoc=1&_issn=00958956&md5=e14c76371b35667e1c8aec1ef228ea9c" title="Click to view the MathML source">(K₄,E(K₄))flow="scroll">false">(K4,Efalse">(K4false">)false">) or f&_user=111111111&_pii=S0095895615001148&_rdoc=1&_issn=00958956&md5=6dfd1a787b7154c0e2ab375ea39ab1da">f" data-inlimgeid="1-s2.0-S0095895615001148-si14.gif">flow="scroll">K3=.