star (graph theory)
{{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 = ∞
| chromatic_number = 2
| chromatic_index = {{mvar|k}}
| spectral_gap = 1
| properties = Edge-transitive
Tree
Unit distance
Bipartite
| notation = {{math|S{{sub|k}}}}
}}
In graph theory, a star {{math|S{{sub|k}}}} is the complete bipartite graph {{math|K{{sub|1,k}} :}} a tree with one internal node and {{math|k}} leaves (but no internal nodes and {{math|k + 1}} leaves when {{math|k ≤ 1}}). 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|l > 1}}), girth ∞ (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.{{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
}}.{{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
}}. 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}}}}.{{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
}}.
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.{{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
}}
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,{{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
}} 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.{{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}}. The graphs of branchwidth 1 are exactly the graphs in which each connected component is a star.{{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
}}.
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.{{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
}}
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
- Star (simplicial complex) - a generalization of the concept of a star from a graph to an arbitrary simplicial complex.
References
{{commonscat|Star graphs}}
{{reflist}}