Star (graph theory)
Template:Short description Template:CS1 config <templatestyles src="Infobox graph/styles.css"/>Script error: No such module "Infobox".Template:Template other
In graph theory, a star SkScript error: No such module "Check for unknown parameters". is the complete bipartite graph K1,k :Script error: No such module "Check for unknown parameters". a tree with one internal node and kScript error: No such module "Check for unknown parameters". leaves (but no internal nodes and k + 1Script error: No such module "Check for unknown parameters". leaves when k ≤ 1Script error: No such module "Check for unknown parameters".). Alternatively, some authors define SkScript error: No such module "Check for unknown parameters". to be the tree of order Template:Mvar with maximum diameter 2; in which case a star of k > 2Script error: No such module "Check for unknown parameters". has k − 1Script error: No such module "Check for unknown parameters". leaves.
A star with 3 edges is called a claw.
The star SkScript error: No such module "Check for unknown parameters". is edge-graceful when Template:Mvar is even and not when Template:Mvar is odd. It is an edge-transitive matchstick graph, and has diameter 2 (when l > 1Script error: No such module "Check for unknown parameters".), girth ∞ (it has no cycles), chromatic index Template:Mvar, and chromatic number 2 (when k > 0Script error: No such module "Check for unknown parameters".). Additionally, the star has large automorphism group, namely, the symmetric group on Template:Mvar 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.[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 K3Script error: No such module "Check for unknown parameters"..[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,kScript error: No such module "Check for unknown parameters". consists of k − 1Script error: No such module "Check for unknown parameters". 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
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
<templatestyles src="Reflist/styles.css" />
- ↑ Script error: No such module "citation/CS1"..
- ↑ Script error: No such module "citation/CS1"..
- ↑ Script error: No such module "citation/CS1"..
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1"..
- ↑ Script error: No such module "citation/CS1"..
- ↑ Script error: No such module "citation/CS1".
Script error: No such module "Check for unknown parameters".