I was wondering if the following graph property has a name and has been researched: Consider any connected induced subgraph $H \subseteq G$. Then $r(G)$ denotes the maximum radius of any such $H$.

I think it is an interesting property since graphs with bounded $r(G)$ are closed under taking induced subgraphs whereas graphs of bounded radius are not.

Edit: The reason why I am only interested in induced subgraphs is that it otherwise would degenerate to the length of the longest (not necessarily) induced path.

  • $\begingroup$ What happens when H = G? Assuming G is connected. $\endgroup$ – SamiD Jan 19 '20 at 7:46
  • 1
    $\begingroup$ I am not sure what you mean exactly. Consider the example where G is a wheel of size n+1, then G has radius 1. When you consider the induced subgraph without the Apex it has radius n/2. Hence r(G) >=n/2. $\endgroup$ – Daniel Jan 19 '20 at 11:41
  • $\begingroup$ Sorry, my mistake I somehow thought you were talking about minimum diameter. $\endgroup$ – SamiD Jan 20 '20 at 8:56
  • 7
    $\begingroup$ Would that be decided by the longest induced cycle/path? $\endgroup$ – Yixin Cao Jan 20 '20 at 11:20

The property $\Pi_r$, defined as containing exactly the graphs $G$ such that every induced subgraph $H$ of $G$ has diameter at most $r$, is the same as the class of graphs that do not contain a $P_{r+2}$ as induced subgraph, where the $P_{r+2}$ is the path on $r+2$ vertices.

The equivalence can be seen as follows. The two degree-one vertices in the $P_{r+2}$ have a distance of $r+1$. Hence, if $G$ contains a subgraph isomorphic to the $P_{r+2}$, then $G$ does not fulfill $\Pi_r$. Conversely, if $G$ does not fulfill $\Pi_r$, then $G$ has an induced subgraph $H$ containing two vertices $u$ and $v$ such that the distance between $u$ and $v$ in $H$ is at least $r+1$. Take the vertex set $P$ of a shortest path between $u$ and $v$ in $H$. Since $P$ is a shortest path, $G[P]$ is an induced path, that is, it is isomorphic to some $P_\ell$. Since $u$ and $v$ have distance at least $r+1$ in $G[P]$, we have $\ell\ge r+2$. Hence $G$ contains $P_{r+2}$ as an induced subgraph.

  • $\begingroup$ This is a good characterisation! Do you happen to know some if it connected to other graph characteristics or has interesting structural/algorithmical implications? $\endgroup$ – Daniel Jan 20 '20 at 15:49
  • 3
    $\begingroup$ There are lots of results on graphs without induced $P_4$ (which are called co-graphs) and on graphs without induced $P_5$; see for instance graphclasses.org/classes/gc_151.html and graphclasses.org/classes/gc_396.html $\endgroup$ – Gamow Jan 20 '20 at 16:09
  • 1
    $\begingroup$ The Wikipedia article on induced paths refers to a quite a bunch of results on graphs with bounded induced path length: en.m.wikipedia.org/wiki/Induced_path $\endgroup$ – Hermann Gruber Jan 20 '20 at 20:59
  • $\begingroup$ The "detour number" is what I have been looking for. It even has a connection to treedepth. Thanks to all participants! $\endgroup$ – Daniel Jan 21 '20 at 8:18

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.