# Known property? Maximum radius of connected induced subgraph

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.

• What happens when H = G? Assuming G is connected. – SamiD Jan 19 '20 at 7:46
• 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. – Daniel Jan 19 '20 at 11:41
• Sorry, my mistake I somehow thought you were talking about minimum diameter. – SamiD Jan 20 '20 at 8:56
• Would that be decided by the longest induced cycle/path? – Yixin Cao Jan 20 '20 at 11:20

## 1 Answer

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.

• This is a good characterisation! Do you happen to know some if it connected to other graph characteristics or has interesting structural/algorithmical implications? – Daniel Jan 20 '20 at 15:49
• 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 – Gamow Jan 20 '20 at 16:09
• 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 – Hermann Gruber Jan 20 '20 at 20:59
• The "detour number" is what I have been looking for. It even has a connection to treedepth. Thanks to all participants! – Daniel Jan 21 '20 at 8:18