<p>A nut graph is a nontrivial simple graph whose adjacency matrix contains a one-dimensional null space spanned by a vector without zero entries. Moreover, an <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3218_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="12" /> </InlineMediaObject> <EquationSource Format="TEX">\(\ell \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation>-circulant graph is a graph that admits a cyclic group of automorphisms having <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3218_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="12" /> </InlineMediaObject> <EquationSource Format="TEX">\(\ell \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation> vertex orbits of equal size. It is not difficult to observe that there exists no cubic 1-circulant nut graph or cubic 2-circulant nut graph, while the full classification of all the cubic 3-circulant nut graphs was recently obtained (Damnjanović et al. in Electron J Comb 31(2):P2.31, 2024). Here, we investigate the existence of cubic <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3218_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="12" /> </InlineMediaObject> <EquationSource Format="TEX">\(\ell \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation>-circulant nut graphs for <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3218_Article_IEq5.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">\(\ell \ge 4\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ℓ</mi> <mo>≥</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation> and show that there is no cubic 4-circulant nut graph or cubic 5-circulant nut graph by using a computer-assisted proof. Furthermore, we rely on a construction based approach in order to demonstrate that there exist infinitely many cubic <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3218_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="12" /> </InlineMediaObject> <EquationSource Format="TEX">\(\ell \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation>-circulant nut graphs for any fixed <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3218_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="74" /> </InlineMediaObject> <EquationSource Format="TEX">\(\ell \in \{6, 7 \}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ℓ</mi> <mo>∈</mo> <mo stretchy="false">{</mo> <mn>6</mn> <mo>,</mo> <mn>7</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> or <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3218_Article_IEq8.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">\(\ell \ge 9\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ℓ</mi> <mo>≥</mo> <mn>9</mn> </mrow> </math></EquationSource> </InlineEquation>.</p>

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

On cubic polycirculant nut graphs

  • Nino Bašić,
  • Ivan Damnjanović

摘要

A nut graph is a nontrivial simple graph whose adjacency matrix contains a one-dimensional null space spanned by a vector without zero entries. Moreover, an \(\ell \) -circulant graph is a graph that admits a cyclic group of automorphisms having \(\ell \) vertex orbits of equal size. It is not difficult to observe that there exists no cubic 1-circulant nut graph or cubic 2-circulant nut graph, while the full classification of all the cubic 3-circulant nut graphs was recently obtained (Damnjanović et al. in Electron J Comb 31(2):P2.31, 2024). Here, we investigate the existence of cubic \(\ell \) -circulant nut graphs for \(\ell \ge 4\) 4 and show that there is no cubic 4-circulant nut graph or cubic 5-circulant nut graph by using a computer-assisted proof. Furthermore, we rely on a construction based approach in order to demonstrate that there exist infinitely many cubic \(\ell \) -circulant nut graphs for any fixed \(\ell \in \{6, 7 \}\) { 6 , 7 } or \(\ell \ge 9\) 9 .