Source-linked AI summary
Mathematical aspects of Wiener index
Martin Knor, Riste Škrekovski, Aleksandra Tepeh
TL;DR
The paper addresses mathematical questions surrounding the Wiener index, a distance-based molecular descriptor whose graph-theoretic properties support chemical applications. It synthesizes results, conjectures, and open problems, emphasizing the authors’ work. The paper establishes foundational relations and extremal results while identifying unresolved limits and additional inverse-problem families.
Problem
The paper examines mathematical properties, values, extremal behavior, and unresolved problems for the Wiener index, a molecular descriptor defined from graph distances.
Method
The authors synthesize mathematical results, conjectures, problems, and future-work ideas, emphasizing their own work and including related open problems.
Results
The paper establishes foundational Wiener-index relations and extremal results, including tree decompositions, while presenting Theorem 7.23’s characterization of when W(Li(T)) = W(T) has a solution.
Takeaways & Limitations
The paper provides a consolidated mathematical reference while identifying conjectures and open directions for Wiener-index research.
Takeaways & Limitations
The inverse Wiener index problem remains open for graph and tree families beyond caterpillars and trees with small diameter, and analogous limits for related congruence results remain of interest.
Abstract
from arXiv · showhide
The Wiener index (i.e., the total distance or the transmission number), defined as the sum of distances between all unordered pairs of vertices in a graph, is one of the most popular molecular descriptors. In this article we summarize some results, conjectures and problems on this molecular descriptor, with emphasis on works we were involved in.
1 Introduction
The Wiener index is a molecular-graph descriptor formed by summing distances over unordered vertex pairs. This paper presents mathematical results, conjectures, problems, and related indices, emphasizing the authors’ own work.
- Molecular graphs represent atoms as vertices and bonds as edges, while topological indices are graph invariants used to predict molecular properties.
- The Wiener index, introduced in 1947 as the path number, is the oldest topological index.
- Its applications include preliminary screening of drug molecules and preliminary prediction of protein–ligand binding energy.
- Wiener index is also known as gross status, distance of graphs, or transmission, and is one of more than 200 topological indices used in chemistry.
- Wiener index is the sum of distances between all unordered pairs of vertices of a graph.
- The paper summarizes mathematical work on Wiener index while integrating conjectures, open problems, and ideas for future research.
2 Some fundamental properties of Wiener index
This section develops foundational decompositions and extremal properties of the Wiener index, especially for trees and connected graphs. It also relates the Wiener and Szeged indices.
- Wiener decomposed a tree’s index into easily calculable edge contributions.
- For a tree edge e = ij, deleting e produces components of sizes ne(i) and ne(j), so its contribution is ne(i)ne(j).
- The Wiener and Szeged indices coincide on trees; the Szeged index generalizes the tree formula by relaxing the tree condition.
- Among trees on n vertices, the path Pn maximizes Wiener index and the star Sn minimizes it.
- Among connected graphs on n vertices, the complete graph Kn has the smallest Wiener index.
- Among 2-connected graphs, and even graphs of minimum degree 2, the cycle Cn has the largest Wiener index.
3 The inverse Wiener index problem
The inverse Wiener index problem asks which integers occur as indices of graphs or trees. Results establish broad existence theorems, while remaining work seeks solutions in additional graph families.
- For every w > 10^8, a caterpillar tree exists with Wiener index w, while all but 49 integers are realized by trees of diameter at most 4.
- For every sufficiently large integer w, at least 2f(w) trees have Wiener index w.
- Further work could seek inverse-problem solutions among graph families beyond caterpillars and trees with small diameter.
- The inverse problem asks which integers w are Wiener indices of graphs or trees on n vertices.
4 Graphs with prescribed minimum/maximum degree
This section studies extremal Wiener indices under degree constraints and proposes conjectures for regular graphs. The central intuition is that diameter governs the extremal behavior when degree and edge counts are fixed.
- For n-vertex graphs with maximum degree at most Δ, the maximum Wiener index equals W(Pn), while with minimum degree at least δ, the minimum equals W(Kn).
- The section asks for the maximum index under minimum-degree constraints and the minimum index under maximum-degree constraints.
- For regular graphs, fixed edge counts make diameter especially important for comparing Wiener indices.
- The authors conjecture that among n-vertex cubic graphs, Ln has the largest Wiener index.
- Among r-regular graphs, the conjectured maximum and minimum Wiener indices are attained by graphs with maximum and minimum possible diameter, respectively.
5 Graphs with prescribed diameter/radius
The paper surveys extremal Wiener-index problems for graphs with prescribed diameter or radius. Several exact results and conjectures are known, but maximum-index questions remain open in important cases.
- Eccentricity is a vertex’s greatest distance to another vertex, while diameter and radius are respectively the maximum and minimum eccentricities.
- The maximum Wiener index for graphs of order n and diameter d remains an open problem, even under additional restrictions.
- For graphs of order 2d + 1 and diameter d > 2, Conjecture 5.2 proposes W(G) ≤ W(C2d+1).
- Known tree results cover maximum Wiener index for selected diameters, including 2 ≤ d ≤ 4 and n − 3 ≤ d ≤ n − 1.
- The paper also asks for maximum and minimum Wiener indices among graphs of order n and radius r.
- Conjecture 5.5 states that graphs Gn,r,s for s ∈ {1, ..., r − 1} minimize the Wiener index among graphs of order n and radius r.The construction begins from a 2r-cycle and replaces two vertices by cliques connected according to the stated pattern.
6 Congruence relations for Wiener index
This section surveys congruence relations for the Wiener index across structured graph classes. Results include congruences for perfect-matchable, k-proportional, T-factor, and specially assembled graphs, alongside limits and open extensions.
- For trees of the same order with perfect matchings, the Wiener indices are congruent modulo 4.
- For k-proportional trees, the Wiener indices are congruent modulo k^3.These trees have the same order, number of segments, and segment lengths divisible by k.
- For trees of the same order with P_r-factors, the Wiener indices are congruent modulo 2r when r is even.A P_r-factor is a vertex-disjoint decomposition into paths on r vertices.
- For graphs assembled from connected components H_i and connecting graphs F_j under specified order congruences, all resulting graphs have the same Wiener index modulo r.Contracting each H_i produces a tree whose supervertices are the H_i and whose superedges are the F_j.
- For the restricted tree construction with even r, the corresponding Wiener indices are congruent modulo 2r.This construction uses trees H_i with orders divisible by r and trees F_j with orders congruent to 2 modulo r.
- Theorems 6.5 and 6.6 identify limits of Theorem 6.3 and motivate conditions for congruence modulo k^3 in k-proportional graphs.
7 Wiener index and the line graph operation
The section surveys how the Wiener index changes under the line-graph operation and its iterations, establishing bounds, equality cases, extremal problems, and conjectures. It also presents families where Wiener indices coincide across iterations and identifies substantial open questions.
- Definitions: The line graph L(G) replaces vertices by edges and joins two new vertices exactly when the corresponding original edges are adjacent.Iterated line graphs are defined recursively from this operation.
- Basic inequalities: For every tree T, W(L(T)) is strictly smaller than W(T).The survey attributes the foundational result to Buckley and notes its strict inequality consequence.
- Basic inequalities: For connected unicyclic graphs, W(L(G)) ≤ W(G), with equality exactly for cycles of the same length.Among connected graphs with minimum degree at least 2, the corresponding equality case is also restricted to cycles.
- Equality and inequalities: In connected bicyclic graphs, all three relations W(L(G)) < W(G), W(L(G)) = W(G), and W(L(G)) > W(G) occur.The survey reports 26 nine-vertex bicyclic graphs and 166 ten-vertex graphs with equality.
- Bounds: The survey gives general lower-bound results for W(L(G)), including equality characterizations involving trees and complete graphs.It also records a minimum-degree version and notes that the lower bound was later improved.
- Extremal problems: Maximizing W(L(G)) remains an open problem, with dumbbell and barbell graphs conjectured as extremal candidates for general and bipartite graphs, respectively.A separate conjecture states that for large n, W(L_k(G))/W(G) is maximized by K_n and minimized by P_n for k ≥2.
- Iterated line graphs: For higher iterations, infinitely many graphs satisfy W(L(G)) = W(G), including graphs of girth h^2 + h + 9 and conjecturally graphs of every girth g ≥3.The survey also conjectures that certain constructed graphs have minimum order for a prescribed cyclomatic number.
- Iterated line graphs: For generalized t-stars, W(L^2(S)) < W(S) when t = 3 and W(L^2(S)) > W(S) when t ≥7, while equality families occur for t ∈ {4, 5, 6}.This behavior motivates a conjecture about extending any non-trivial tree satisfying equality to an infinite homeomorphic family.
8 Excursion into digraphs
The section extends Wiener-index questions to directed graphs, including orientations, reachability, and betweenness centrality. It records results for particular orientations and several open problems and conjectures about extremal values and computational complexity.
- Structural relations and problems: The section relates directed Wiener index to reachability and betweenness centrality, and asks for the complexity of finding Wmax(G) and Wmin(G).Theorem 8.2 expresses the directed index using betweenness centrality and the number of reachable ordered pairs.
- Orientations: The directed setting assigns Wmax(G) and Wmin(G) as the largest and smallest Wiener indices over all orientations of G.For non-strongly connected digraphs, unreachable directed pairs require an explicit convention.
- Orientations: Plesník proved that minimizing the Wiener index over strongly connected orientations is NP-hard, while maximum-index orientations were resolved for complete graphs.The cited complete-graph results assume strong connectivity.
- Extremal orientations: For certain Θ-graphs, a maximum-Wiener-index orientation is not strongly connected, motivating a conjecture that a directed cycle on the two longest paths attains Wmax.The section also conjectures that 2-connected chordal graphs have a strongly connected orientation attaining Wmax.
- Minimum orientations: For every graph, the authors conjecture that Wmin is achieved by an acyclic orientation; this is established for bipartite graphs, where Wmin(G)=|E(G)|.Orienting every bipartite edge from one part to the other yields the lower bound.
9 Wiener index for disconnected graphs
For disconnected graphs, the paper modifies the Wiener index by ignoring infinite-distance pairs, making the index additive across components. This yields new characterization problems for disconnected graphs and forests.
- Modified definition: The modified Wiener index excludes vertex pairs whose distance is treated as infinite, allowing disconnected graphs to be handled componentwise.The paper notes applications to disconnected hexagonal networks.
- Modified definition: For components G1,…,Gp, the modified index satisfies W(G)=W(G1)+W(G2)+···+W(Gp).This additivity follows directly from summing within-component distances.
- Open problems: The authors propose finding all Wiener-index values realizable by n-vertex graphs or forests under the modified definition.They identify this as an analogue of earlier Wiener-index value problems.
- Open problems: They also ask which forests satisfy W(Li(F))=W(F) for i≥3, contrasting with most trees and paths.Most trees satisfy W(Li(T))>W(T), whereas paths on n≥2 vertices satisfy W(Li(Pn))<W(Pn).
10 Trees with given degree conditions
This section gathers extremal Wiener-index questions for trees and graphs under degree-based constraints. Several extremal tree problems are solved or partially ordered, while corresponding graph problems remain open.
- Degree constraints: Lin characterized trees maximizing and minimizing the Wiener index among fixed-order trees whose vertices all have odd degrees.Subsequent work ordered such trees by their smallest indices and identified trees with the second through seventeenth greatest indices.
- Degree constraints: Open problems ask for extremal graphs with all vertices of odd degree or all vertices of even degree.The odd-degree case concerns graphs on 2n vertices, while the even-degree case concerns graphs on n vertices.
- Degree constraints: For graphs with exactly r even-degree vertices, the paper asks how to order trees and characterize graphs with maximal or minimal Wiener index.The class En,r has order n, exactly r even-degree vertices, r≥1, and n≡r (mod 2).
- Degree constraints: For trees with exactly k maximum-degree vertices, maximum-index trees are known, but the corresponding minimum-index characterization remains open.The open problem asks for the tree or trees of minimum Wiener index under that constraint.
- Degree constraints: The minimum-Wiener-index tree for a given degree sequence is known, whereas the maximum-index tree remains open despite extremal graphs being known to be caterpillars.The unresolved question is which tree maximizes the index among trees with a fixed degree sequence.
11 Few more problems
The paper surveys further Wiener-index problems involving Eulerian, fullerene, matching, connectivity, bipartition, and Szeged-index constraints. It records several solved extremal cases alongside conjectures and open maximum-index questions.
- Eulerian graphs: Among Eulerian graphs of order n, Cn attains the maximal Wiener index, while the second-maximal value is conjectured to be attained by Cn,3 for sufficiently large n.Cn,3 is formed by identifying one vertex of Cn−2 with one vertex of C3.
- Fullerene graphs: For (6,0)-nanotubes with 12k vertices, the Wiener index is 48k^3+828k−1632, and the paper conjectures fullerene indices have asymptotic order θ(n^3).The nanotubes’ long diameter is associated in the passage with their large Wiener index.
- Szeged index: The Szeged index satisfies Sz(G)≥W(G), with equality exactly when every block of G is complete.The paper surveys classifications based on the difference η(G)=Sz(G)−W(G) and states a further conjecture.
- Matching number: For connected graphs with prescribed matching number, maximum Wiener index is known and uniquely attained by a tree, but the unicyclic maximum remains open.The open problem asks for the maximum among unicyclic graphs with n vertices and matching number i.
- Connectivity: In k-connected graphs, the minimum Wiener index is known, while the maximum-index problem and whether vertex- and edge-connectivity extremals coincide remain open.Paths and cycles are extremal for 1-connected and 2-connected graphs, respectively.
- Bipartition: For prescribed bipartition sizes, extremal trees and minimum-index unicyclic graphs are characterized, but maximum-index unicyclic graphs remain unresolved.The open question covers unicyclic graphs on n vertices with bipartition sizes p and q.