2012/11/23 by Lily Chen, Xueliang Li, Chen, Lily +3
Chemistry · Mathematics · Physics and Astronomy · #05C12 #05C35 #05C90 #92E10 #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Graph theory and applications #Synthesis and Properties of Aromatic Compounds #math.CO #msc:05C12 #msc:05C35 #msc:05C90 #msc:92E10
paper · pdf · doi:10.48550/arxiv.1211.5457
12 pages. arXiv admin note: text overlap with arXiv:1210.6460
openalex publication_date 2012/11/23 · arxiv created 2012/12/07 · arxiv updated 2012/12/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Hansen et. al. used the computer programm AutoGraphiX to study the differences between the Szeged index Sz(G) and the Wiener index W(G), and between the revised Szeged index Sz^*(G) and the Wiener index for a connected graph G. They conjectured that for a connected nonbipartite graph G with n ≥ 5 vertices and girth g ≥ 5, Sz(G)-W(G) ≥ 2n-5. Moreover, the bound is best possible as shown by the graph composed of a cycle on 5 vertices, C5, and a tree T on n-4 vertices sharing a single vertex. They also conjectured that for a connected nonbipartite graph G with n ≥ 4 vertices, Sz^*(G)-W(G) ≥ (n2+4n-6)/(4). Moreover, the bound is best possible as shown by the graph composed of a cycle on 3 vertices, C3, and a tree T on n-3 vertices sharing a single vertex. In this paper, we not only give confirmative proofs to these two conjectures but also characterize those graphs that achieve the two lower bounds.