We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On a conjecture about the existence of isometric subgraphs.
- Authors
Khalifeh, M. H.; Zahedi, Emad
- Abstract
It has been conjectured that for an n‐vertex graph G, if δ(G)>0.5n, then G has at least one isometric subgraph of every possible order. On the other hand, it is known that δ(G)>β⋅n, for any β<.5, does not guarantee that G has this property. A graph having an isometric subgraph of every order will be called distance preserving graph. The best bound in the literature is δ(G)≥23n, which guarantees that the graph G is distance preserving. In this paper, using a combinatorial method, it is proved that for every ϵ>0 there is an integer N such that every graph G with n≥N vertices and δ(G)≥(0.5+ϵ)n is distance preserving.
- Subjects
LOGICAL prediction; INTEGERS; ISOMETRICS (Mathematics); CANNING &; preserving; DISTANCES
- Publication
Journal of Graph Theory, 2020, Vol 94, Issue 2, p299
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.22521