| Star | |
|---|---|
 The star S7. |
|
| Vertices | k+1 |
| Edges | k |
| Diameter | 2 |
| Girth | ∞ |
| Chromatic number | 2 |
| Chromatic index | k |
| Properties | Edge-transitive Tree Unit distance Bipartite |
| Notation | Sk |
In graph theory, a star Sk is the complete bipartite graph K1,k, a tree with one internal node and k leaves. A star with 3 edges is called a claw.
The star Sk is edge-graceful when k is even and not when k is odd. It is edge-transitive, unit distance and has diameter 2, girth ∞, chromatic index k and chromatic number 2.
Relation to other graph families
Claws are notable in the definition of claw-free graphs, graphs that do not have any claw as an induced subgraph.[1][2]
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 K1,k consists of k − 1 copies of the center vertex.[3]
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,[4] 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.[5]
Other applications
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.[6]
The star network, a computer network modeled after the star graph, is important in distributed computing.
References
- ^ Faudree, Ralph; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Claw-free graphs — A survey", Discrete Mathematics 164 (1–3): 87–147, doi:, MR1432221.
- ^ Chudnovsky, Maria; Seymour, Paul (2005), "The structure of claw-free graphs", Surveys in combinatorics 2005, London Math. Soc. Lecture Note Ser., 327, Cambridge: Cambridge Univ. Press, pp. 153–171, MR2187738, http://publications.ias.edu/files/2005/02/u:4_p:180____claws_survey.pdf.
- ^ Gottlieb, J.; Julstrom, B. A.; Rothlauf, F.; Raidl, G. R. (2001), "Prüfer numbers: A poor representation of spanning trees for evolutionary search", Proc. Genetic and Evolutionary Computation Conference, Morgan Kaufmann, pp. 343–350, http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf.
- ^ Hakimi, S. L.; Mitchem, J.; Schmeichel, E. E. (1996), "Star arboricity of graphs", Discrete Math. 149: 93–98, doi:
- ^ Fertin, Guillaume; Raspaud, André; Reed, Bruce (2004), "Star coloring of graphs", Journal of Graph Theory 47 (3): 163–182, doi:.
- ^ Linial, Nathan (2002), "Finite metric spaces–combinatorics, geometry and algorithms", Proc. International Congress of Mathematicians, Beijing, 3, pp. 573–586, arΧiv:math/0304466
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
