TOPICS
Search

Claw-Free Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
Claw

A claw-free graph is a simple graph that contains no induced subgraph isomorphic to the complete bipartite graph K_(1,3), known as the "claw graph" (illustrated above).

The line graph of any graph is claw-free, as is the complement of any triangle-free graph.

Classes of graphs that are claw-free include

1. antiprism graphs,

2. barbell graphs,

3. bishop graphs (and their connected components),

4. cocktail party graphs K_(n×2),

5. complete graphs,

6. cycle graphs,

7. empty graphs K^__n,

8. Hanoi graphs,

9. ladder rung graphs,

10. rook graphs,

11. line graphs,

12. lollipop graphs,

13. path graphs P_n,

14. Sierpiński gasket graphs,

15. triangular graphs, and

16. two-regular graphs.

Claw-FreeGraphs

The numbers of claw-free unlabeled simple graphs on n nodes for n=1, 2, ... are 1, 2, 4, 10, 26, 85, 302, 1285, 6170, ... (OEIS A086991; illustrated above).

ConnectedClaw-FreeGraphs

The numbers of claw-free unlabeled connected simple graphs on n nodes for n=1, 2, ... are 1, 1, 2, 5, 14, 50, 191, 881, 4494, 26389, 184749, 1728404, ... (OEIS A022562; illustrated above).

The maximum independent set problem, which is NP-hard on unrestricted simple graphs, can be solved in polynomial time on claw-free graphs. Minty (1980) gave an algorithm based on the maximum-weight matching algorithm of Edmonds (1965a). Nakamura and Tamura (2001, pp. 194-195 and 201) showed that Minty's weighted version fails in some cases and corrected it. The unweighted version is unaffected. Sbihi (1980) also gave an algorithm for finding an independent vertex set of maximum cardinality in a claw-free graph.

See also

Claw Graph, Complete Bipartite Graph, Forbidden Induced Subgraph, Line Graph, Perfect Matching

Portions of this entry contributed by Jonathan William Mugan

Explore with Wolfram|Alpha

References

Edmonds, J. "Maximum Matching and a Polyhedron with 0,1-Vertices." J. Res. Nat. Bur. Stand. B 69, 125-130, 1965a. https://doi.org/10.6028/jres.069B.013.Edmonds, J. "Paths, Trees, and Flowers." Canad. J. Math. 17, 449-467, 1965b. https://doi.org/10.4153/CJM-1965-045-4.Faudree, R.; Flandrin, E.; and Ryjáček, Z. "Claw-Free Graphs--A Survey." Disc. Math. 164, 87-147, 1997. https://doi.org/10.1016/S0012-365X(96)00045-3.Minty, G. J. "On Maximal Independent Sets of Vertices in Claw-Free Graphs." J. Combin. Th. B 28, 284-304, 1980. https://doi.org/10.1016/0095-8956(80)90074-X.Nakamura, D. and Tamura, A. "A Revision of Minty's Algorithm for Finding a Maximum Weight Stable Set of a Claw-Free Graph." J. Oper. Res. Soc. Japan 44, 194-204, 2001. https://doi.org/10.15807/jorsj.44.194.Sbihi, N. "Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile." Disc. Math. 29, 53-76, 1980. https://doi.org/10.1016/0012-365X(90)90287-R.Sloane, N. J. A. Sequences A022562 and A086991 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Claw-Free Graph

Cite this as:

Weisstein, Eric W., with contributions by Jonathan William Mugan. "Claw-Free Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Claw-FreeGraph.html

Subject classifications