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

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

CC BY-SA 4.0
2020-01-20T15:49:27.037Z
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
CC BY-SA 4.0
2020-01-20T16:09:21.087Z
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 http://www.graphclasses.org/classes/gc_151.html and http://www.graphclasses.org/classes/gc_396.html
Gamow
CC BY-SA 4.0
2020-01-20T20:59:21.293Z
The Wikipedia article on induced paths refers to a quite a bunch of results on graphs with bounded induced path length: https://en.m.wikipedia.org/wiki/Induced_path
Hermann Gruber
CC BY-SA 4.0
2020-01-21T08:18:44.957Z
The "detour number" is what I have been looking for. It even has a connection to treedepth. Thanks to all participants!
Daniel
CC BY-SA 4.0
2020-01-20T13:13:12.557Z
2020-01-20T13:13:12.557Z
Christian Komusiewicz
<p>I was wondering if the following graph property has a name and has been researched:
Consider any connected induced subgraph <span class="math-container">$H \subseteq G$</span>.
Then <span class="math-container">$r(G)$</span> denotes the maximum radius of any such <span class="math-container">$H$</span>.</p>

<p>I think it is an interesting property since graphs with bounded <span class="math-container">$r(G)$</span> are closed under taking induced subgraphs whereas graphs of bounded radius are not.</p>

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

CC BY-SA 4.0
2020-01-19T07:46:57.470Z
What happens when H = G? Assuming G is connected.
SamiD
CC BY-SA 4.0
2020-01-19T11:41:28.943Z
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
CC BY-SA 4.0
2020-01-20T08:56:11.640Z
Sorry, my mistake I somehow thought you were talking about minimum diameter.
SamiD
CC BY-SA 4.0
2020-01-20T11:20:33.050Z
Would that be decided by the longest induced cycle/path?
Yixin Cao
<graph-theory>
Known property? Maximum radius of connected induced subgraph
Daniel
# Known property? Maximum radius of connected induced subgraph

(Asked by: username_0 on 2020-01-17)

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.

**Tags:** graph-theory
> **Comments:**
> **username_1**: What happens when H = G? Assuming G is connected.  
> **username_0**: 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.  
> **username_1**: Sorry, my mistake I somehow thought you were talking about minimum diameter.  
> **username_2**: Would that be decided by the longest induced cycle/path?  

---

## 1 answers

### Answer by username_3 on 2020-01-20. Score: 10 | Accepted 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.

> **Comments:**
> **username_0**: This is a good characterisation! Do you happen to know some if it connected to other graph characteristics or has interesting structural/algorithmical implications?  
> **username_4**: 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 http://www.graphclasses.org/classes/gc_151.html and http://www.graphclasses.org/classes/gc_396.html  
> **username_5**: The Wikipedia article on induced paths refers to a quite a bunch of results on graphs with bounded induced path length: https://en.m.wikipedia.org/wiki/Induced_path  
> **username_0**: The "detour number" is what I have been looking for. It even has a connection to treedepth. Thanks to all participants!  

---

