The maximum Wiener index of maximal planar graphs
- PDF / 483,766 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 88 Downloads / 196 Views
The maximum Wiener index of maximal planar graphs Debarun Ghosh1 · Ervin Gyori ˝ 1,2 · Addisu Paulos1,3 · Nika Salia1,2 Oscar Zamora1,4
·
Accepted: 22 September 2020 / Published online: 3 October 2020 © The Author(s) 2020
Abstract The Wiener index of a connected graph is the sum of the distances between all pairs of vertices in the graph. It was conjectured that the Wiener index of an n-vertex maximal 1 (n 3 + 3n 2 ). We prove this conjecture and determine the planar graph is at most 18 unique n-vertex maximal planar graph attaining this maximum, for every n ≥ 10. Keywords Wiener index · Planar graphs · Triangulation · Distance · Mini–Max
1 Introduction The Wiener index is a graph invariant based on distances in the graph. For a connected graph G, the Wiener index is the sum of distances between all unordered pairs of vertices in the graph and is denoted by W (G). That means, W (G) =
dG (u, v).
{u,v}⊆V (G)
B
Nika Salia [email protected] Debarun Ghosh [email protected] Ervin Gy˝ori [email protected] Addisu Paulos [email protected] Oscar Zamora [email protected]
1
Central European University, Budapest, Hungary
2
Alfréd Rényi Institute of Mathematics, Budapest, Hungary
3
Addis Ababa University, Addis Ababa, Ethiopia
4
Universidad de Costa Rica, San José, Costa Rica
123
1122
Journal of Combinatorial Optimization (2020) 40:1121–1135
where dG (u, v) denotes the distance from u to v i.e. the minimum length of a path from u to v in the graph G. It was first introduced by Wiener (1947) while studying its correlations with boiling points of paraffin considering its molecular structure. Since then, it has been one of the most frequently used topological indices in chemistry, as molecular structures are usually modelled as undirected graphs. Many results on the Wiener index and closely related parameters such as the gross status (Harary 1959), the distance of graphs (Entringer et al. 1976), and the transmission (Šoltés 1991) have been studied. A great deal of knowledge on the Wiener index is accumulated in several survey papers (Dobrynin et al. 2001, 2002; Dobrynin Mel’nikov 2012; Knor and Škrekovski 2014; Xu et al. 2014). Finding a sharp bound on the Wiener index for graphs under some constraints has been one of the research topics attracting many researchers. The most basic upper bound of W (G) states that, if G is a connected graph of order n, then (n − 1)n(n + 1) , (1) W (G) ≤ 6 which is attained only by a path (Dankelmann et al. 2008a; Plesník 1984; Lovász 1979). Many sharp or asymptotically sharp bounds on W (G) in terms of other graph parameters are known, for instance, minimum degree (Beezer et al. 2001; Dankelmann and Entringer 2000; Kouider and Winkler 1997), connectivity (Dankelmann et al. 2009; Favaron et al. 1989), edge-connectivity (Dankelmann et al. 2008b, a) and maximum degree (Fischermann et al. 2002). For finding more details in mathematical aspect of Wiener index, see also results (Das and Nadjafi-Arani 2017; Gutman et al. 2014; Klavžar and Nadjafi-Ar
Data Loading...
