.gif)
Star (graph theory)
Encyclopedia
In graph theory
, a star Sk is the complete bipartite graph
K1,k: a tree
with one internal node and k leaves (but, no internal nodes and k + 1 leaves when k ≤ 1). Alternatively, some authors define Sk to be the tree of order k with maximum 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 edge-graceful
when k is even and not when k is odd. It is an edge-transitive matchstick graph
, and has diameter 2 (when k > 1), girth ∞ (it has no cycles), chromatic index k, and chromatic number 2 (when k > 0).
Stars may also be described as the only connected graphs in which at most one vertex has degree
greater than one.
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.
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, 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. The graphs of branchwidth 1 are exactly the graphs in which each connected component is a star.
that cannot be embedded isometrically
into a Euclidean space
of any dimension.
The star network
, a computer network
modeled after the star graph, is important in distributed computing
.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a star Sk is the complete bipartite graph
Complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
K1,k: a tree
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
with one internal node and k leaves (but, no internal nodes and k + 1 leaves when k ≤ 1). Alternatively, some authors define Sk to be the tree of order k with maximum 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 edge-graceful
Edge-graceful labeling
In graph theory, an edge-graceful graph labeling is a type of graph labeling. This is a labeling for simple graphs, namely ones in which no two distinct edges connect the same two distinct vertices, no edge connects a vertex to itself, and the graph is connected. Edge-graceful labelings were first...
when k is even and not when k is odd. It is an edge-transitive matchstick graph
Matchstick graph
In geometric graph theory, a branch of mathematics, a matchstick graph is a graph that can be drawn in the plane in such a way that its edges are line segments with length one that do not cross each other. That is, it is a graph that has an embedding which is simultaneously a unit distance graph...
, and has diameter 2 (when k > 1), girth ∞ (it has no cycles), chromatic index k, and chromatic number 2 (when k > 0).
Stars may also be described as the only connected graphs in which at most one vertex has degree
Degree (graph theory)
In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum 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.A star is a special kind of tree
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
. As with any tree, stars may be encoded by a Prüfer sequence
Prüfer sequence
In combinatorial mathematics, the Prüfer sequence of a labeled tree is a unique sequence associated with the tree. The sequence for a tree on n vertices has length n − 2, and can be generated by a simple iterative algorithm...
; the Prüfer sequence for a star K1,k consists of k − 1 copies of the center vertex.
Several graph invariants are defined in terms of stars. Star arboricity
Arboricity
The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph.-Example:...
is the minimum number of forests that a graph can be partitioned into such that each tree in each forest is a star, and the star chromatic number
Star coloring
In graph-theoretic mathematics, a star coloring of a graph G is a vertex coloring in which every path on four vertices uses at least three distinct colors. Equivalently, in a star coloring, the induced subgraphs formed by the vertices of any two colors has connected components that are star graphs...
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. The graphs of branchwidth 1 are exactly the graphs in which each connected component is a star.
Other applications
The set of distances between the vertices of a claw provides an example of a finite metric spaceMetric space
In mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...
that cannot be embedded isometrically
Isometry
In mathematics, an isometry is a distance-preserving map between metric spaces. Geometric figures which can be related by an isometry are called congruent.Isometries are often used in constructions where one space is embedded in another space...
into a Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
of any dimension.
The star network
Star network
Star networks are one of the most common computer network topologies. In its simplest form, a star network consists of one central switch, hub or computer, which acts as a conduit to transmit messages...
, a computer network
Computer network
A computer network, often simply referred to as a network, is a collection of hardware components and computers interconnected by communication channels that allow sharing of resources and information....
modeled after the star graph, is important in distributed computing
Distributed computing
Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
.