I'll start with a couple important definitions. I'm not sure how well-known any of them are.

Firstly, if $G$ is a graph, and $u, v \in V(G)$, say that $u$ is maximally distant from $v$, denoted $u\ MD\ v$, if $d(u, v) \geq d(n, v)$ for any $n \in N(u)$, the open neighbourhood of $u$. Say that $u$ and $v$ are mutually maximally distant if $u\ MD\ v$ and $v\ MD\ u$, and denote this by $u\ MMD\ v$.

Now define the strong resolving graph of $G$, denoted $G_{SR}$, to be such that $V(G_{SR}) = V(G)$ and $(u, v) \in E(G_{SR}) \iff u\ MMD\ v$.

Next, define a cycle with non-crossing chords to be a cycle graph along with any number of chords such that it is outerplanar. Alternatively these are just the outerplanar hamiltonian graphs.

Finally, on to the problem. Are there any classes of graphs which anyone thinks can easily (or not-so-easily) be shown to contain, be contained in, or be equivalent to the class of strong resolving graphs of cycles with non-crossing chords?

I have been able to show that this class of graphs contains arbitrary odd cycles, along with induced copies of $K_n$ for any $n$, and I even found one containing an induced copy of $K_{2,3}$.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.