# 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. Jan 19, 2020 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. Jan 19, 2020 at 11:41
• Sorry, my mistake I somehow thought you were talking about minimum diameter. Jan 20, 2020 at 8:56
• Would that be decided by the longest induced cycle/path? Jan 20, 2020 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.
• 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 Jan 20, 2020 at 16:09