Name
Abstract | ||
|---|---|---|
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 s-clique-power property if for every graph G∈G, every maximal clique in Gs 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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.dam.2014.04.016 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Clique,s-club,k-chordal graphs,AT-free graphs | Block graph,Discrete mathematics,Combinatorics,Forbidden graph characterization,Graph power,Interval graph,Chordal graph,Distance-hereditary graph,Pathwidth,Mathematics,Split graph | Journal |
Volume | ISSN | Citations |
174 | 0166-218X | 3 |
PageRank | References | Authors |
0.41 | 15 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Petr A. Golovach | 1 | 766 | 83.25 |
| Pinar Heggernes | 2 | 845 | 72.39 |
| Dieter Kratsch | 3 | 1957 | 146.89 |
| Arash Rafiey | 4 | 339 | 28.08 |