Name
Abstract | ||
|---|---|---|
The transmission of a vertex v of a graph G is the sum of distances from v to all the other vertices in G. The Wiener complexity of G is the number of different transmissions of its vertices. Similarly, the eccentric complexity of G is defined as the number of different eccentricities of its vertices. In this paper these two complexities are compared. The complexities are first studied on Cartesian product graphs. Transmission indivisible graphs and arithmetic transmission graphs are introduced to demonstrate sharpness of upper and lower bounds on the Wiener complexity, respectively. It is shown that for almost all graphs the Wiener complexity is not smaller than the eccentric complexity. This property is proved for trees, the equality holding precisely for center-regular trees. Several families of graphs in which the complexities are equal are constructed. Using the Cartesian product, it is proved that the eccentric complexity can be arbitrarily larger than the Wiener complexity. Additional infinite families of graphs with this property are constructed by amalgamating universally diametrical graphs with center-regular trees. (C) 2020 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1016/j.dam.2020.11.020 | DISCRETE APPLIED MATHEMATICS |
Keywords | DocType | Volume |
Graph distance, Wiener complexity, Eccentric complexity, Cartesian product of graphs, Graph of diameter 2 | Journal | 290 |
ISSN | Citations | PageRank |
0166-218X | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kexiang Xu | 1 | 72 | 11.43 |
| Aleksandar Ilic | 2 | 0 | 0.34 |
| Vesna Irsic | 3 | 3 | 2.87 |
| Sandi Klavžar | 4 | 738 | 84.46 |
| Huimin Li | 5 | 0 | 0.34 |