<p>A graph <i>H</i> is a star complement for an eigenvalue <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\mu \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>μ</mi> </math></EquationSource> </InlineEquation> in its extension <i>G</i> if <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\mu \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>μ</mi> </math></EquationSource> </InlineEquation> is not in the spectrum of&#xa0;<i>H</i>, but appears as an eigenvalue of <i>G</i> with multiplicity <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(|V(G)|-|V(H)|\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">|</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo stretchy="false">|</mo> <mo>-</mo> <mo stretchy="false">|</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> <mo stretchy="false">|</mo> </mrow> </math></EquationSource> </InlineEquation>. The eigenvalues 0 and&#xa0;<InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(-\,1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>-</mo> <mspace width="0.166667em" /> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> pose certain obstruction to the general theory, as for every&#xa0;<i>H</i> there is a finite number of graphs containing&#xa0;<i>H</i> as a star complement for <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\mu \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>μ</mi> </math></EquationSource> </InlineEquation> if and only if <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\mu \notin \{0,-\,1\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>μ</mi> <mo>∉</mo> <mo stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mo>-</mo> <mspace width="0.166667em" /> <mn>1</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>. We establish some structural properties of regular graphs having a path as a star complement for any of these eigenvalues. It occurs that, for a fixed path, either there are no regular extensions or there is an infinite family of such extensions. We also discuss corona products <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(T\circ K_1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>T</mi> <mo>∘</mo> <msub> <mi>K</mi> <mn>1</mn> </msub> </mrow> </math></EquationSource> </InlineEquation> as star complements for 0 in regular graphs, where&#xa0;<i>T</i> is either a star or a path. Regular extensions are characterized, and in some particular cases they are completely determined. In contrast to the previous case, here we encounter the existence of a unique regular extension among regular graphs with a given vertex degree greater than 2.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Paths and related graphs as star complements for 0 or \(-\,1\) in regular graphs

  • Zoran Stanić

摘要

A graph H is a star complement for an eigenvalue \(\mu \) μ in its extension G if \(\mu \) μ is not in the spectrum of H, but appears as an eigenvalue of G with multiplicity \(|V(G)|-|V(H)|\) | V ( G ) | - | V ( H ) | . The eigenvalues 0 and  \(-\,1\) - 1 pose certain obstruction to the general theory, as for every H there is a finite number of graphs containing H as a star complement for \(\mu \) μ if and only if \(\mu \notin \{0,-\,1\}\) μ { 0 , - 1 } . We establish some structural properties of regular graphs having a path as a star complement for any of these eigenvalues. It occurs that, for a fixed path, either there are no regular extensions or there is an infinite family of such extensions. We also discuss corona products \(T\circ K_1\) T K 1 as star complements for 0 in regular graphs, where T is either a star or a path. Regular extensions are characterized, and in some particular cases they are completely determined. In contrast to the previous case, here we encounter the existence of a unique regular extension among regular graphs with a given vertex degree greater than 2.