Star (graph theory)

<h2 id="relation-to-other-graph-families">Relation to other graph families</h2>
Claws are notable in the definition of <a href="/facts/Claw-free_graph/P5FLH3uz">claw-free graphs</a>, graphs that do not have any claw as an <a href="/facts/Induced_subgraph/G3EUC0MQ">induced subgraph</a>.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a><a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> They are also one of the exceptional cases of the <a href="/facts/Whitney_graph_isomorphism_theorem/RWNxSy5j">Whitney graph isomorphism theorem</a>: in general, graphs with <a href="/facts/Graph_isomorphism/SBjVIhwW">isomorphic</a> <a href="/facts/Line_graph/RWNxSy5j">line graphs</a> are themselves isomorphic, with the exception of the claw and the triangle K3.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> 
A star is a special kind of <a href="/facts/Tree_(graph_theory)/TCWk4Joy">tree</a>. As with any tree, stars may be encoded by a <a href="/facts/Pr%25C3%25BCfer_sequence/0tmI33Mm">Prüfer sequence</a>; the Prüfer sequence for a star K1,k consists of k − 1 copies of the center vertex.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
Several <a href="/facts/Graph_invariant/bjuIvgb1">graph invariants</a> are defined in terms of stars. <a href="/facts/Arboricity/JjfuCv8r">Star arboricity</a> is the minimum number of forests that a graph can be partitioned into such that each tree in each forest is a star,<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> and the <a href="/facts/Star_coloring/Husd65Fu">star chromatic number</a> 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.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> The graphs of <a href="/facts/Branchwidth/Cc7HEATJ">branchwidth</a> 1 are exactly the graphs in which each connected component is a star.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

<h2 id="other-applications">Other applications</h2>
The set of distances between the vertices of a claw provides an example of a finite <a href="/facts/Metric_space/gnBBRXtc">metric space</a> that cannot be embedded <a href="/facts/Isometry/K5wX8ah6">isometrically</a> into a <a href="/facts/Euclidean_space/R2UbzmzM">Euclidean space</a> of any dimension.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>
The <a href="/facts/Star_network/HPQDmFkI">star network</a>, a <a href="/facts/Computer_network/3w5RM99p">computer network</a> modeled after the star graph, is important in <a href="/facts/Distributed_computing/o5nyhqTF">distributed computing</a>. 
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 <a href="/facts/Tropical_geometry/fFy8Evgv">tropical geometry</a>. A tropical curve is defined to be a metric space that is locally isomorphic to a star-shaped metric graph.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Star_(simplicial_complex)/XKFeazex">Star (simplicial complex)</a> - a generalization of the concept of a star from a graph to an arbitrary simplicial complex.</li></ul>

Wikimedia Commons has media related to Star graphs.

<h2 id="references">References</h2>

<ol>
<li id="fn:1">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. <a href="/wiki/Ralph_Faudree" target="_blank">/wiki/Ralph_Faudree</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Chudnovsky, Maria; Seymour, Paul (2005), "The structure of claw-free graphs", Surveys in combinatorics 2005 (PDF), London Math. Soc. Lecture Note Ser., vol. 327, Cambridge: Cambridge Univ. Press, pp. 153–171, MR 2187738. <a href="/wiki/Maria_Chudnovsky" target="_blank">/wiki/Maria_Chudnovsky</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Whitney, Hassler (January 1932), "Congruent Graphs and the Connectivity of Graphs", American Journal of Mathematics, 54 (1): 150–168, doi:10.2307/2371086, hdl:10338.dmlcz/101067, JSTOR 2371086. <a href="/wiki/Hassler_Whitney" target="_blank">/wiki/Hassler_Whitney</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">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, archived from the original (PDF) on 2006-09-26 <a href="1558607749" target="_blank">1558607749</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Hakimi, S. L.; Mitchem, J.; Schmeichel, E. E. (1996), "Star arboricity of graphs", Discrete Math., 149 (1–3): 93–98, doi:10.1016/0012-365X(94)00313-8 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Fertin, Guillaume; Raspaud, André; Reed, Bruce (2004), "Star coloring of graphs", Journal of Graph Theory, 47 (3): 163–182, doi:10.1002/jgt.20029. <a href="/wiki/Bruce_Reed_(mathematician)" target="_blank">/wiki/Bruce_Reed_(mathematician)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">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. <a href="/wiki/Neil_Robertson_(mathematician)" target="_blank">/wiki/Neil_Robertson_(mathematician)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Linial, Nathan (2002), "Finite metric spaces–combinatorics, geometry and algorithms", Proc. International Congress of Mathematicians, Beijing, vol. 3, pp. 573–586, arXiv:math/0304466, Bibcode:2003math......4466L <a href="/wiki/Nati_Linial" target="_blank">/wiki/Nati_Linial</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
</ol>

Star (graph theory) open-in-new

Star (graph theory)