{{Short description|Tree graph with one central node and leaves of length 1}} {{CS1 config|mode=cs2}} {{infobox graph | name = Star | image = 180px | image_caption = The star {{math|''S''{{sub|7}}}}. (Some authors index this as {{math|''S''{{sub|8}}}}.) | namesake = | vertices = {{math|''k'' + 1}} | edges = {{mvar|k}} | radius = | diameter = 2 | girth = <math>\infty</math> | chromatic_number = 2 | chromatic_index = {{mvar|k}} | spectral_gap = 1 | properties = Edge-transitive<br>Tree<br>Unit distance<br>Bipartite | notation = {{math|''S''{{sub|''k''}}}} }}
In graph theory, the '''star''' {{math|''S''{{sub|''k''}}}} is the complete bipartite graph {{math|''K''{{sub|1, ''k''}}}}, that is, it is a tree with one internal node and {{mvar|k}} leaves{{efn|When {{math|''k'' ≥ 2}}; for {{math|''k'' {{=}} 0}}, it is the tree with one node, while for {{math|''k'' {{=}} 1}} it is the tree with two nodes, both of which are leaves.}}. Alternatively, some authors define {{math|''S''{{sub|''k''}}}} to be the tree of order {{mvar|k}} with maximum diameter 2, in which case a star of {{math|''k'' > 2}} has {{math|''k'' − 1}} leaves.
A star with 3 edges is called a '''claw'''.
The star {{math|''S''{{sub|''k''}}}} is edge-graceful when {{mvar|k}} is even and not when {{mvar|k}} is odd. It is an edge-transitive matchstick graph, and has diameter 2 (when {{math|''k'' > 1}}), girth <math>\infty</math> (it has no cycles), chromatic index {{mvar|k}}, and chromatic number 2 (when {{math|''k'' > 0}}). Additionally, the star has large automorphism group, namely, the symmetric group on {{mvar|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== Claws are notable in the definition of claw-free graphs, graphs that do not have any claw as an induced subgraph.<ref>{{citation | last1 = Faudree | first1 = Ralph | author1-link = Ralph Faudree | last2 = Flandrin | first2 = Evelyne | last3 = Ryjáček | first3 = Zdeněk | doi = 10.1016/S0012-365X(96)00045-3 | mr = 1432221 | issue = 1–3 | journal = Discrete Mathematics | pages = 87–147 | title = Claw-free graphs — A survey | volume = 164 | year = 1997| doi-access = free }}.</ref><ref>{{citation | last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician) | contribution = The structure of claw-free graphs | mr = 2187738 | location = Cambridge | pages = 153–171 | publisher = Cambridge Univ. Press | series = London Math. Soc. Lecture Note Ser. | title = Surveys in combinatorics 2005 | url = http://www.columbia.edu/~mc2775/claws_survey.pdf | volume = 327 | year = 2005 }}.</ref> 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 {{math|''K''{{sub|3}}}}.<ref>{{citation | last = Whitney | first = Hassler | author-link = Hassler Whitney | date = January 1932 | issue = 1 | journal = American Journal of Mathematics | jstor = 2371086 | pages = 150–168 | title = Congruent Graphs and the Connectivity of Graphs | volume = 54 | doi=10.2307/2371086| hdl = 10338.dmlcz/101067 | hdl-access = free }}.</ref>
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 {{math|''K''{{sub|1,''k''}}}} consists of {{math|''k'' − 1}} copies of the center vertex.<ref>{{citation |last1 = Gottlieb |first1 = J. |last2 = Julstrom |first2 = B. A. |last3 = Rothlauf |first3 = F. |last4 = Raidl |first4 = G. R. |chapter = Prüfer numbers: A poor representation of spanning trees for evolutionary search |pages = 343–350 |publisher = Morgan Kaufmann |title = GECCO-2001: Proceedings of the Genetic and Evolutionary Computation Conference |chapter-url = http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf |year = 2001 |isbn=1558607749 |archive-url = https://web.archive.org/web/20060926171652/http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf |archive-date = 2006-09-26 }}</ref>
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,<ref>{{citation | last1 = Hakimi | first1 = S. L. | last2 = Mitchem | first2 = J. | last3 = Schmeichel | first3 = E. E. | doi = 10.1016/0012-365X(94)00313-8 | journal = Discrete Math. | pages = 93–98 | title = Star arboricity of graphs | volume = 149 | year = 1996| issue = 1–3 | doi-access = free }}</ref> 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.<ref>{{citation | last1 = Fertin | first1 = Guillaume | last2 = Raspaud | first2 = André | last3 = Reed | first3 = Bruce | author3-link = Bruce Reed (mathematician) | journal = Journal of Graph Theory | title = Star coloring of graphs | volume = 47 | issue = 3 | pages = 163–182 | year = 2004 | doi = 10.1002/jgt.20029| url = https://hal.archives-ouvertes.fr/hal-00307788}}.</ref> The graphs of branchwidth 1 are exactly the graphs in which each connected component is a star.<ref>{{citation | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician) | last2 = Seymour | first2 = Paul D. | author2-link = Paul Seymour (mathematician) | doi = 10.1016/0095-8956(91)90061-N | issue = 2 | journal = Journal of Combinatorial Theory | pages = 153–190 | title = Graph minors. X. Obstructions to tree-decomposition | volume = 52 | year = 1991| doi-access = free }}.</ref>
class=skin-invert-image|thumb|600px|center|The star graphs {{math|''S''{{sub|3}}}}, {{math|''S''{{sub|4}}}}, {{math|''S''{{sub|5}}}} and {{math|''S''{{sub|6}}}}.
==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.<ref>{{citation | last = Linial | first = Nathan | author-link = Nati Linial | contribution = Finite metric spaces–combinatorics, geometry and algorithms | arxiv = math/0304466 | pages = 573–586 | title = Proc. International Congress of Mathematicians, Beijing | volume = 3 | year = 2002| bibcode = 2003math......4466L }}</ref>
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.
== See also == * Starlike tree - a tree with at most one vertex of degree larger than 2; a subdivision of a star * Star (simplicial complex) - a generalization of the concept of a star from a graph to an arbitrary simplicial complex.
==References== {{commonscat|Star graphs}} {{notelist}} {{reflist}}
Category:Trees (graph theory) Category:Parametric families of graphs