Circle graph
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 .
definition
A pie graph is an undirected graph consisting of the nodes
and the edges
- ,
whereby it is mostly assumed. A circle graph with nodes is also called a circle or cycle.
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.
- The diameter and the stability number of the circular graph are .
- The chromatic number of the circle graph is two if is even and three if is odd.
- The chromatic polynomial of the circle graph is .
- All circular graphs are homeomorphic to one another .
Properties of special circular graphs are:
- The circle graph is a special triangle graph .
- The circle graph is a special grid graph .
- The pie graph is the smallest regular graph that is not strongly regular.
See also
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
- ^ Vasudev: Graph theory with applications . 2006, p. 76 .
- ^ Vasudev: Graph theory with applications . 2006, p. 50 .
- ^ Vasudev: Graph theory with applications . 2006, p. 458 .
- ↑ Tittmann: Graph Theory: An Application-Oriented Introduction . 2003, p. 35.60 .
- ^ Wallis: A Beginner's Guide to Graph Theory . 2007, p. 94 .
- ↑ 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).