Growing without cloning

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

A graph G is claw-free if no induced subgraph of it is isomorphic to the complete bipartite graph K 1,3, and it is prime if |V (G)| ≥ 4 and there is no X V (G) with 1 < |X| < |V (G)| such that every vertex of V (G) \ X with a neighbor in X is adjacent to every vertex of X. In particular, if G is prime, then both G and G c are connected. This paper has two main results. The first one is that if G is a prime graph that is not a member of a particular family of exceptions, and H is a prime induced subgraph of G, then (up to isomorphism) G can be grown from H, adding one vertex at a time, in such a way that all the graphs constructed along the way are prime induced subgraphs of G. A simplicial clique in G is a nonempty clique K such that for every k ∈ K the set of neighbors of k in V (G) \ K is a clique. Our second result is that a prime claw-free graph G has at most |V (G)| + 1 simplicial cliques, and we give an algorithm to find them all with running time O(|V (G)| 4). In particular, this answers a question of Prasad Tetali [private communication] who asked if there is an efficient algorithm to test if a claw-free graph has a simplicial clique. Finally, we apply our results to claw-free graphs that are not prime. Such a graph may have exponentially many simplicial cliques, so we cannot list them all in polynomial time, but we can in a sense describe them.

Original languageEnglish (US)
Pages (from-to)860-880
Number of pages21
JournalSIAM Journal on Discrete Mathematics
Volume26
Issue number2
DOIs
StatePublished - Sep 6 2012

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Claw-free graphs
  • Induced subgraphs
  • Prime graphs
  • Simplicial clique
  • Splitter theorem

Fingerprint Dive into the research topics of 'Growing without cloning'. Together they form a unique fingerprint.

Cite this