For a positive integer s, an s-club in a graph G is a set of vertices that induces a subgraph of G of diameter at most s. We study a relation of clubs and cliques. For a positive integer s, we say that a graph class G has the sclique-power property if for every graph G ∈ G, every maximal clique in G s is an s-club in G. Our main combinatorial results show that both 4-chordal graphs and AT-free graphs have the s-clique-power property for all s ≥ 2. This has various algorithmic consequences. In particular we show that a maximum s-club in G can be computed in polynomial time when G is a chordal bipartite or a strongly chordal or a distance hereditary graph. On weakly chordal graphs, we obtain a polynomial-time algorithm when s is an odd integer, which is best possible as the problem is NP-hard for even values of s. We complement these results by proving the NP-hardness of the problem for every fixed s on 4-chordal graphs. Finally, if G is an AT-free graph, we prove that the problem can be solved in polynomial time when s ≥ 2, which gives an interesting contrast to the fact that the problem is NP-hard for s = 1 on this graph class.
On a superclass of these graph classes, called weakly chordal graphs, it is NP-hard for even s and can be solved in polynomial time for odd s REF .
Finding clubs in graph classes
Discret. Appl. Math.
Discret. Appl. Math.
Mathematics Computer Science