Abstract

The Steiner 3-Szeged index, denoted by 𝑆𝑆𝑧3(𝐺) is a distance-based graph invariant defined using Voronoi-type partitions of vertex subsets. Closed-form formulas are known for several standard graph families; however, the extremal behaviour of SSz₃ over the full class of trees, and its behaviour under graph operations such as the corona product, have not previously been determined. 𝑆𝑆𝑧3(𝐺)

This paper establishes a complete characterization of extremal trees with respect to 𝑆𝑆𝑧3. A phase transition occurs at 𝑛 = 4: among trees on four vertices, the path 𝑃₄ is the unique minimiser, while the star 𝐾₁,₃ is the unique maximiser. For all 𝑛 ≥ 5, these roles are reversed — the star 𝐾₁,ₙ₋₁ becomes the unique minimiser and the path 𝑃ₙ becomes the unique maximiser.

In addition, explicit expressions for 𝑆𝑆𝑧₃ are derived for two families of corona graphs. Specifically, a closed-form formula is derived for 𝐾₁,ₙ ∘ 𝐾₁ , together with a structural decomposition for 𝑃ₙ ∘ 𝐾₁ based on a classification of Voronoi configurations.

These findings extend existing results on Steiner distance-based indices and offer further insight into the relationship between graph structure and Voronoi-type partitions, with potential relevance to chemical graph theory and network analysis.

Keywords

Corona graphs, Graph invariants, Trees, Voronoi partitions, Wiener-type indices.

References

[1] I. Gutman, “A Formula for the Wiener Number of Trees,” Graph Theory Notes, vol. 27, pp. 9-15, 1994.
[Google Scholar]

[2] Modjtaba Ghorbani et al., “Steiner (Revised) Szeged Index of Graphs,” MATCH Communications in Mathematical and in Computer Chemistry, vol. 82, pp. 733-742, 2019.
[Google Scholar] [Publisher Link]

[3] Xueliang Li, and Meiqiao Zhang, “Results on Two Kinds of Steiner Distance-Based Indices for Some Graph Families,” MATCH Communications in Mathematical and in Computer Chemistry, vol. 84, pp. 567–578, 2020.
[Google Scholar] [Publisher Link]

[4] Sandi Klavžar, and M.J. Nadjafi-Arani, “Improved Bounds on the Difference between the Szeged Index and the Wiener Index of Graphs,” European Journal of Combinatorics, vol. 39, pp. 148-156, 2014.
[CrossRef] [Google Scholar] [Publisher Link]

[5] Harry Wiener, “Structural Determination of Paraffin Boiling Points,” Journal of the American Chemical Society, vol. 69, pp. 17-20, 1947.
[CrossRef] [Google Scholar] [Publisher Link]

[6] Gary Chartrand et al., “Steiner Distance in Graphs,” A Magazine for Cultivating Mathematics, vol. 114, pp. 399-410, 1989.
[Google Scholar] [Publisher Link]

[7]  Xueliang Li, Yaping Mao, and Ivan Gutman, “The Steiner Wiener Index of a Graph,” Discussiones Mathematicae Graph Theory, vol. 36, pp. 455-465, 2016.
[CrossRef] [Google Scholar] [Publisher Link]

[8] Yaping Maoa, and Boris Furtula, “Steiner Distance in Chemical Graph Theory,” MATCH Communications in Mathematical and in Computer Chemistry, vol. 86, pp. 211-287, 2021.
[Google Scholar] [Publisher Link]

[9] Mengmeng Liu, and Kinkar Chandra Das, “On the Steiner (Revised) Szeged Index,” MATCH Communications in Mathematical and in Computer Chemistry, vol. 84, pp. 579-594, 2020.
[Google Scholar] [Publisher Link]