The Wiener index W(G) of a graph G is the sum of distances between all unordered pairs of its vertices. Dobrynin and Mel’nikov (Dist Mol Graphs Theory: 85–121, 2012) propose the study of estimates for extremal values of the ratio <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3094_Article_IEq1.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="196" /> </InlineMediaObject> <EquationSource Format="TEX">$R_k(G)=W(L^k(G))/W(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>R</mi> <mi>k</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>W</mi> <mrow> <mo stretchy="false">(</mo> <msup> <mi>L</mi> <mi>k</mi> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">/</mo> <mi>W</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> where <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3094_Article_IEq2.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="46" /> </InlineMediaObject> <EquationSource Format="TEX">$L^k(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>L</mi> <mi>k</mi> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> denotes the k-th iterated line graph of G. Hriňáková et al. (Art Disc Appl Math:1(1): 1.09, 2018) prove that for each <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3094_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">$k\ge 3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>, the path <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3094_Article_IEq4.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">$P_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> has the smallest value of the ratio <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3094_Article_IEq5.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="23" /> </InlineMediaObject> <EquationSource Format="TEX">$R_k$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>R</mi> <mi>k</mi> </msub> </math></EquationSource> </InlineEquation> among all trees of large order n, and they conjecture that the same holds for the case <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3094_Article_IEq6.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">$k=2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>. We give a counterexample of every order <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3094_Article_IEq7.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">$n\ge 22$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>22</mn> </mrow> </math></EquationSource> </InlineEquation> to this conjecture.

On the second-order Wiener ratios of iterated line graphs

期刊论文
发表日期：

2025年1月22日

查看全文

Mohammad Ghebleh,
Ali Kanso

摘要

The Wiener index W(G) of a graph G is the sum of distances between all unordered pairs of its vertices. Dobrynin and Mel’nikov (Dist Mol Graphs Theory: 85–121, 2012) propose the study of estimates for extremal values of the ratio $R_k(G)=W(L^k(G))/W(G)$ $R_{k} (G) = W (L^{k} (G)) / W (G)$ where $L^k(G)$ $L^{k} (G)$ denotes the k-th iterated line graph of G. Hriňáková et al. (Art Disc Appl Math:1(1): 1.09, 2018) prove that for each $k\ge 3$ $k \geq 3$ , the path $P_n$ $P_{n}$ has the smallest value of the ratio $R_k$ $R_{k}$ among all trees of large order n, and they conjecture that the same holds for the case $k=2$ $k = 2$ . We give a counterexample of every order $n\ge 22$ $n \geq 22$ to this conjecture.