 Graphs preserving Wiener index upon vertex removalMartin Knor, Snježana Majstorović and Riste Škrekovski Applied Mathematics and Computation, 2018, vol. 338, issue C, 25-32 Abstract: The Wiener index W(G) of a connected graph G is defined as the sum of distances between all pairs of vertices in G. In 1991, Šoltés posed the problem of finding all graphs G such that the equality W(G)=W(G−v) holds for all their vertices v. Up to now, the only known graph with this property is the cycle C11. Our main object of study is a relaxed version of this problem: Find graphs for which Wiener index does not change when a particular vertex v is removed. In an earlier paper we have shown that there are infinitely many graphs with the vertex v of degree 2 satisfying this property. In this paper we focus on removing a higher degree vertex and we show that for any k ≥ 3 there are infinitely many graphs with a vertex v of degree k satisfying W(G)=W(G−v). In addition, we solve an analogous problem if the degree of v is n−1 or n−2. Furthermore, we prove that dense graphs cannot be a solutions of Šoltes’s problem. We conclude that the relaxed version of Šoltés’s problem is rich with a solutions and we hope that this can provide an insight into the original problem of Šoltés. Keywords: Wiener index; Transmission; Diameter; Pendant vertex; Induced subgraph; Dense graph (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:338:y:2018:i:c:p:25-32 DOI: 10.1016/j.amc.2018.05.047 Access Statistics for this article Applied Mathematics and Computation is currently edited by Theodore Simos More articles in Applied Mathematics and Computation from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.