<p>Let <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1913_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="12" /> </InlineMediaObject> <EquationSource Format="TEX">$\Gamma $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Γ</mi> </math></EquationSource> </InlineEquation> be a graph and <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1913_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="38" /> </InlineMediaObject> <EquationSource Format="TEX">$D(\Gamma )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>D</mi> <mo stretchy="false">(</mo> <mi mathvariant="normal">Γ</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> be the canonical double cover of <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1913_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="12" /> </InlineMediaObject> <EquationSource Format="TEX">$\Gamma $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Γ</mi> </math></EquationSource> </InlineEquation>. We say that <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1913_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="12" /> </InlineMediaObject> <EquationSource Format="TEX">$\Gamma $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Γ</mi> </math></EquationSource> </InlineEquation> is stable if <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1913_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="188" /> </InlineMediaObject> <EquationSource Format="TEX">$\textrm{Aut}(D(\Gamma ))\cong \textrm{Aut}(\Gamma )\times \mathbb {Z}_{2}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>Aut</mtext> <mrow> <mo stretchy="false">(</mo> <mi>D</mi> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="normal">Γ</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <mo>≅</mo> <mtext>Aut</mtext> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="normal">Γ</mi> <mo stretchy="false">)</mo> </mrow> <mo>×</mo> <msub> <mi mathvariant="double-struck">Z</mi> <mn>2</mn> </msub> </mrow> </math></EquationSource> </InlineEquation> and unstable otherwise. In this paper, we introduce a construction of unstable graphs from bipartite graphs and apply this construction to Cayley graphs by giving a sufficient condition for the instability of Cayley graphs of a group that has a subgroup of index 2. We observe that circulant graphs of Wilson type <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1913_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="38" /> </InlineMediaObject> <EquationSource Format="TEX">$(\textrm{C}.1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mtext>C</mtext> <mo>.</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1913_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">$(\mathrm {C'}.2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msup> <mi mathvariant="normal">C</mi> <mo>′</mo> </msup> <mo>.</mo> <mn>2</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> or <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1913_Article_IEq8.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">$(\mathrm {C'}.3)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msup> <mi mathvariant="normal">C</mi> <mo>′</mo> </msup> <mo>.</mo> <mn>3</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> can be constructed in this way.</p>

Constructing Unstable Graphs from Bipartite Graphs

期刊论文
发表日期：

2025年6月30日

查看全文

Haiyan Jiang,
Junyang Zhang

摘要

Let $\Gamma $ $Γ$ be a graph and $D(\Gamma )$ $D (Γ)$ be the canonical double cover of $\Gamma $ $Γ$ . We say that $\Gamma $ $Γ$ is stable if $\textrm{Aut}(D(\Gamma ))\cong \textrm{Aut}(\Gamma )\times \mathbb {Z}_{2}$ $Aut (D (Γ)) ≅ Aut (Γ) \times Z_{2}$ and unstable otherwise. In this paper, we introduce a construction of unstable graphs from bipartite graphs and apply this construction to Cayley graphs by giving a sufficient condition for the instability of Cayley graphs of a group that has a subgroup of index 2. We observe that circulant graphs of Wilson type $(\textrm{C}.1)$ $(C . 1)$ , $(\mathrm {C'}.2)$ $(C^{'} . 2)$ or $(\mathrm {C'}.3)$ $(C^{'} . 3)$ can be constructed in this way.