Proofs of three conjectures on the quotients of the (revised) Szeged index and the Wiener index and beyond

详细信息    查看全文

• 关键词：Wiener index ; Szeged index ; Revised Szeged index ; AutoGraphiX
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：340
• 期：3
• 页码：311-324
• 全文大小：517 K
• 卷排序：340

文摘

Let W(G),Sz(G)W(G),Sz(G) and Sz∗(G)Sz∗(G) be the Wiener index, Szeged index and revised Szeged index of a connected graph GG, respectively. Call Ln,rLn,r a lollipop   if it is obtained by identifying a vertex of CrCr with an end-vertex of Pn−r+1Pn−r+1. For a connected unicyclic graph GG with n≥4n≥4 vertices, Hansen et al. (2010) conjectured: equation(A)Sz(G)W(G)≤2−8n2+7,if n is odd,2,if n is even,equation(B)Sz∗(G)W(G)≥1+3(n2+4n−6)2(n3−7n+12),if n≤9,1+24(n−2)n3−13n+36,if n≥10,equation(C)Sz∗(G)W(G)≤2+2n2−1,if n is odd,2,if n is even,where the equality in (A) holds if and only if GG is the lollipop Ln,n−1Ln,n−1 if nn is odd, and the cycle CnCn if nn is even; the equality in (B) holds if and only if GG is the lollipop Ln,3Ln,3 if n≤9n≤9, and Ln,4Ln,4 if n≥10n≥10, whereas the equality in (C) holds if and only if GG is the cycle CnCn. In this paper, we not only confirm these conjectures but also determine the lower bound of Sz∗(G)∕W(G)Sz∗(G)∕W(G) (resp. Sz(G)∕W(G)Sz(G)∕W(G)) for cyclic graphs GG. The extremal graphs that achieve these lower bounds are characterized.