Disproof of a conjecture on the minimum Wiener index of signed trees

2022/08/03 by Songlin Guo, Wei Wang, Guo, Songlin +3
Chemistry · Mathematics · Physics and Astronomy · #05C09 #05C22 #Combinatorics #Combinatorics (math.CO) #Complex Network Analysis Techniques #Computer science #Conjecture #Connectivity #Counterexample #Discrete mathematics #FOS: Mathematics #Graph #Graph theory and applications #Index (typography) #Mathematics #Path (computing) #Synthesis and Properties of Aromatic Compounds #Topological index #Wiener index

paper · pdf · doi:10.48550/arxiv.2208.01984

openalex publication_date 2022/08/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

Abstract

The Wiener index of a connected graph is the sum of distances between all unordered pairs of vertices. Sam Spiro [The Wiener index of signed graphs, Appl. Math. Comput., 416(2022)126755] recently introduced the Wiener index for a signed graph and conjectured that the path P_n with alternating signs has the minimum Wiener index among all signed trees with n vertices. By constructing an infinite family of counterexamples, we prove that the conjecture is false whenever n is at least 30.

Related

• The Wiener Index of Signed Graphs
• On inverse Wiener interval problem of trees
• The structure of graphs with given number of blocks and the maximum Wiener index
• Wiener index of graphs with fixed number of pendant or cut vertices
• Bounding the k-Steiner Wiener and Wiener-type indices of trees in terms of eccentric sequence