Geodetic Convexity Parameters for Graphs with Few Short Induced Paths

Abstract

We study several parameters of geodetic convexity for graph classes defined by restrictions concerning short induced paths. Partially answering a question posed by Araujo et al., we show that computing the geodetic hull number of a given $P_9$-free graph is NP-hard. Similarly, we show that computing the geodetic interval number of a given $P_5$-free graph is NP-hard. On the positive side, we identify several graph classes for which the geodetic hull number can be computed efficiently. Furthermore, following a suggestion of Campos et al., we show that the geodetic interval number, the geodetic convexity number, the geodetic Carathéodory number, and the geodetic Radon number can all be computed in polynomial time for $(q,q-4)$-graphs.

1 Introduction

In the present paper we study five prominent graph parameters of geodetic convexity, the hull number, the interval number, the convexity number, the Carathéodory number, and the Radon number, for graph classes defined by restrictions concerning short induced paths. Our motivation mainly comes from two recent papers. In [7] Campos, Sampaio, Silva, and Szwarcfiter show that for the $P_3$-convexity, the above parameters can be determined in linear time for $(q,q-4)$-graphs. In their conclusion they suggest to consider the geodetic versions of the parameters for these graphs. In [3] Araujo, Morel, Sampaio, Soares, and Weber study the geodetic hull number of $P_5$-free graphs. They show that this number can be computed in polynomial time for triangle-free $P_5$-free graphs, and ask about the computational complexity of the geodetic hull number of $P_k$-free graphs in general.

Before we discuss further related work and our own contribution, we collect some relevant definitions. All graphs will be finite, simple, and undirected, and we use standard terminology and notation. A graph G is F-free for some graph F if G does not contain an induced subgraph that is isomorphic to F. For a positive integer n, let $K_n$, $P_n$, $K_{1,n-1}$, and $C_n$ be the complete graph, the path, the star, and the cycle of order n, respectively. For an integer q at least 4, a graph G is a $(q,q-4)$-graph [5] if every set of q vertices of G induces at most $q-4$ distinct $P_4$s. The clique number $\omega (G)$ of a graph G is the maximum order of a clique in G, which is a set of pairwise adjacent vertices. The independence number $\alpha (G)$ of a graph G is the maximum order of an independent set in G, which is a set of pairwise non-adjacent vertices. A vertex of a graph is simplicial if its neighborhood is a clique. For an integer k, let [k] be the set of all positive integers at most k.

For a set X of vertices of a graph G, the interval $I_G(X)$ of X in G is the set of vertices of G that contains X as well as all vertices of G that lie on shortest paths between vertices from X. If $I_G(X)=X$, then X is a convex set. The hull $H_G(X)$ of X in G is the smallest convex set that contains X. If $H_G(X)=V(G)$, then X is a hull set of G, and if $I_G(X)=V(G)$, then X is an interval set of G. The hull number h(G) of G [24] is the smallest order of a hull set of G. Similarly, the interval number i(G) of G, also known as the geodetic number [28], is the smallest order of an interval set of G. The convexity number cx(G) of G [11] is the maximum cardinality of a convex set that is a proper subset of the vertex set of G. Inspired by a classical theorem of Carathéodory [6], the Carathéodory number cth(G) of G [19] is the minimum integer k such that for every set X of vertices of G, and every vertex x in $H_G(X)$, there is a subset Y of X of order at most k such that x belongs to $H_G(Y)$. Similarly, inspired by a classical theorem by Radon [30], the Radon number r(G) of G [13, 14] is the minimum integer k such that for every set X of at least k vertices of G, there is a subset $X_1$ of X such that $H_G(X_1)\cap H_G(X\setminus X_1)\not =\emptyset$. A set A of vertices of G is anti-Radon if A has no subset $A_1$ with $H_G(A_1)\cap H_G(A\setminus A_1)\not =\emptyset$. It is easy to see that the Radon number is exactly one more than the maximum cardinality of an anti-Radon set. Note that a clique is anti-Radon.

For reduction arguments useful to prove Theorem 6 below, we consider a second kind of convexity. For a set X of vertices of a graph G, the restricted interval $I'_G(X)$ of X in G is the set of vertices of G that contains X as well as all vertices of G that lie on an induced $P_3$ between vertices from X, that is, we only consider shortest paths of order 3. This leads to a convexity that has recently been studied on its own right [4], and is different from the above-mentioned $P_3$-convexity. If $I'_G(X)=X$, then X is restricted convex. The restricted hull $H'_G(X)$ of X in G, a restricted hull set of G, a restricted interval set of G, the restricted hull number $h'(G)$ of G, the restricted interval number $i'(G)$ of G, the restricted convexity number $cx'(G)$ of G, the restricted Carathéorody number $cth'(G)$ of G, the restricted Radon number $r'(G)$ of G, and restricted anti-Radon sets are all defined in the obvious way. Note that $I'_G(X)\subseteq I_G(X)$, which implies $H'_G(X)\subseteq H_G(X)$. Hence, every anti-Radon set is a restricted anti-Radon set.

We briefly survey some known related results. The hull number is NP-hard for bipartite graphs [2] and even for partial cubes [1], but can be computed in polynomial time for cographs [12], $(q,q-4)$-graphs [2], $\{ C_3,P_5\}$-free graphs [3], distance-hereditary graphs [29], and chordal graphs [29]. Bounds on the hull number are given in [2, 15, 24]. The interval number is NP-hard for cobipartite graphs [22] and for chordal graphs as well as for chordal bipartite graphs [16], but can be computed in polynomial time for split graphs [16], proper interval graphs [23], block-cactus graphs [22], and monopolar chordal graphs [22]. The convexity number is NP-hard for bipartite graphs [17, 27]. Finally, also the Carathéodory number [19] as well as the Radon number [14] are NP-hard. Next to the geodetic convexity and the $P_3$-convexity, further well-studied graphs convexities are the induced paths convexity, also known as the monophonic convexity [18, 21, 25], the all paths convexity [8], the triangle path convexity [9, 10], and the convexity based on induced paths of order at least 4 [20].

Our contributions are as follows. Partially answering the question posed by Araujo et al. [3], we show that computing the hull number of a given $P_\ell$-free graph is NP-hard for every $\ell \ge 9$. Similarly, we show that computing the interval number of a given $P_\ell$-free graph is NP-hard for every $\ell \ge 5$. Furthermore, we extend the result of Araujo et al. [3] that the hull number can be computed in polynomial time for $\{ C_3,P_5\}$-free graphs to $\{ \mathrm{paw},P_5\}$-free graphs, to triangle-free graphs in which every six vertices induce at most one $P_5$, and to $\{ C_3,\ldots ,C_{k-2},P_k\}$-free graphs for every integer k. Following the suggestion of Campos et al. [7], we show that the interval number, the convexity number, the Carathéodory number, and the Radon number as well as their restricted versions can all be computed in polynomial time for $(q,q-4)$-graphs. Section 2 contains our complexity results. In Sect. 3 we present the efficiently solvable cases, and in Sect. 4 we list some open problems.

2 Complexity Results

Theorem 1

For a given $P_9$-free graph G, and a given integer k, it is NP-complete to decide whether $h(G)\le k$.

Proof

Since the hull of a set of vertices can be computed in polynomial time, the considered decision problem belongs to NP. In order to prove NP-completeness, we describe a polynomial reduction from a restricted version of Satisfiability. Therefore, let $\mathcal{C}$ be an instance of Satisfiability consisting of m clauses $C_1,\ldots ,C_m$ over n boolean variables $x_1,\ldots ,x_n$ such that every clause in $\mathcal{C}$ contains at most three literals, and, for every variable $x_i$, there are at most three clauses in $\mathcal{C}$ that contain either $x_i$ or $\bar{x}_i$. Note that Satisfiability is still NP-complete for such instances (cf. [LO1] in [26]).

Clearly, we may assume that no clause in $\mathcal{C}$ contains a variable as well as its negation, and that $n\ge 2$. If, for some variable $x_i$, no clause in $\mathcal{C}$ contains $\bar{x}_i$, then setting $x_i$ to true, and removing all clauses from $\mathcal{C}$ that contain $x_i$, leads to an equivalent instance. Therefore, by symmetry, we may assume that, for every variable $x_i$, some clause in $\mathcal{C}$ contains $x_i$, and some clause in $\mathcal{C}$ contains $\bar{x}_i$. If, for some variable $x_i$, there is only one clause in $\mathcal{C}$ containing $x_i$, and only one clause in $\mathcal{C}$ containing $\bar{x}_i$, then introducing two new variables $x_{n+1}$ and $x_{n+2}$, and adding the three clauses $x_i\vee x_{n+1}\vee x_{n+2}$, $\bar{x}_{n+1}\vee x_{n+2}$, and $x_{n+1}\vee \bar{x}_{n+2}$, leads to an equivalent instance. Therefore, by symmetry, we may assume that, for every variable $x_i$, there are exactly three clauses in $\mathcal{C}$ that contain either $x_i$ or $\bar{x}_i$. If, for some variable $x_i$, there is one clause in $\mathcal{C}$ containing $x_i$, and two clauses in $\mathcal{C}$ containing $\bar{x}_i$, then exchanging $x_i$ with $\bar{x}_i$ within $\mathcal{C}$, leads to an equivalent instance. Altogether, we may assume that, for every variable $x_i$, there are exactly two clauses in $\mathcal{C}$, say $C_{j_i^{(1)}}$ and $C_{j_i^{(2)}}$, that contain $x_i$, and exactly one clause in $\mathcal{C}$, say $C_{j_i^{(3)}}$, that contains $\bar{x}_i$. Furthermore, these three clauses are distinct.

Let the graph G be constructed as follows starting with the empty graph:

• For every $j\in [m]$, add a vertex $c_j$.

• For every $i\in [n]$, add a copy $G_i$ of the graph in Fig. 1, and denote the vertices as indicated in the figure.

• Add two further vertices $w_1$ and $w_2$.

• Add further edges to turn the set

  $$\begin{aligned} C=\{ c_j:j\in [m]\}\cup \{ y_i:i\in [n]\}\cup \{ v_i:i\in [n]\} \end{aligned}$$

  into a clique.

• For every i in [n], add the three edges $x_i^{(1)}c_{j_i^{(1)}}$, $x_i^{(2)}c_{j_i^{(2)}}$, and $\bar{x}_ic_{j_i^{(3)}}$.

• For every i in [n], add the two edges $v_iw_1$ and $v_iw_2$.

See Fig. 2 for a partial illustration.

Fig. 1.

The graph $G_i$.

Fig. 2.

Part of G, where $C_1:x_1\vee x_2\vee x_3$, $C_2:x_1\vee \bar{x}_2\vee x_3$, and $C_3:\bar{x}_1\vee x_2\vee \bar{x}_3$. For the sake of visibility, the edges within C as well as the vertices $w_1$ and $w_2$ are not shown.

Let $k=2n+2$. Note that the order of G is $9n+m+2$. It remains to show that G is $P_9$-free, and that $\mathcal{C}$ is satisfiable if and only if $h(G)\le k$.

Let P be an induced path in G. Since C is a clique, the subgraph $G[V(P)\cap C]$ of P induced by C is a (possibly empty) path of order at most 2. Note that all components of $G[V(G)\setminus C]$ have order at most 5, and only contain induced paths of order at most 3. This implies that P has order at most $3+2+3$, that is, G is $P_9$-free.

First, let $\mathcal{S}$ be a satisfying truth assignment for $\mathcal{C}$. Let

$$\begin{aligned} S=\{ w_1,w_2\} \cup \,\,\,\,\bigcup _{i\in [n]:\,x_i\,\mathrm{true}\,\mathrm{in}\,\mathcal{S}} \{ x_i,x_i'\}\,\,\,\, \cup \,\,\,\,\bigcup _{i\in [n]:\,x_i\,\mathrm{false}\,\mathrm{in}\, \mathcal{S}}\{ \bar{x}_i,\bar{x}_i'\}. \end{aligned}$$

Clearly, $|S|=k$. Since $\{ v_1,\ldots ,v_n\}\subseteq H_G(\{ w_1,w_2\})$, and $y_i\in H_G(\{ x'_i,v_i\})\cap H_G(\{ \bar{x}'_i,v_i\})$ for $i\in [n]$, we obtain $\{ v_1,\ldots ,v_n\}\cup \{ y_1,\ldots ,y_n\}\subseteq H_G(S).$ If $i\in [n]$ is such that $x_i$ is true in $\mathcal{S}$, and $\ell \in [n]\setminus \{ i\}$, then $u_i\in H_G(\{ x_i,v_i\})$, $\bar{x}'_i\in H_G(\{ y_i,u_i\})$, and $\left\{ c_{j_i^{(1)}},c_{j_i^{(2)}},x_i^{(1)},x_i^{(2)}\right\} \subseteq H_G(\{ x_i,v_\ell \})$. If $i\in [n]$ is such that $x_i$ is false in $\mathcal{S}$, then $u_i\in H_G(\{ \bar{x}_i',v_i\})$, $x_i'\in H_G(\{ \bar{x}_i,y_i\})$, and $c_{j_i^{(3)}}\in H_G(\{ \bar{x}_i,v_i\})$. Since $\mathcal{S}$ is a satisfying truth assignment, this implies $\{ x_1',\ldots ,x_n'\}\cup \{ \bar{x}'_1,\ldots ,\bar{x}'_n\}\cup \{ u_1,\ldots ,u_n\}\cup \{ c_1,\ldots ,c_m\}\subseteq H_G(S).$ For $i\in [n]$, we have $\left\{ x_i^{(1)},x_i^{(2)}\right\} \subseteq H_G\left( \left\{ u_i,c_{j_i^{(1)}},c_{j_i^{(2)}}\right\} \right)$, $x_i\in H_G\left( \left\{ x_i^{(1)},x_i^{(2)}\right\} \right)$, $\bar{x}_i\in H_G\left( \left\{ x_i',c_{j_i^{(3)}}\right\} \right)$. This implies

$$\begin{aligned} \bigcup _{i\in [n]}\left\{ x_i,x_i^{(1)},x_i^{(2)},\bar{x}_i\right\} \subseteq H_G(S). \end{aligned}$$

Altogether, it follows that S is a hull set, and, hence, $h(G)\le |S|=k$.

Conversely, let S be a hull set of order at most $2n+2$. Since $w_1$ and $w_2$ are simplicial, we have $w_1,w_2\in S$. For $i\in [n]$, let

$$\begin{aligned} V_i^{(1)}= & {} \left\{ x_i,x_i^{(1)},x_i^{(2)},u_i,\bar{x}_i'\right\} , \,\,\,\,V_i^{(2)}=\left\{ x_i',\bar{x}_i\right\} , \text{ and }\,\,\,\, V_i^{(3)}=\left\{ \bar{x}'_i,y_i,x_i'\right\} . \end{aligned}$$

Since $N_G\left( V_i^{(1)}\right) \setminus V_i^{(1)}\subseteq C$, $N_G\left( V_i^{(2)}\right) \setminus V_i^{(2)}\subseteq C$, and C is a clique, the two sets $V(G)\setminus V_i^{(1)}$ and $V(G)\setminus V_i^{(2)}$ are convex, which implies that S intersects $V_i^{(1)}$ as well as $V_i^{(2)}$. Since $u_iv_ic_{j_i^{(3)}}\bar{x}_i$ is a path of order 4 between $u_i$ and $\bar{x}_i$, no shortest path between two vertices in $V(G)\setminus V_i^{(3)}$ contains the two vertices $\bar{x}'_i$ and $x_i'$. Since $N_G(y_i)\setminus \{ \bar{x}'_i,x_i'\}\subseteq C$, no shortest path between two vertices in $V(G)\setminus V_i^{(3)}$ intersects $V_i^{(3)}$ only in $y_i$. Since $u_i$ has distance at most 2 from every vertex in C, no shortest path between two vertices in $V(G)\setminus V_i^{(3)}$ contains $\bar{x}'_i$ and $y_i$. Since $\bar{x}_i$ has distance at most 2 from every vertex in C, no shortest path between two vertices in $V(G)\setminus V_i^{(3)}$ contains $y_i$ and $x_i'$. Altogether, it follows, that $V(G)\setminus V_i^{(3)}$ is convex, which implies that S intersects $V_i^{(3)}$. Since $S\setminus \{ w_1,w_2\}$ has order exactly 2n, it follows that S contains exactly one vertex from $V_i^{(1)}$, exactly one vertex from $V_i^{(2)}$, and intersects $\{ \bar{x}_i', x_i'\}$. Since $y_i,x_i'\in H_G(\{ \bar{x}_i',\bar{x}_i\})$, we may assume that $\bar{x}_i'\in S$ implies $S\cap V(G_i)=\{ \bar{x}_i,\bar{x}_i'\}$. Since $\{ v_1,\ldots ,v_n\}\subseteq H_G(\{ w_1,w_2\})$ and $u_i,\bar{x}_i',y_i,x_i^{(1)},x_i^{(2)}\in H_G(\{ x_i,x_i',v_i,v_\ell \})$ for every $\ell \in [n]\setminus \{ i\}$, we may assume that $x_i'\in S$ implies $S\cap V(G_i)=\{ x_i,x_i'\}$. Altogether, for every $i\in [n]$, we obtain that

$$\begin{aligned} S\cap V(G_i)\in \left\{ \{ x_i,x_i'\},\{ \bar{x}_i,\bar{x}_i'\}\right\} . \end{aligned}$$

(1)

Let $\mathcal{S}$ be the truth assignment, where we set $x_i$ to be true exactly if $S\cap V(G_i)=\{ x_i,x_i'\}$.

For $j\in [m]$, let

$$\begin{aligned} V_j=\{ c_j\} \cup \,\,\bigcup _{i\in [n]:j=j_i^{(1)}}\left\{ x_i,x_i^{(1)}\right\} \,\, \cup \,\,\bigcup _{i\in [n]:j=j_i^{(2)}}\left\{ x_i,x_i^{(2)}\right\} \,\, \cup \,\,\bigcup _{i\in [n]:j=j_i^{(3)}}\left\{ \bar{x}_i\right\} . \end{aligned}$$

Fig. 3.

The set $V_1$ for the clause $C_1=x_1\vee x_2\vee \bar{x}_3$, where $j_1^{(1)}=j_2^{(2)}=1$.

See Fig. 3 for an illustration. Note that $N_G(c_j)\setminus V_j=C\setminus \{ c_j\}$. Furthermore, if $i\in [n]$ is such that $j=j_i^{(1)}$, then $N_G\left( \left\{ x_i,x_i^{(1)}\right\} \right) \setminus V_j=\left\{ u_i,x_i^{(2)}\right\}$, if $i\in [n]$ is such that $j=j_i^{(2)}$, then $N_G\left( \left\{ x_i,x_i^{(2)}\right\} \right) \setminus V_j=\left\{ u_i,x_i^{(1)}\right\}$, and, if $i\in [n]$ is such that $j=j_i^{(3)}$, then $N_G\left( \left\{ \bar{x}_i\right\} \right) \setminus V_j=\left\{ x_i'\right\}$. Since $C\setminus \{ c_j\}$ is a clique, no shortest path between two vertices in $V(G)\setminus V_j$ intersects $V_j$ only in $c_j$. If a shortest path P between two vertices in $V(G)\setminus V_j$ contains a vertex $x_i^{(r)}$ from $V_j$ for some $r\in [2]$, then, possibly exchanging $x_i$ with $u_i$ on P, we may assume that P contains the vertex $u_i$. Since every two vertices in $\{ u_1,\dots ,u_n\}\cup \{ x_1',\ldots ,x_n'\}$ have distance at most three, no shortest path between two vertices in $V(G)\setminus V_j$ contains two vertices from

$$\begin{aligned} V_j\cap \left( \left\{ x_1^{(1)},\ldots ,x_n^{(1)}\right\} \cup \left\{ x_1^{(2)},\ldots ,x_n^{(2)}\right\} \cup \left\{ \bar{x}_1,\ldots ,\bar{x}_n\right\} \right) . \end{aligned}$$

This implies that, since $u_i$ has distance at most two from each vertex in $C\setminus \{ c_j\}$ for every $i\in [n]$, no shortest path between two vertices in $V(G)\setminus V_j$ contains a vertex from

$$\begin{aligned} V_j\cap \left( \left\{ x_1^{(1)},\ldots ,x_n^{(1)}\right\} \cup \left\{ x_1^{(2)},\ldots ,x_n^{(2)}\right\} \right) . \end{aligned}$$

Similarly, since $x_i'$ has distance at most two from each vertex in $C\setminus \{ c_j\}$ for every $i\in [n]$, no shortest path between two vertices in $V(G)\setminus V_j$ contains a vertex from

$$\begin{aligned} V_j\cap \left\{ \bar{x}_1,\ldots ,\bar{x}_n\right\} . \end{aligned}$$

Altogether, it follows that $V(G)\setminus V_j$ is convex, which implies that S intersects

$$\begin{aligned} \bigcup _{i\in [n]:j=j_i^{(1)}}\left\{ x_i,x_i^{(1)}\right\} \,\, \cup \,\,\bigcup _{i\in [n]:j=j_i^{(2)}}\left\{ x_i,x_i^{(2)}\right\} \,\, \cup \,\,\bigcup _{i\in [n]:j=j_i^{(3)}}\left\{ \bar{x}_i\right\} \end{aligned}$$

for every $j\in [m]$. By (1) and the definition of $\mathcal{S}$, this implies that $\mathcal{S}$ is a satisfying truth assignment for $\mathcal{C}$, which completes the proof. $\square$

Theorem 2

For a given $P_5$-free graph G, and a given integer k, it is NP-complete to decide whether $i(G)\le k$.

3 Efficiently Solvable Cases

As observed in the introduction, Araujo et al. [3] show that the hull number can be computed in polynomial time for $\{ C_3,P_5\}$-free graphs. We extend their result in several ways.

The paw is the unique graph with degree sequence 1, 2, 2, 3. Note that the paw arises by attaching an endvertex to one vertex of a triangle.

Theorem 3

The hull number of a given $\{ \mathrm{paw},P_5\}$-free graph can be computed in polynomial time.

Proof

Let G be a $\{ \mathrm{paw},P_5\}$-free graph. Clearly, we may assume that G is connected. If G is $P_4$-free, then G is a cograph, and the statement follows from [12]. Hence, we may assume that G contains an induced path $P:u_1u_2u_3u_4$ of order 4. For a positive integer d, let $V_d=\{ v\in V(G):\mathrm{dist}_G(v,V(P))=d\}$, where $\mathrm{dist}_G(v,V(P))=\min \{ \mathrm{dist}_G(v,u):u\in V(P)\}$. Let X be the union of V(P) and the set of all simplicial vertices. We will show that adding at most one vertex to X yields a hull set of G, which implies that a minimum hull set can be found efficiently. In fact, every hull set contains all simplicial vertices, and considering the polynomially many extensions of the set of simplicial vertices by at most 5 vertices will yield a minimum hull set.

Let $v\in V_1$. First, we assume that v is adjacent to $u_1$. If v is adjacent to $u_2$, then, since G is paw-free, v is adjacent to all vertices of P. If v is not adjacent to $u_2$, then, since G is $\{ \mathrm{paw},P_5\}$-free, $N_G(v)\cap V(P)\in \{ \{ u_1,u_3\},\{ u_1,u_4\}\}$. Next, we assume that v is not adjacent to $u_1$ or $u_4$. Since G is paw-free, we obtain $N_G(v)\cap V(P)\in \{ \{ u_2\},\{ u_3\}\}$. Altogether, by symmetry, we obtain that $N_G(v)\cap V(P)$ is one of the sets $\{ u_2\}$, $\{ u_3\}$, $\{ u_1,u_3\}$, $\{ u_2,u_4\}$, $\{ u_1,u_4\}$, and V(P). Note that a vertex v in $V_1$ does not lie in $H_G(V(P))\subseteq H_G(X)$ only if $N_G(v)\cap V(P)\in \{ \{ u_2\},\{ u_3\}\}$.

If $w\in V_2$, and v is a neighbor of w in $V_1$, then, since G is $\{ \mathrm{paw},P_5\}$-free, $N_G(v)\cap V(P)$ is one of the sets $\{ u_1,u_3\}$ and $\{ u_2,u_4\}$. Since G is $P_5$-free, this implies $V_3=\emptyset$, that is, $V(G)=V(P)\cup V_1\cup V_2$. Suppose that $w_1$ and $w_2$ are adjacent vertices in $V_2$. Let $w_1vu_i$ be a path between $w_1$ and V(P). By symmetry, we may assume that $i<4$. Since G is paw-free, the vertex $w_2$ is not adjacent to v. Now, $w_2w_1vu_iu_{i+1}$ is a $P_5$. Hence, $V_2$ is independent. Recall that every neighbor v in $V_1$ of a vertex in $V_2$ lies in $H_G(V(P))$. Therefore, every non-simplicial vertex in $V_2$ lies in $H_G(V(P))\subseteq H_G(X)$, that is, $V(P)\cup V_2\subseteq H_G(X)$.

Let $V_1'$ be the set of non-simplicial vertices in $V_1$ that do not belong to $H_G(X)$. If $V_1'=\emptyset$, then $V_1\subseteq H_G(X)$, and X is a hull set. Hence, we may assume that $V_1'$ is not empty. If $A=\{ v\in V_1':N_G(v)\cap V(P)=\{ u_2\}\}$, and $B=\{ v\in V_1':N_G(v)\cap V(P)=\{ u_3\}\}$, then $V_1'=A\cup B$. Since G is paw-free, the sets A and B are independent. Since every vertex in $V_1'$ is non-simplicial, it has two non-adjacent neighbors, at least one of which does not belong to $H_G(X)$. It follows that every vertex in A has a neighbor in B, and every vertex in B has a neighbor in A. Note that this implies that A and B are both not empty. Let H be the bipartite induced subgraph $G[A\cup B]$ of G with partite sets A and B. If $a_1,a_2\in A$ and $b_1,b_2\in B$ are such that $a_1b_1,a_2b_2\in E(G)$ and $a_1b_2,a_2b_1\not \in E(G)$, then $b_1a_1u_2a_2b_2$ is a $P_5$. Hence, H is $2K_2$-free. Let $a_1$ be a vertex in A of maximum degree $d_H(a_1)$ in H. Suppose that $a_1$ is not adjacent to some vertex $b_2$ in B. Let $a_2$ be a neighbor of $b_2$ in A. Since $d_H(a_1)\ge d_H(a_2)$, there is a neighbor $b_1$ of $a_1$ in B that is not adjacent to $a_2$. Now, $a_1,a_2\in A$ and $b_1,b_2\in B$ are as above, which is a contradiction. Hence, $N_H(a_1)=B$, which implies that $B\subseteq H_G(\{ a_1,u_3\})\subseteq H_G(X\cup \{ a_1\})$. Since $A\subseteq H_G(B\cup \{ u_2\})$, it follows that $V_1'\subseteq H_G(X\cup \{ a_1\})$, that is, $X\cup \{ a_1\}$ is a hull set, which completes the proof. $\square$

We proceed to our next generalization of the result of Araujo et al. [3].

Theorem 4

Let k be a fixed positive integer.

For a given $\{ C_i:3\le i\le k-2\}\cup \{ P_k\}$-free graph G, the hull number h(G) can be computed in polynomial time.

Proof

The proof is by induction on k. For $k\le 4$, the graph G is a cograph, and the statement follows from [12]. For $k=5$, the statement follows from the result of Araujo et al. [3], or from Theorem 3. Now, let $k\ge 6$. The proof for $k=6$ is similar to the proof of Theorem 3, and is given in the appendix. Hence, let $k\ge 7$.

Let G be a connected $\{ C_i:3\le i\le k-2\}\cup \{ P_k\}$-free graph. If G is $P_{k-1}$-free, then the result follows by induction. Hence, we may assume that G contains an induced path $P:u_1\ldots u_{k-1}$ of order $k-1$. Let X be the union of V(P) and the set of all simplicial vertices. We will show that X is a hull set of G, which implies that a minimum hull set can be found efficiently. $\square$

Claim 1

G has only cycles of orders $k-1$ and k, and every cycle of G is induced.

Proof

Suppose that G has a cycle of order at least $k+1$. Let $C:x_0\ldots x_{\ell -1}x_0$ be a shortest cycle in G of order $\ell$ at least $k+1$. Since G is $P_k$-free, the cycle C is not induced. Let $x_ix_j$ be an edge such that $j-i=\mathrm{dist}_C(x_i,x_j)$ is minimum. By symmetry, we may assume that $i=0$. Since $x_0x_1\ldots x_jx_0$ is an induced cycle of order $j+1$, we obtain $j\ge k-2$. Since $x_0x_1\ldots x_{j-1}$ is an induced path of order j, we obtain $j\le k-1$, that is, $j\in \{ k-2,k-1\}$. First, we assume that $j=k-1$. Since the path $x_1x_2\ldots x_k$ is not induced, the choice of $x_ix_j$ implies that $x_1x_k$ is an edge. Now, $x_1x_kx_{k-1}x_0x_1$ is a cycle of order 4, which is a contradiction. Hence $j=k-2$. Since the path $x_1x_2\ldots x_k$ is not induced, the choice of $x_ix_j$ implies that there is an edge between $\{ x_1,x_2\}$ and $\{ x_{k-1},x_k\}$. Since G is $\{ C_4,C_5\}$-free, we obtain that $x_2x_k$ is an edge. Since $x_0x_1x_2x_kx_{k-1}x_{k-2}x_0$ is an induced cycle of order 6, we obtain $k=7$, which implies $j=5$ and $\ell \ge 8$. Since $x_0x_5x_4x_3x_2x_7x_8\ldots x_0$ is a cycle of order $\ell -2$, the choice of C implies $\ell \le 9$. Now, $x_0x_5x_6\ldots x_{\ell -1}x_0$ is a cycle of order $\ell -4\le 5$, which is a contradiction. Hence, G has no cycle of order at least $k+1$. In view of the forbidden induced subgraphs, this implies that G has only cycles of orders $k-1$ or k, and that every cycle of G is induced. $\square$

For a positive integer d, let $V_d=\{ v\in V(G):\mathrm{dist}_G(v,V(P))=d\}$.

Claim 2

$V_d\not =\emptyset$ implies $d\le \left\lfloor \frac{k}{2}\right\rfloor -1$.

Proof

Suppose that $V_d$ is non-empty for some $d\ge \left\lfloor \frac{k}{2}\right\rfloor$. Let $x_0\ldots x_d$ be a shortest path between a vertex $x_0$ in $V_d$ and some vertex $x_d$ of P. By symmetry, we may assume that $x_d=u_i$, where $i\ge \left\lceil \frac{k}{2}\right\rceil$. If $x_{d-1}$ has a neighbor in $\left\{ u_j:i-\left\lceil \frac{k-2}{2}\right\rceil \le j\le i-1\right\}$, then G has a cycle of order at most $\left\lceil \frac{k-2}{2}\right\rceil +2\le k-2$, which is a contradiction. Hence, $x_0\ldots x_du_{i-1}u_{i-2}\ldots u_{i-\left\lceil \frac{k-2}{2}\right\rceil }$ is an induced path of order $d+1+\left\lceil \frac{k-2}{2}\right\rceil \ge \left\lfloor \frac{k}{2}\right\rfloor +1+\left\lceil \frac{k-2}{2}\right\rceil =k$, which is a contradiction. $\square$

Claim 3

For every d at least 2, every vertex in $V_d$ has exactly one neighbor in $V_{d-1}$.

Proof

Suppose that for some d at least 2, some vertex in $V_d$ has two neighbors in $V_{d-1}$. This implies the existence of two distinct paths $Q:x_0x_1\ldots x_d$ and $Q':x_0x_1'\ldots x_d'$ between some vertex $x_0$ in $V_d$ and vertices $x_d$ and $x_d'$ of P. Since $2d\le k-2$, we obtain that $V(Q)\cap V(Q')=\{ x_0\}$. Let $x_d=u_i$ and $x'_d=u_j$, where $j>i$. The union of Q, $Q'$, and the path $u_i\ldots u_j$ is a cycle C. First, we assume that C has order k. Recall that, by Claim 1, all cycles of G are induced. Since $d\ge 2$, we obtain $j-i=k-2d\le k-4$. Hence, since P has order $k-1$, we may assume that $i\ge 2$. Since the path $u_{i-1}\ldots u_jx'_{d-1}\ldots x_1'x_0x_1\ldots x_{d-2}$ of order k is not induced, we obtain that $u_{i-1}$ is adjacent to $x_{d-1}'$. By Claim 1, this implies that $j-i\le 2$. Now, $u_{i-1}\ldots u_jx_{d-1}'u_{i-1}$ is a cycle of order at most 5, which is a contradiction. Hence, by Claim 1, the order of C is $k-1$. Since $d\ge 2$, we obtain $j-i\le k-5$. Hence, since P has order $k-1$, we may assume that $i\ge 3$. Similarly as above, we obtain that $x_{d-1}'$ is adjacent to $u_{i-1}$ or $u_{i-2}$. If $x_{d-1}'$ is adjacent to $u_{i-1}$, then $j-i=1$, and $u_{i-1}u_iu_jx_{d-1}'u_{i-1}$ is a cycle of order 4, which is a contradiction. Hence, $x_{d-1}'$ is adjacent to $u_{i-2}$. By Claim 1, this implies that $j-i\le 2$. Similarly as above, if $j-i=1$, then G contains a cycle of order 5, which is a contradiction. Hence $j-i=2$, and $u_{i-2}\ldots u_jx_{d-1}'u_{i-2}$ is a cycle of order 6, which implies that $k=7$ and $d=2$. If $j\le 5$, then $u_{i-1}x_2x_1x_0x_1'x_2'u_{j+1}$ is an induced path of order 7, which is a contradiction. Hence $j=6$, which implies that $i=j-2=4$. Now, $u_1u_2x_1'x_0x_1u_4u_5$ is an induced path of order 7, which is a contradiction. $\square$

Claim 4

For every d at least 2, the set $V_d$ is independent.

Proof

Suppose that for some d at least 2, the set $V_d$ is not independent. This implies the existence of two distinct paths $Q:x_0x_1\ldots x_d$ and $Q':x'_0x_1'\ldots x_d'$ between two adjacent vertices $x_0$ and $x_0'$ in $V_d$ and vertices $x_d$ and $x_d'$ of P. If $V(Q)\cap V(Q')\not =\emptyset$, then Claims 1 and 2 imply that $x_d=x_d'$, $V(Q)\cap V(Q')=\{ x_d\}$, and $d=\frac{k}{2}-1$. By symmetry, we may assume that $x_d=u_i$, where $i\ge 3$. Now, $u_{i-2}u_{i-1}x_dx_{d-1}\ldots x_1x_0x_0'x_1'\ldots x_{d-2}'$ is an induced path of order k, which is a contradiction. Hence, $V(Q)\cap V(Q')=\emptyset$. Let $x_d=u_i$ and $x'_d=u_j$, where $j>i$. The union of Q, $Q'$, the edge $x_0x_0'$, and the path $u_i\ldots u_j$ is a cycle C. First, we assume that C has order k. Since $d\ge 2$, we obtain $j-i=k-2d-1\le k-5$. Hence, since P has order $k-1$, we may assume that $i\ge 2$. Since the path $u_{i-1}\ldots u_jx'_{d-1}\ldots x_1'x_0'x_0x_1\ldots x_{d-2}$ of order k is not induced, we obtain that $u_{i-1}$ is adjacent to $x_{d-1}'$. By Claim 1, this implies that $j-i\le 2$. Now, $u_{i-1}\ldots u_jx_{d-1}'u_{i-1}$ is a cycle of order at most 5, which is a contradiction. Hence, by Claim 1, the order of C is $k-1$. Since $d\ge 2$, we obtain $j-i=k-1-2d-1\le k-6$. Hence, since P has order $k-1$, we may assume that $i\ge 3$. Similarly as in the proof of Claim 3, we obtain that $x_{d-1}'$ is adjacent to $u_{i-2}$. By Claim 1, this implies that $j-i\le 2$. Similarly as above, if $j-i=1$, then G contains a cycle of order 5, which is a contradiction. Hence $j-i=2$, and $u_{i-2}\ldots u_jx_{d-1}'u_{i-2}$ is a cycle of order 6, which implies that $k=7$. Now, $j-i\le k-6=1$, which is a contradiction. $\square$

Recall that X is the union of V(P) and the set of all simplicial vertices.

Let $u\in V_d$ for some $d\ge 2$. Let $d'\ge d$ and $u'\in V_{d'}$ be such that u lies on a shortest path between $u'$ and some vertex of P, and $d'$ is maximum. Note that $d'=d$ and $u'=u$ is allowed. Since $u'$ has no neighbor in $V_{d'+1}$, Claims 3 and 4 imply that $u'$ is simplicial, and, hence, $u\in H_G(\{ u'\}\cup V(P))\subseteq H_G(X)$.

Let $u\in V_1\setminus H_G(X)$. It follows that u does not have two neighbors on P, and also no neighbor in $V_2$. Since u is not simplicial, this implies that u has exactly one neighbor $u_i$ on P as well as some neighbor $u'$ in $V_1$. Let $u_j$ be a neighbor of $u'$ on P. Clearly, $i\not =j$. Note that $u_iuu'u_j$ is a path of order 4. Hence, since $u\not \in H_G(V(P))$, the distance in G between $u_i$ and $u_j$ is at most 2, which implies the contradiction that G contains a cycle of order at most 5.

It follows that X is a hull set of G, which completes the proof. $\square$

We present another generalization of the result of Araujo et al. [3], and consider triangle-free graphs in which every six vertices induce at most one $P_5$. Obviously, these graphs have been inspired by the $(q,q-4)$-graphs [5], and, consequently, we refer to them as (6,1)-graphs.

Theorem 5

If G is a connected triangle-free (6, 1)-graph, then either G is $P_5$-free or G arises from a star $K_{1,p}$ with $p\ge 2$ by subdividing two edges once and all remaining edges at most once.

Corollary 1

The hull number of a given triangle-free (6, 1)-graph can be computed in polynomial time.

Using the structural properties of $(q,q-4)$-graphs [5, 7], and establishing suitable recursions for the convexity parameters, we obtain our final result.

Theorem 6

Let q be a fixed integer at least 4.

For a given $(q,q-4)$-graph G, all parameters h(G), $h'(G)$, i(G), $i'(G)$, cx(G), $cx'(G)$, cth(G), $cth'(G)$, r(G), and $r'(G)$ can be computed in polynomial time.

4 Conclusion

We conclude with a number of questions. Can the considered parameters be determined in linear time for $(q,q-4)$-graphs? What is the complexity of the hull number for $P_k$-free graphs for $k\in \{ 5,6,7,8\}$? What is the complexity of the other convexity parameters for $\{ C_i:3\le i\le k-2\}\cup \{ P_k\}$-free graphs or (triangle-free) (6, 1)-graphs?

For an integer q at least 5, let the $(q,q-5)$-graphs be those graphs in which every q vertices induce at most $q-5$ distinct $P_5$s. Do the (triangle-free) $(q,q-5)$-graphs allow a similar decomposition as the $(q,q-4)$-graphs [5, 7]? Do these graphs have nice structural features?