Star graph

The star graphs , , and ${\displaystyle S_{3}}$ ${\displaystyle S_{4}}$ ${\displaystyle S_{5}}$ ${\displaystyle S_{6}}$

A star graph , or star for short , is a class of graphs with a simple structure in graph theory . In a star graph, a central node is connected to all other nodes by edges , while the other nodes apart from this central node have no further neighbors . Star graphs with edges are denoted by or . A network topology in the form of a star graph is called a star topology . ${\displaystyle n}$ ${\displaystyle S_{n}}$ ${\displaystyle K_{1,n}}$

definition

A star graph , also called a star, is an undirected graph consisting of the nodes ${\displaystyle S_{n}}$ ${\displaystyle n}$ ${\displaystyle (V,E)}$ ${\displaystyle n+1}$

${\displaystyle V=\{v_{0},\ldots ,v_{n}\}}$

and the edges ${\displaystyle n}$

${\displaystyle E=\{\{v_{0},v_{1}\},\{v_{0},v_{2}\},\ldots ,\{v_{0},v_{n}\}\}}$,

whereby it is mostly assumed. The knot is called the center of the star, central knot, or star knot. Sometimes a star graph with nodes is also referred to as. ${\displaystyle n\geq 2}$ ${\displaystyle v_{0}}$ ${\displaystyle n+1}$ ${\displaystyle S_{n+1}}$

properties

In the following, only star graphs consisting of at least three nodes are considered.

• A star graph is a tree , i.e. a connected acyclic undirected graph without multiple edges . Usually the central node is chosen as the root of the tree; the tree then has a height of one.
• A star graph is a completely bipartite graph in which one partition class consists of the central node and the other partition class consists of the remaining nodes. ${\displaystyle K_{1,n}}$ ${\displaystyle n}$
• The diameter is two and the mean distance between two nodes is slightly less than two. ${\displaystyle {\tfrac {2n}{n+1}}}$
• The edge graph of the star graph is the complete graph . Conversely, there is no graph whose edge graph is a star graph with more than three nodes. ${\displaystyle S_{n}}$ ${\displaystyle K_{n}}$
• The chromatic number of a star graph is two. A permissible coloring is obtained by coloring the central node in one color and the other nodes in the other color. The chromatic polynomial of the star graph is . ${\displaystyle S_{n}}$ ${\displaystyle \lambda (\lambda -1)^{n}}$
• Each star graph has two graceful labels : on one the central node is labeled with , on the other with ; the remaining nodes each receive the remaining numbers between and . ${\displaystyle 0}$ ${\displaystyle n}$ ${\displaystyle 0}$ ${\displaystyle n}$
• The peripheral nodes of a star graph form a maximally stable set of the graph. The stability number of the star graph is therefore . ${\displaystyle S_{n}}$ ${\displaystyle n}$

See also

• Circle graph
• Linear graph
• Ladder graph

literature

• Peter Tittmann: Graph Theory: An Application-Oriented Introduction . Hanser Verlag, 2003, ISBN 3-446-22343-6 .
• Walter D. Wallis: A Beginner's Guide to Graph Theory . 2nd Edition. Springer, 2007, ISBN 0-8176-4484-9 .

Individual evidence

1. ^ Eric W. Weisstein: CRC Concise Encyclopedia of Mathematics . 2nd Edition. CRC Press, 2010, pp. 2838 .
2. ^ Wallis: A Beginner's Guide to Graph Theory . 2007, p. 53 .
3. ↑ Tittmann: Graph Theory: An Application-Oriented Introduction . 2003, p. 23 .
4. ↑ Robert Sedgewick, Kevin Wayne, Kevin Wayne: Introduction to Programming with Java . Pearson, 2011, pp. 693-694 .
5. ↑ Tittmann: Graph Theory: An Application-Oriented Introduction . 2003, p. 69 .
6. ^ Wallis: A Beginner's Guide to Graph Theory . 2007, p. 94 .
7. ^ Wallis: A Beginner's Guide to Graph Theory . 2007, p. 126 .
8. ↑ Tittmann: Graph Theory: An Application-Oriented Introduction . 2003, p. 61 .

Web links

• Eric W. Weisstein : Star Graph . In: MathWorld (English).