12
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Andrew Morgan
    Commented Aug 10, 2016 at 16:06
  • $\begingroup$ 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? $\endgroup$
    – Andrew Morgan
    Commented Aug 10, 2016 at 16:17
  • 1
    $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Commented Aug 10, 2016 at 21:01

2 Answers 2

Reset to default
8
$\begingroup$

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

Improve this answer
$\endgroup$
1
8
$\begingroup$

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, chordal graphs, and median graphs.

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, 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, 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 (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, so (unlike chordal graphs and distance-hereditary graphs) they are not perfect and not closed under induced subgraphs.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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: epubs.siam.org/doi/abs/10.1137/… $\endgroup$
    – JimN
    Commented Aug 18, 2016 at 9:00
  • $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Commented Aug 18, 2016 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.