5
$\begingroup$

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.

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

1 Answer 1

10
$\begingroup$

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.

$\endgroup$
4
  • $\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
    Commented Jan 20, 2020 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
    Commented Jan 20, 2020 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$ Commented Jan 20, 2020 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
    Commented Jan 21, 2020 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.