On the minimum distance in a k-vertex set in a graph

Martin Knor and Riste Škrekovski

Applied Mathematics and Computation, 2019, vol. 356, issue C, 99-104

Abstract: Consider the smallest distance among k distinct vertices in a graph. How large can it be? Let G be a connected graph on n vertices, let k satisfy 3 ≤ k < n and let v1,v2…,vk be distinct vertices in G. We prove that there are i and j, 1 ≤ i < j ≤ k, such that dG(vi,vj)≤2n−2k. Moreover, for every k and n the subdivided k-star, with rays of lengths ⌊n−1k⌋ and ⌈n−1k⌉, is one of the extremal graphs. The special case k=2 coincides with the well-known fact that in a connected graph two vertices are on distance at most n−1, and the maximum distance is achieved for the endvertices of the path Pn. We consider also the corresponding problem for 2-connected graphs and we solve it for k=3.

Keywords: Distance; k-subset of vertices; Graph (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300319302577
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:356:y:2019:i:c:p:99-104

DOI: 10.1016/j.amc.2019.03.050

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().