Name
Abstract | ||
|---|---|---|
The Wiener index (the distance) of a connected graph is the sum of distances between all pairs of vertices. In this paper, we study the maximum possible value of this invariant among graphs on n vertices with fixed number of blocks p. It is known that among graphs on n vertices that have just one block, the n-cycle has the largest Wiener index. And the n-path, which has $$n-1$$ blocks, has the maximum Wiener index in the class of graphs on n vertices. We show that among all graphs on n vertices which have $$p\ge 2$$ blocks, the maximum Wiener index is attained by a graph composed of two cycles joined by a path (here we admit that one or both cycles can be replaced by a single edge, as in the case $$p=n-1$$ for example). |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s10878-019-00462-6 | Journal of Combinatorial Optimization |
Keywords | Field | DocType |
Graph theory, Wiener index, Distance | Graph,Discrete mathematics,Combinatorics,Wiener index,Vertex (geometry),Invariant (mathematics),Connectivity,Mathematics | Journal |
Volume | Issue | ISSN |
39 | 1 | 1382-6905 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stéphane Bessy | 1 | 117 | 19.68 |
| François Dross | 2 | 10 | 5.83 |
| Katarína Hrináková | 3 | 0 | 0.34 |
| Martin Knor | 4 | 119 | 28.90 |
| Riste Škrekovski | 5 | 607 | 83.39 |