Circle graph

The circle graph , , and ${\displaystyle C_{3}}$ ${\displaystyle C_{4}}$ ${\displaystyle C_{5}}$ ${\displaystyle C_{6}}$

A circle graph , or circle for short , is a class of graphs with a simple structure in graph theory . A circle graph always has the same number of nodes as edges , whereby all nodes in the circle are connected to one another. Circle graphs with nodes are denoted by. A network topology in the form of a circular graph is called a ring topology . ${\displaystyle n}$ ${\displaystyle C_{n}}$

definition

A pie graph is an undirected graph consisting of the nodes ${\displaystyle C_{n}}$ ${\displaystyle (V,E)}$ ${\displaystyle n}$

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

and the edges ${\displaystyle n}$

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

whereby it is mostly assumed. A circle graph with nodes is also called a circle or cycle. ${\displaystyle n\geq 3}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

properties

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

• All circular graphs are connected , planar , cyclic , Eulerian and Hamiltonian .
• All circular graphs are 2-regular , that is, every node has degree two.
• The edge graph of the circle graph is isomorphic to its output graph , i.e. again a circle graph with nodes. ${\displaystyle C_{n}}$ ${\displaystyle n}$
• The diameter and the stability number of the circular graph are . ${\displaystyle C_{n}}$ ${\displaystyle \lfloor {\tfrac {n}{2}}\rfloor }$
• The chromatic number of the circle graph is two if is even and three if is odd. ${\displaystyle C_{n}}$ ${\displaystyle n}$ ${\displaystyle n}$
• The chromatic polynomial of the circle graph is . ${\displaystyle C_{n}}$ ${\displaystyle (-1)^{n}(\lambda -1)+(\lambda -1)^{n}}$
• All circular graphs are homeomorphic to one another . ${\displaystyle n\geq 2}$

Properties of special circular graphs are:

• The circle graph is a special triangle graph . ${\displaystyle C_{3}}$
• The circle graph is a special grid graph . ${\displaystyle C_{4}}$
• The pie graph is the smallest regular graph that is not strongly regular. ${\displaystyle C_{6}}$

See also

• Linear graph
• Star graph
• Ladder graph

literature

• Peter Tittmann: Graph Theory: An Application-Oriented Introduction . Hanser Verlag, 2003, ISBN 3-446-22343-6 .
• C. Vasudev: Graph theory with applications . New Age International, 2006, ISBN 81-224-1737-X .
• Walter D. Wallis: A Beginner's Guide to Graph Theory . 2nd Edition. Springer, 2007, ISBN 0-8176-4484-9 .

Individual evidence

1. ^ Vasudev: Graph theory with applications . 2006, p. 76 .
2. ^ Vasudev: Graph theory with applications . 2006, p. 50 .
3. ^ Vasudev: Graph theory with applications . 2006, p. 458 .
4. ↑ Tittmann: Graph Theory: An Application-Oriented Introduction . 2003, p. 35.60 .
5. ^ Wallis: A Beginner's Guide to Graph Theory . 2007, p. 94 .
6. ↑ Robert A. Wilson: Graphs, Colors and the Four-Color Theorem . Oxford University Press, 2002, pp. 101 .

Web links

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