2
$\begingroup$

Is there an established name for cycles $C\subseteq G(V,E)$ with the property that
$$\lbrace u,v\rbrace\subseteq C\cap V\implies\mathrm{dist}_{|C}(u,v)\le \mathrm{dist}_{|G}(u,v)$$

I would be tempted to call them facets because vertices and edges that constitute to the boundary of a facet of a polyhedron are prototypical examples of such cycles.

$\endgroup$
  • $\begingroup$ @MarkSapir the term convex subgraph exists but has a slightly different meaning: all shortest paths from $G$ must me in $C$. $\endgroup$ – M. Winter Mar 24 at 15:44
5
$\begingroup$

You are looking for the following:

Definition. A subgraph $H\subseteq G$ is called isometric if $\mathrm{dist}_H(u,v)=\mathrm{dist}_G(u,v)$ for all $u,v\in V(H)$.

So your cycles could be called isometric cycles.


Note that not all facets of a polyhedron are induced in this sense. Consider the a $2n$-gonal pyramid for some $n\ge 3$. Two antipodal vertices of the $2n$-gonal face $C$ have distance $n$ along $C$, but only distance two in the pyramid (via the apex vertex).

| cite | improve this answer | |
$\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.