TOPICS
Search

Claw Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
Claw

The complete bipartite graph K_(1,3) is a tree known as the "claw." It is isomorphic to the star graph S_4, and is sometimes known as the Y graph (Horton and Bouwer 1991; Biggs 1993, p. 147).

More generally, the star graph S_n=K_(1,n) is sometimes also known as a "claw" (Hoffmann 1960; Harary 1994, p. 17).

The claw graph has chromatic number 2 and chromatic polynomial

pi(z)=(z-1)^3z.

Its graph spectrum is (-sqrt(3))0^2sqrt(3).

A graph that does not contain the claw as an induced subgraph is called a claw-free graph.

See also

A Graph, Claw-Free Graph, Complete Bipartite Graph, E Graph, H Graph, Line Graph, R Graph, Star Graph

Explore with Wolfram|Alpha

References

Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, p. 147, 1993.Brandstädt, A.; Le, V. B.; and Spinrad, J. P. Graph Classes: A Survey. Philadelphia, PA: SIAM, p. 18, 1987.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Hoffman, A. J. "On the Uniqueness of the Triangular Association Scheme." Ann. Math. Stat. 31, 492-497, 1960.Horton, J. D. and Bouwer, I. Z. "Symmetric Y-Graphs and H-Graphs." J. Combin. Th. Ser. B 53, 114-129, 1991.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 12, 2000.

Cite this as:

Weisstein, Eric W. "Claw Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ClawGraph.html

Subject classifications