Star (graph theory)

A star graph, short Star, in graph theory is a class of graphs of simple structure. In a star graph a central node to all other nodes connected by edges, and the other nodes have no further neighbors in addition to said central node. Star graph with edges are denoted by or. A network topology in the form of a star graph is called a star topology.

Definition

A star graph, also called Star, is an undirected graph consisting of the nodes

And edges

Which is usually assumed. The node is called the center of the star, the central node or star node. Occasionally a star graph with node is also designated.

Properties

Below are just a star graphs are considered to consist of at least three nodes.

• A star graph is a tree, ie a connected acyclic undirected graph without multiple edges. Most of the central node is selected as the root of the tree; then the tree has height one.
• A star graph is a complete bipartite graph in which the class one partition from the central node and the other partition of the other node is class.
• The average degree of the nodes in a star graph is two, the diameter is two and also the average distance between two nodes with a little less than two.
• The line graph of the star graph is the complete graph. Conversely, there is no graph having line graph is a star graph with more than three nodes.
• The chromatic number of a star graph is two. An acceptable coloration is obtained by coloring the central node in one color and the other nodes in the different color. The chromatic polynomial of the star graphs.
• Each star graph has two graceful labels: in a central node with labeled at the other with; the remaining nodes will each receive the remaining numbers between and.
• The peripheral nodes of a star graph form a maximum stable set of the graph. The stability number of the star graph is therefore.