<p>I don't have an answer for your whole class of graphs, but three subclasses of graphs that have this property are the <a href="https://en.wikipedia.org/wiki/Distance-hereditary_graph" rel="nofollow">distance-hereditary graphs</a>, <a href="https://en.wikipedia.org/wiki/Chordal_graph" rel="nofollow">chordal graphs</a>, and <a href="https://en.wikipedia.org/wiki/Median_graph" rel="nofollow">median graphs</a>. </p>

<p>Distance-hereditary graphs are defined by the property that every connected induced subgraph has the same distances. So you can pick an arbitrary starting vertex $v_1$ and then choose each successive vertex to be any not-already-chosen vertex that is adjacent to a previously-chosen vertex.</p>

<p>The chordal graphs are the graphs that have an ordering with the property that each successive vertex, when added, has a clique for its neighbors. This ordering is obviously distance-preserving.</p>

<p>Similarly, median graphs (including your grid example) have the property that, for any breadth-first ordering, each vertex has a hypercube neighborhood at the time it is added. (See pages 76–77 of Eppstein et al, "Media Theory", Springer, 2008). Again, this property means that the addition cannot change the distances among the previous vertices.</p>

<p>There's a class of graphs that I don't know a name for, generalizing both chordal and distance-hereditary graphs, that can be recognized in polynomial time and that have your property. They are the connected graphs that can be built up from a single vertex by adding vertices one by one, where the neighbors of each new vertex are a subset of one of the closed neighborhoods of the previous graph. They are almost (but not quite) the same as the <a href="http://www.graphclasses.org/classes/gc_49.html" rel="nofollow">dismantlable graphs</a>, the difference being that the new vertex does not have to be adjacent to the vertex whose neighborhood is being copied. An elimination ordering of a chordal graph is a construction of this type where each new vertex chooses a clique subset of a neighborhood. Similarly distance-hereditary graphs have a construction of this type where the neighbors of each new vertex are an entire closed neighborhood, an open neighborhood, or a single vertex. Each new vertex can't change the distances of the previous vertices, so this construction sequence has the property you're looking for.</p>

<p>If you define a vertex v to be "removable" if it could be the last one in this sequence (it has an open neighborhood that is a subset of someone else's closed neighborhood) then removing other removable vertices doesn't change the removability of v: if v's neighborhood is a subset of u's, and we remove u as having a neighborhood that is a subset of w's, then v is still removable because its neighborhood is still a subset of w's. Therefore, the sequences of removal steps that we can follow to take a graph back down to nothing form an <a href="https://en.wikipedia.org/wiki/Antimatroid" rel="nofollow">antimatroid</a>, and one such sequence can be found in polynomial time by a greedy algorithm that repeatedly removes a removable vertex whenever it can find one. Reversing the output of this algorithm gives the construction sequence for the given graph. The graph of the cube gives an example of a graph that has your property (a median graph) but is not constructible in this way. I think the median graphs that can be constructed in this way are exactly the <a href="https://en.wikipedia.org/wiki/Squaregraph" rel="nofollow">squaregraphs</a> (which include the regular grids). The graphs that have a construction sequence of this type also include all graphs that have a universal vertex, such as the <a href="https://en.wikipedia.org/wiki/Wheel_graph" rel="nofollow">wheel graphs</a>, so (unlike chordal graphs and distance-hereditary graphs) they are not perfect and not closed under induced subgraphs.</p>

CC BY-SA 3.0
2016-08-18T09:00:26.497Z
the property of this class of graphs you aren't sure of is reminiscent of a domination elimination ordering. This paper seems relevant to the original question: http://epubs.siam.org/doi/abs/10.1137/S0895480195291230?journalCode=sjdmec
JimN
CC BY-SA 3.0
2016-08-18T16:15:04.230Z
I think the dominatlon elimination ordering may be the same thlng as dlsmantlability. But you should link that paper in an actual answer, because its "distance-preserving elimination ordering" seems to be exactly what the original question is asking for.
David Eppstein
CC BY-SA 3.0
2016-08-10T20:33:05.507Z
2016-08-17T21:30:14.923Z
2016-08-17T21:30:14.923Z
David Eppstein
<p>It would seem you are asking about graphs admitting a <em>distance-preserving elimination ordering</em> which forms a class of graphs studied in this paper:</p>

<p><a href="http://epubs.siam.org/doi/abs/10.1137/S0895480195291230?journalCode=sjdmec">http://epubs.siam.org/doi/abs/10.1137/S0895480195291230?journalCode=sjdmec</a></p>

CC BY-SA 3.0
2016-08-31T14:40:33.280Z
Also available freely on the author's webpage: http://www.lif-sud.univ-mrs.fr/%7Echepoi/dpo.ps
Florent Foucaud
CC BY-SA 3.0
2016-08-29T04:55:12.780Z
2016-08-30T06:50:36.253Z
2016-08-30T06:50:36.253Z
JimN
<p>Let us say that a graph $G$ has the property $M$ if its vertices can be ordered $v_1, v_2, \ldots v_n$ in such a way that the graph $H_i$ induced by the vertices $\{v_1, \ldots, v_i\}$ has $dist_{H_i} (v_j, v_k) = dist_G(v_j, v_k)$ for all $j,k \leq i$. In other words adding the next vertex in our ordering does not affect the distance metric of the current graph.</p>

<p>An example of such a graph is the regular $n \times n$ grid.</p>

<p>Does this property or class of graphs have a name? Have they been studied?</p>

CC BY-SA 3.0
2016-08-10T16:06:03.023Z
A simple example of a graph that does *not* have this property is the $k$-cycle for $k \ge 5$. This is because, for any ordering, the subgraphs $H_i$ have to be connected, and so at time $i = \lfloor k/2 \rfloor +2 < k$, $H_i$ is a line of length $i-1$, and so some two vertices are distance $i-1 > \lfloor k/2 \rfloor$ apart.
Andrew Morgan
CC BY-SA 3.0
2016-08-10T16:17:07.853Z
On the other hand, a natural candidate for finding a good order $v_1, \ldots, v_n$ is to do a BFS from an arbitrary choice of $v_1$. By viewing $G$ as the BFS tree with some extra edges, it seems like the only obstruction to having property $M$ is for there to be something "like" a $k$-cycle for $k \ge 5$ in $G$. By "like" I mean there is a $k$-cycle $v_1, \ldots, v_k, v_{k+1}=v_1$ with $k \ge 5$ so that $d(v_i,v_j) = |i-j|$ in $G$. If we call such a cycle "minimal", then is it true that property $M$ is equivalent to the nonexistence of minimal cycles of length at least 5?
Andrew Morgan
CC BY-SA 3.0
2016-08-10T21:01:32.217Z
A cube has an induced and isometric 6-cycle (remove two opposite vertices of the cube; what's left is the 6-cycle) but can be ordered in a distance-preserving way (e.g. BFS). So your $k$-cycles are not always obstacles. This example also shows that greedily removing vertices that preserve distances can get stuck, even when some other ordering works.
David Eppstein
<reference-request><graph-theory>
Reference for a class of graphs that preserve subgraph distances when ordered
aellab
# Reference for a class of graphs that preserve subgraph distances when ordered

(Asked by: username_0 on 2016-08-10)

Let us say that a graph $G$ has the property $M$ if its vertices can be ordered $v\_1, v\_2, \ldots v\_n$ in such a way that the graph $H\_i$ induced by the vertices $\{v\_1, \ldots, v\_i\}$ has $dist\_{H\_i} (v\_j, v\_k) = dist\_G(v\_j, v\_k)$ for all $j,k \leq i$. In other words adding the next vertex in our ordering does not affect the distance metric of the current graph.

An example of such a graph is the regular $n \times n$ grid.

Does this property or class of graphs have a name? Have they been studied?

**Tags:** reference-request, graph-theory
> **Comments:**
> **username_1**: A simple example of a graph that does *not* have this property is the $k$-cycle for $k \ge 5$. This is because, for any ordering, the subgraphs $H_i$ have to be connected, and so at time $i = \lfloor k/2 \rfloor +2 < k$, $H_i$ is a line of length $i-1$, and so some two vertices are distance $i-1 > \lfloor k/2 \rfloor$ apart.  
> **username_1**: On the other hand, a natural candidate for finding a good order $v_1, \ldots, v_n$ is to do a BFS from an arbitrary choice of $v_1$. By viewing $G$ as the BFS tree with some extra edges, it seems like the only obstruction to having property $M$ is for there to be something "like" a $k$-cycle for $k \ge 5$ in $G$. By "like" I mean there is a $k$-cycle $v_1, \ldots, v_k, v_{k+1}=v_1$ with $k \ge 5$ so that $d(v_i,v_j) = |i-j|$ in $G$. If we call such a cycle "minimal", then is it true that property $M$ is equivalent to the nonexistence of minimal cycles of length at least 5?  
> **username_2**: A cube has an induced and isometric 6-cycle (remove two opposite vertices of the cube; what's left is the 6-cycle) but can be ordered in a distance-preserving way (e.g. BFS). So your $k$-cycles are not always obstacles. This example also shows that greedily removing vertices that preserve distances can get stuck, even when some other ordering works.  

---

## 2 answers

### Answer by username_3 on 2016-08-29. Score: 8 | Accepted answer

It would seem you are asking about graphs admitting a *distance-preserving elimination ordering* which forms a class of graphs studied in this paper:

<http://epubs.siam.org/doi/abs/10.1137/S0895480195291230?journalCode=sjdmec>

> **Comments:**
> **username_4**: Also available freely on the author's webpage: http://www.lif-sud.univ-mrs.fr/%7Echepoi/dpo.ps  

---

### Answer by username_2 on 2016-08-10. Score: 8

I don't have an answer for your whole class of graphs, but three subclasses of graphs that have this property are the [distance-hereditary graphs](https://en.wikipedia.org/wiki/Distance-hereditary_graph), [chordal graphs](https://en.wikipedia.org/wiki/Chordal_graph), and [median graphs](https://en.wikipedia.org/wiki/Median_graph).

Distance-hereditary graphs are defined by the property that every connected induced subgraph has the same distances. So you can pick an arbitrary starting vertex $v\_1$ and then choose each successive vertex to be any not-already-chosen vertex that is adjacent to a previously-chosen vertex.

The chordal graphs are the graphs that have an ordering with the property that each successive vertex, when added, has a clique for its neighbors. This ordering is obviously distance-preserving.

Similarly, median graphs (including your grid example) have the property that, for any breadth-first ordering, each vertex has a hypercube neighborhood at the time it is added. (See pages 76–77 of Eppstein et al, "Media Theory", Springer, 2008). Again, this property means that the addition cannot change the distances among the previous vertices.

There's a class of graphs that I don't know a name for, generalizing both chordal and distance-hereditary graphs, that can be recognized in polynomial time and that have your property. They are the connected graphs that can be built up from a single vertex by adding vertices one by one, where the neighbors of each new vertex are a subset of one of the closed neighborhoods of the previous graph. They are almost (but not quite) the same as the [dismantlable graphs](http://www.graphclasses.org/classes/gc_49.html), the difference being that the new vertex does not have to be adjacent to the vertex whose neighborhood is being copied. An elimination ordering of a chordal graph is a construction of this type where each new vertex chooses a clique subset of a neighborhood. Similarly distance-hereditary graphs have a construction of this type where the neighbors of each new vertex are an entire closed neighborhood, an open neighborhood, or a single vertex. Each new vertex can't change the distances of the previous vertices, so this construction sequence has the property you're looking for.

If you define a vertex v to be "removable" if it could be the last one in this sequence (it has an open neighborhood that is a subset of someone else's closed neighborhood) then removing other removable vertices doesn't change the removability of v: if v's neighborhood is a subset of u's, and we remove u as having a neighborhood that is a subset of w's, then v is still removable because its neighborhood is still a subset of w's. Therefore, the sequences of removal steps that we can follow to take a graph back down to nothing form an [antimatroid](https://en.wikipedia.org/wiki/Antimatroid), and one such sequence can be found in polynomial time by a greedy algorithm that repeatedly removes a removable vertex whenever it can find one. Reversing the output of this algorithm gives the construction sequence for the given graph. The graph of the cube gives an example of a graph that has your property (a median graph) but is not constructible in this way. I think the median graphs that can be constructed in this way are exactly the [squaregraphs](https://en.wikipedia.org/wiki/Squaregraph) (which include the regular grids). The graphs that have a construction sequence of this type also include all graphs that have a universal vertex, such as the [wheel graphs](https://en.wikipedia.org/wiki/Wheel_graph), so (unlike chordal graphs and distance-hereditary graphs) they are not perfect and not closed under induced subgraphs.

> **Comments:**
> **username_3**: the property of this class of graphs you aren't sure of is reminiscent of a domination elimination ordering. This paper seems relevant to the original question: http://epubs.siam.org/doi/abs/10.1137/S0895480195291230?journalCode=sjdmec  
> **username_2**: I think the dominatlon elimination ordering may be the same thlng as dlsmantlability. But you should link that paper in an actual answer, because its "distance-preserving elimination ordering" seems to be exactly what the original question is asking for.  

---

