3
$\begingroup$

Imagine a graph $G$ with unlabeled vertices and unlabeled edges, and where we have an arbitrary vertex pair $(v_1,v_2)$. Let $k$ be the length of the shortest edge-wise path between $v_1$ and $v_2$. If $G$ is an $N$-dimensional hypercube, I believe we can say that $k$ uniquely defines these vertices up to isomorphisms of the graph.

Is there a specific name for the family of graphs with this sort of property?

$\endgroup$

1 Answer 1

0
$\begingroup$

These are the distance-transitive graphs. Apparently the hypercube graphs are the simplest asymptotic families of such graphs, but other infinite families are known: e.g., the square rook's graphs.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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