<p>The Kirchhoff index <i>Kf</i>(<i>G</i>) of <i>G</i> is defined as the sum of the resistance distances between all pairs of vertices in <i>G</i>. In 2024, Gottwald, Majstorović Ergotić and Došlić studied the problem of identifying graphs for which <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_780_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="156" /> </InlineMediaObject> <EquationSource Format="TEX">\(Kf(G)=Kf(G-v)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>K</mi> <mi>f</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>K</mi> <mi>f</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo>-</mo> <mi>v</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for all <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_780_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="71" /> </InlineMediaObject> <EquationSource Format="TEX">\(v\in V(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>v</mi> <mo>∈</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and found only one graph with this property: the cycle with 5 vertices. In this paper, we explore a relaxed version of this problem. Specifically, we aim to identify graphs that preserve the Kirchhoff index after the removal of a specific vertex, which we term a good vertex. Our investigation focuses on unicyclic graphs and cactus graphs, leading to several results. We construct infinitely many unicyclic graphs with girth 3 that contain exactly one good vertex. Moreover, for a given positive integer <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_780_Article_IEq3.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">\(c\ge 4\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>c</mi> <mo>≥</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation> we show the existence of an infinite family of unicyclic graphs with girth <i>c</i> with at least two good vertices. Additionally, we prove that the smallest number of vertices in a unicyclic graph, which is not a cycle and contains at least two good vertices, is 8. We expand our research to cactus graphs to show that for a fixed positive integer <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_780_Article_IEq4.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">\(k\ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> there exists an infinite family of cactus graphs with at least <i>k</i> cycles, where each graph in the family has at least two good vertices.</p>

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

Graphs that preserve Kirchhoff index after the removal of a vertex

  • Snježana Majstorović Ergotić,
  • Kurt Klement Gottwald

摘要

The Kirchhoff index Kf(G) of G is defined as the sum of the resistance distances between all pairs of vertices in G. In 2024, Gottwald, Majstorović Ergotić and Došlić studied the problem of identifying graphs for which \(Kf(G)=Kf(G-v)\) K f ( G ) = K f ( G - v ) for all \(v\in V(G)\) v V ( G ) and found only one graph with this property: the cycle with 5 vertices. In this paper, we explore a relaxed version of this problem. Specifically, we aim to identify graphs that preserve the Kirchhoff index after the removal of a specific vertex, which we term a good vertex. Our investigation focuses on unicyclic graphs and cactus graphs, leading to several results. We construct infinitely many unicyclic graphs with girth 3 that contain exactly one good vertex. Moreover, for a given positive integer \(c\ge 4\) c 4 we show the existence of an infinite family of unicyclic graphs with girth c with at least two good vertices. Additionally, we prove that the smallest number of vertices in a unicyclic graph, which is not a cycle and contains at least two good vertices, is 8. We expand our research to cactus graphs to show that for a fixed positive integer \(k\ge 2\) k 2 there exists an infinite family of cactus graphs with at least k cycles, where each graph in the family has at least two good vertices.