Star  

The star S_{7}. (Some authors index this as S_{8}.)


Vertices  k+1 
Edges  k 
Diameter  minimum of (2, k) 
Girth  ∞ 
Chromatic number  minimum of (2, k + 1) 
Chromatic index  k 
Properties  Edgetransitive Tree Unit distance Bipartite 
Notation  S_{k} 
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.
A star with 3 edges is called a claw.
The star S_{k} is edgegraceful when k is even and not when k is odd. It is an edgetransitive 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 families[edit]
Claws are notable in the definition of clawfree 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 applications[edit]
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.
References[edit]
Wikimedia Commons has media related to Star graphs. 
 ^ Faudree, Ralph; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Clawfree graphs — A survey", Discrete Mathematics 164 (1–3): 87–147, doi:10.1016/S0012365X(96)000453, MR 1432221.
 ^ Chudnovsky, Maria; Seymour, Paul (2005), "The structure of clawfree 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", Proc. Genetic and Evolutionary Computation Conference (PDF), Morgan Kaufmann, pp. 343–350.
 ^ Hakimi, S. L.; Mitchem, J.; Schmeichel, E. E. (1996), "Star arboricity of graphs", Discrete Math. 149: 93–98, doi:10.1016/0012365X(94)003138
 ^ 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 treedecomposition", Journal of Combinatorial Theory 52 (2): 153–190, doi:10.1016/00958956(91)90061N.
 ^ Linial, Nathan (2002), "Finite metric spaces–combinatorics, geometry and algorithms", Proc. International Congress of Mathematicians, Beijing 3, pp. 573–586, arXiv:math/0304466
This page uses Creative Commons Licensed content from Wikipedia. A portion of the proceeds from advertising on Digplanet goes to supporting Wikipedia.