graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a star is the

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..Electronic edition page 17. Graph theory ...

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...

with one internal node and leaves (but no internal nodes and leaves when ). Alternatively, some authors define to be the tree of

order Order, ORDER or Orders may refer to: * A socio-political or established or existing order, e.g. World order, Ancien Regime, Pax Britannica * Categorization, the process in which ideas and objects are recognized, differentiated, and understood ...

with maximum

diameter In geometry, a diameter of a circle is any straight line segment that passes through the centre of the circle and whose endpoints lie on the circle. It can also be defined as the longest Chord (geometry), chord of the circle. Both definitions a ...

2; in which case a star of has leaves. A star with 3 edges is called a claw. The star is edge-graceful when is even and not when is odd. It is an

edge-transitive In geometry, a polytope (for example, a polygon or a polyhedron) or a Tessellation, tiling is isotoxal () or edge-transitive if its Symmetry, symmetries act Transitive group action, transitively on its Edge (geometry), edges. Informally, this mea ...

matchstick graph, and has diameter 2 (when ),

girth Girth may refer to: Mathematics * Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space * Girth (geometry), the perimeter of a parallel projection of a shape * Girth ...

∞ (it has no cycles),

chromatic index In graph theory, a proper edge coloring of a Graph (discrete mathematics), graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge colorin ...

, and

chromatic number In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...

2 (when ). Additionally, the star has large automorphism group, namely, the symmetric group on 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 graph In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw (graph theory), claw as an induced subgraph. A claw is another name for the complete bipartite graph K_ (that is, a star graph comprising three edges, ...

s, graphs that do not have any claw as an

induced subgraph In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges, from the original graph, connecting pairs of vertices in that subset. Definition Formally, let G=(V,E) ...

. They are also one of the exceptional cases of the

Whitney graph isomorphism theorem In the mathematics, mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edge (graph theory), edges of . is constructed in the following way: for each edge i ...

: in general, graphs with

isomorphic In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...

line graph In the mathematics, mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edge (graph theory), edges of . is constructed in the following way: for each edge i ...

s are themselves isomorphic, with the exception of the claw and the triangle . A star is a special kind of

. As with any tree, stars may be encoded by a Prüfer sequence; the Prüfer sequence for a star consists of copies of the center vertex. Several

graph invariant Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties * Graph (topology), a topological space resembling a graph in the sense of discre ...

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

Other applications

The set of distances between the vertices of a claw provides an example of a finite

metric space In mathematics, a metric space is a Set (mathematics), set together with a notion of ''distance'' between its Element (mathematics), elements, usually called point (geometry), points. The distance is measured by a function (mathematics), functi ...

that cannot be embedded isometrically into a

Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...

of any dimension. The

star network A star network is an implementation of a spoke–hub distribution paradigm in computer networks. In a star network, every host is connected to a central hub. In its simplest form, one central hub acts as a conduit to transmit messages. The ...

, a

computer network A computer network is a collection of communicating computers and other devices, such as printers and smart phones. In order to communicate, the computers and devices must be connected by wired media like copper cables, optical fibers, or b ...

modeled after the star graph, is important in

distributed computing Distributed computing is a field of computer science that studies distributed systems, defined as computer systems whose inter-communicating components are located on different networked computers. The components of a distributed system commu ...

. 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 In mathematics, tropical geometry is the study of polynomials and their geometric properties when addition is replaced with minimization and multiplication is replaced with ordinary addition: : x\oplus y=\min\, : x\otimes y=x+y. So for exampl ...

. A tropical curve is defined to be a metric space that is locally isomorphic to a star-shaped metric graph.

References

{{reflist Trees (graph theory) Parametric families of graphs

Relation to other graph families

Other applications

See also

References