Characterization of graphs whose signature equals the number of odd cycles
详细信息 查看全文
- 作者：Xiaobin Ma<sup> ; sup><sup>1sup><sup> ; sup><sup>maxiaobinzaozhuang@163.com" class="auth_mail" title="E-mail the corresponding authorsup> ; Dein Wong ; Fenglei Tian
- 关键词：05C50
- 刊名：Linear Algebra and its Applications
- 出版年：2016
- 出版时间：15 December 2016
- 年：2016
- 卷：511
- 期：Complete
- 页码：259-273
- 全文大小：388 K
文摘
Let G be a simple graph with vertex set <span id="mmlsi1" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0024379516304165&_mathId=si1.gif&_user=111111111&_pii=S0024379516304165&_rdoc=1&_issn=00243795&md5=5f92619e53f560deba2727d01ce615dd" title="Click to view the MathML source">V(G)span><span class="mathContainer hidden"><span class="mathCode">span>span>span> and edge set <span id="mmlsi2" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0024379516304165&_mathId=si2.gif&_user=111111111&_pii=S0024379516304165&_rdoc=1&_issn=00243795&md5=065ff6a23afe8b23319ae59bf8df5e0d" title="Click to view the MathML source">E(G)span><span class="mathContainer hidden"><span class="mathCode">span>span>span>. The signature <span id="mmlsi3" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0024379516304165&_mathId=si3.gif&_user=111111111&_pii=S0024379516304165&_rdoc=1&_issn=00243795&md5=43ff3492fbe7a925e2bffee028a5a753" title="Click to view the MathML source">s(G)span><span class="mathContainer hidden"><span class="mathCode">span>span>span> of G is the difference between the number of positive eigenvalues and the number of negative eigenvalues of the adjacency matrix <span id="mmlsi4" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0024379516304165&_mathId=si4.gif&_user=111111111&_pii=S0024379516304165&_rdoc=1&_issn=00243795&md5=08ebe3805ac02ff7e2ffa02da81437d8" title="Click to view the MathML source">A(G)span><span class="mathContainer hidden"><span class="mathCode">span>span>span>. In <span id="bbr0200">[20]span>, it was proved that <span id="mmlsi25" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0024379516304165&_mathId=si25.gif&_user=111111111&_pii=S0024379516304165&_rdoc=1&_issn=00243795&md5=db404d4289c2a36dbbd4084b25a3d99a" title="Click to view the MathML source">−c<sub>1sub>(G)≤s(G)≤c<sub>1sub>(G)span><span class="mathContainer hidden"><span class="mathCode">span>span>span>, where <span id="mmlsi26" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0024379516304165&_mathId=si26.gif&_user=111111111&_pii=S0024379516304165&_rdoc=1&_issn=00243795&md5=cb716b965705155fba9a6f587c78b6cf" title="Click to view the MathML source">c<sub>1sub>(G)span><span class="mathContainer hidden"><span class="mathCode">span>span>span> denotes the number of odd cycles in G . A problem arises naturally: What graphs have signature attaining the upper bound <span id="mmlsi26" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0024379516304165&_mathId=si26.gif&_user=111111111&_pii=S0024379516304165&_rdoc=1&_issn=00243795&md5=cb716b965705155fba9a6f587c78b6cf" title="Click to view the MathML source">c<sub>1sub>(G)span><span class="mathContainer hidden"><span class="mathCode">span>span>span> (resp., the lower bound <span id="mmlsi7" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0024379516304165&_mathId=si7.gif&_user=111111111&_pii=S0024379516304165&_rdoc=1&_issn=00243795&md5=830def73ce03647f77f8180c5abdea29" title="Click to view the MathML source">−c<sub>1sub>(G)span><span class="mathContainer hidden"><span class="mathCode">span>span>span>)? In this paper, we focus our attention on this problem, characterizing graphs G whose signature equals <span id="mmlsi26" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0024379516304165&_mathId=si26.gif&_user=111111111&_pii=S0024379516304165&_rdoc=1&_issn=00243795&md5=cb716b965705155fba9a6f587c78b6cf" title="Click to view the MathML source">c<sub>1sub>(G)span><span class="mathContainer hidden"><span class="mathCode">span>span>span> (resp., <span id="mmlsi7" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0024379516304165&_mathId=si7.gif&_user=111111111&_pii=S0024379516304165&_rdoc=1&_issn=00243795&md5=830def73ce03647f77f8180c5abdea29" title="Click to view the MathML source">−c<sub>1sub>(G)span><span class="mathContainer hidden"><span class="mathCode">span>span>span>).