2
$\begingroup$

Let $G$ be a graph on $n$ vertices. $G$ is allowed to have multiple edges but no loops. The degree sequence of $G$ is the tuple $(d_1,d_2,\ldots,d_n)$ with $d_1\geq d_2 \geq\cdots\geq d_n\geq 0$ obtained (inductively) as follows: $d_1$ is the highest degree of a vertex; $(d_2,\ldots,d_n)$ is the highest degree sequence in lexicographic order of a graph obtained by deleting a vertex of degree $d_1$ and its incident edges from $G$.

A tuple $D=(d_1,d_2,\ldots,d_n)$ is called graphic if there exist a graph with $n$ vertices, with possible multiple edges but no loops such that its degree sequence is $D$.

It is easy to show that $d_n=0$ for any graphic tuple. But of course there are other necessary conditions.

For instance $(2,2,0,0)$ is graphic with $G=(V,E)$, $V=\{1,2,3,4\}$, $E=\{[1−2],[1−2],[3−4],[3−4]\}$ whereas $(4,2,2,0)$ is not (there is no graph with $4$ vertices and with this degree sequence). However $(4,2,2,0,0)$ becomes graphic once the extra $0$ (corresponding to an extra vertex) is added. The example in this case is $V=\{1,2,3,4,5\}$, $E=\{[1−2],[1−2],[1−3],[1−3],[2−3],[2−3],[4−5],[4−5]\}$.

My question is the following: Is there a complete description of graphic tuples? For simple graphs this seems awfully close in flavour to the Erdös-Gallai Theorem. I was, however, not able to find a good reference online.

$\endgroup$
  • $\begingroup$ There can be more than one vertex with a maximal degree. Then what next? $\endgroup$ – Włodzimierz Holsztyński Oct 27 '16 at 3:32
  • 1
    $\begingroup$ If more than one vertex has maximal degree then for each vertex $v$ of maximal degree consider the graph $G_v=G\setminus\{v\}$ and calculate its degree sequence $D_v$. Then compare the $D_v$s lexicographically and choose the $v$ with the highest $D_v$. $\endgroup$ – Alex Oct 27 '16 at 3:41
  • 1
    $\begingroup$ indeed, one could make this lexicographic decision or one may consider more than one variation of your question. The other variant would call for a study of all sequences obtained by removals of arbitrary maximal vertices (one at the time, of course). $\endgroup$ – Włodzimierz Holsztyński Oct 27 '16 at 4:42
  • 1
    $\begingroup$ For simple graphs it is Erdös - Gallai theorem - why? They seem to consider sequence of degrees in the initial graph, without removing vertices. $\endgroup$ – Fedor Petrov Oct 27 '16 at 7:34
  • $\begingroup$ @FedorPetrov You're right. In the normal definition of degree sequences one does not delete vertices. But it seems awfully close in flavour. I shall edit my post accordingly. $\endgroup$ – Alex Oct 27 '16 at 8:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.