Succession

Graph with drawn node degrees and the degree sequence 0,1,2,2,3,3,3

In graph theory, the ascending order of the nodal degrees of all nodes of a graph is called the degree sequence (or also valence sequence or degree sequence ) of a simple graph.

definition

The degree result of a simple graph with nodes and node levels is the result of natural numbers ${\displaystyle G=(V,E)}$ ${\displaystyle v_{1},v_{2},\ldots ,v_{n}\in V}$ ${\displaystyle d(v_{1})\leq d(v_{2})\leq \dots \leq d(v_{n})}$

${\displaystyle d_{1},d_{2},\ldots ,d_{n}}$,

where for each indicates the degree of the node . An increasing sequence of natural numbers is called graphical if there is at least one simple graph that shows this degree sequence. ${\displaystyle d_{i}=d(v_{i})}$ ${\displaystyle i=1,2,\dots ,n}$ ${\displaystyle v_{i}}$

Examples

Nicholas' house with node numbering

Succession

The House of Santa Claus has with node numbering in the picture alongside the node degrees and . Sorting by degree then results in the associated degree sequence . ${\displaystyle d(1)=d(2)=3,d(3)=d(4)=4}$ ${\displaystyle d(5)=2}$ ${\displaystyle 2,3,3,4,4}$

Graphic sequences

The result is graphical, since the graph shown at the beginning has exactly these degrees. The consequence is not graphical, for example, since no simple graph with three vertices can exist that has a vertex with degree four. ${\displaystyle 0,1,2,2,3,3,3}$ ${\displaystyle 1,3,4}$

use

Sequences of degrees are considered in graph theory with the Hamilton circle problem , especially in a theorem by Vašek Chvátal , which deduces statements about the existence of Hamilton circles by considering sequences of degrees.

literature

• Reinhard Diestel: graph theory . Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 pages).