For all n ≥ k ≥ 1, every maximal k-degenerate graph has Wiener index at least n^2 - (k+1)n + k(k+1)/2 and at most sum_{i=0}^{floor((n-2)/k)} C(n-ik,2), and for k-trees with n ≥ 2k+2 the upper bound is attained only by P_n^k.
Wiener Index and Remoteness in Triangulations and Quadrangulations
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
Let $G$ be a a connected graph. The Wiener index of a connected graph is the sum of the distances between all unordered pairs of vertices. We provide asymptotic formulae for the maximum Wiener index of simple triangulations and quadrangulations with given connectivity, as the order increases, and make conjectures for the extremal triangulations and quadrangulations based on computational evidence. If $\overline{\sigma}(v)$ denotes the arithmetic mean of the distances from $v$ to all other vertices of $G$, then the remoteness of $G$ is defined as the largest value of $\overline{\sigma}(v)$ over all vertices $v$ of $G$. We give sharp upper bounds on the remoteness of simple triangulations and quadrangulations of given order and connectivity.
fields
math.CO 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Wiener indices of maximal $k$-degenerate graphs
For all n ≥ k ≥ 1, every maximal k-degenerate graph has Wiener index at least n^2 - (k+1)n + k(k+1)/2 and at most sum_{i=0}^{floor((n-2)/k)} C(n-ik,2), and for k-trees with n ≥ 2k+2 the upper bound is attained only by P_n^k.