# Star (graph theory)

In graph theory, a **star** *S*_{k} is the complete bipartite graph *K*_{1,k}: a tree with one internal node and *k* leaves (but, no internal nodes and *k* + 1 leaves when *k* ≤ 1). Alternatively, some authors define *S*_{k} to be the tree of order *k* with maximum diameter 2; in which case a star of *k* > 2 has *k* − 1 leaves.

Star | |
---|---|

The star S. (Some authors index this as _{7}S.)_{8} | |

Vertices | k+1 |

Edges | k |

Diameter | minimum of (2, k) |

Girth | ∞ |

Chromatic number | minimum of (2, k + 1) |

Chromatic index | k |

Properties | Edge-transitive Tree Unit distance Bipartite |

Notation | S_{k} |

Table of graphs and parameters |

A star with 3 edges is called a **claw**.

The star *S*_{k} is edge-graceful when *k* is even and not when *k* is odd. It is an edge-transitive matchstick graph, and has diameter 2 (when *k* > 1), girth ∞ (it has no cycles), chromatic index *k*, and chromatic number 2 (when *k* > 0). Additionally, the star has large automorphism group, namely, the symmetric group on k letters.

Stars may also be described as the only connected graphs in which at most one vertex has degree greater than one.

## Relation to other graph familiesEdit

Claws are notable in the definition of claw-free graphs, graphs that do not have any claw as an induced subgraph.^{[1]}^{[2]} They are also one of the exceptional cases of the Whitney graph isomorphism theorem: in general, graphs with isomorphic line graphs are themselves isomorphic, with the exception of the claw and the triangle *K*_{3}.^{[3]}

A star is a special kind of tree. As with any tree, stars may be encoded by a Prüfer sequence; the Prüfer sequence for a star *K*_{1,k} consists of *k* − 1 copies of the center vertex.^{[4]}

Several graph invariants are defined in terms of stars. Star arboricity is the minimum number of forests that a graph can be partitioned into such that each tree in each forest is a star,^{[5]} and the star chromatic number of a graph is the minimum number of colors needed to color its vertices in such a way that every two color classes together form a subgraph in which all connected components are stars.^{[6]} The graphs of branchwidth 1 are exactly the graphs in which each connected component is a star.^{[7]}

## Other applicationsEdit

The set of distances between the vertices of a claw provides an example of a finite metric space that cannot be embedded isometrically into a Euclidean space of any dimension.^{[8]}

The star network, a computer network modeled after the star graph, is important in distributed computing.

A geometric realization of the star graph, formed by identifying the edges with intervals of some fixed length, is used as a local model of curves in tropical geometry. A tropical curve is defined to be a metric space that is locally isomorphic to a star shaped metric graph.

## ReferencesEdit

Wikimedia Commons has media related to .Star graphs |

**^**Faudree, Ralph; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Claw-free graphs — A survey",*Discrete Mathematics*,**164**(1–3): 87–147, doi:10.1016/S0012-365X(96)00045-3, MR 1432221.**^**Chudnovsky, Maria; Seymour, Paul (2005), "The structure of claw-free graphs",*Surveys in combinatorics 2005*(PDF), London Math. Soc. Lecture Note Ser.,**327**, Cambridge: Cambridge Univ. Press, pp. 153–171, MR 2187738.**^**Whitney, Hassler (January 1932), "Congruent Graphs and the Connectivity of Graphs",*American Journal of Mathematics*,**54**(1): 150–168, doi:10.2307/2371086, JSTOR 2371086.**^**Gottlieb, J.; Julstrom, B. A.; Rothlauf, F.; Raidl, G. R. (2001). "Prüfer numbers: A poor representation of spanning trees for evolutionary search" (PDF).*GECCO-2001: Proceedings of the Genetic and Evolutionary Computation Conference*. Morgan Kaufmann. pp. 343–350. ISBN 1558607749.**^**Hakimi, S. L.; Mitchem, J.; Schmeichel, E. E. (1996), "Star arboricity of graphs",*Discrete Math.*,**149**: 93–98, doi:10.1016/0012-365X(94)00313-8**^**Fertin, Guillaume; Raspaud, André; Reed, Bruce (2004), "Star coloring of graphs",*Journal of Graph Theory*,**47**(3): 163–182, doi:10.1002/jgt.20029.**^**Robertson, Neil; Seymour, Paul D. (1991), "Graph minors. X. Obstructions to tree-decomposition",*Journal of Combinatorial Theory*,**52**(2): 153–190, doi:10.1016/0095-8956(91)90061-N.**^**Linial, Nathan (2002), "Finite metric spaces–combinatorics, geometry and algorithms",*Proc. International Congress of Mathematicians, Beijing*,**3**, pp. 573–586, arXiv:math/0304466, Bibcode:2003math......4466L