<p>Let <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1896_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="264" /> </InlineMediaObject> <EquationSource Format="TEX">\(\varphi (G)=\max \{ H_G(x, y)| x, y\in V(G)\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>φ</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mo movablelimits="true">max</mo> <mo stretchy="false">{</mo> <msub> <mi>H</mi> <mi>G</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>x</mi> <mo>,</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">|</mo> <mi>x</mi> <mo>,</mo> <mi>y</mi> <mo>∈</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> denote the hitting time of <i>G</i>, where <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1896_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="64" /> </InlineMediaObject> <EquationSource Format="TEX">\(H_G(x, y)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>H</mi> <mi>G</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>x</mi> <mo>,</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> represents the expected hitting time from vertex <i>x</i> to vertex <i>y</i> in a simple connected graph <i>G</i>. We investigate extremal problems related to hitting time on unicyclic graphs with a given maximum degree. We examine how the hitting time is affected by graph transformations. By employing graph grafting techniques to increase the hitting time of graphs, we establish a sharp upper bound for the hitting time of unicyclic graphs with a given maximum degree and identify the corresponding extremal graph.</p>

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

The Hitting Time of Random Walks on Unicyclic Graphs with a Given Maximum Degree

  • Xiao-Min Zhu,
  • Ya-Li Xie,
  • Ying-Ke Yan,
  • Jing Chen

摘要

Let \(\varphi (G)=\max \{ H_G(x, y)| x, y\in V(G)\}\) φ ( G ) = max { H G ( x , y ) | x , y V ( G ) } denote the hitting time of G, where \(H_G(x, y)\) H G ( x , y ) represents the expected hitting time from vertex x to vertex y in a simple connected graph G. We investigate extremal problems related to hitting time on unicyclic graphs with a given maximum degree. We examine how the hitting time is affected by graph transformations. By employing graph grafting techniques to increase the hitting time of graphs, we establish a sharp upper bound for the hitting time of unicyclic graphs with a given maximum degree and identify the corresponding extremal graph.