On graphs whose Wiener complexity equals their order and on Wiener index of asymmetric graphs

摘要

If u is a vertex of a graph G, then the transmission of u is the sum of distances from u to all the other vertices of G. The Wiener complexity CW(G) of G is the number of different complexities of its vertices. G is transmission irregular if CW(G)=n(G). It is proved that almost no graphs are transmission irregular. Let Tn1,n2,n3 be the tree obtained from paths of respective lengths n1, n2, and n3, by identifying an end-vertex of each of them. It is proved that T1,n2,n3 is transmission irregular if and only if n3=n2+1 and n2∉{(k2−1)/2,(k2−2)/2} for some k ≥ 3. It is also proved that if T is an asymmetric tree of order n, then the Wiener index of T is bounded by (n3−13n+48)/6 with equality if and only if T=T1,2,n−4. A parallel result is deduced for asymmetric uni-cyclic graphs.