Star (graph theory)

Source: Wikipedia, the free encyclopedia.
Star
Chromatic index
k
PropertiesEdge-transitive
Tree
Unit distance
Bipartite
NotationSk
Table of graphs and parameters

In

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 Sk is

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

Claws are notable in the definition of

Whitney graph isomorphism theorem: in general, graphs with isomorphic line graphs are themselves isomorphic, with the exception of the claw and the triangle K3.[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 K1,k consists of k − 1 copies of the center vertex.[4]

Several

branchwidth 1 are exactly the graphs in which each connected component is a star.[7]

The star graphs S3, S4, S5 and S6.

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.[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.

See also

  • Star (simplicial complex)
    - a generalization of the concept of a star from a graph to an arbitrary simplicial complex.

References

Wikimedia Commons has media related to Star graphs.
  1. MR 1432221
    .
  2. MR 2187738
    .
  3. JSTOR 2371086
    .
  4. ISBN 1558607749
    .
  5. doi:10.1016/0012-365X(94)00313-8
  6. doi:10.1002/jgt.20029
    .
  7. doi:10.1016/0095-8956(91)90061-N
    .
  8. Bibcode:2003math......4466L
Retrieved from "https://en.wikipedia.org/w/index.php?title=Star_(graph_theory)&oldid=1198435685"