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.

Improve this question
$\endgroup$
1
  • $\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
    Commented Mar 24, 2020 at 15:44

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .