8
$\begingroup$

For a given integer sequence $(d_1, d_2,...,d_n)$, a natural question is if such a sequence is graphical, i.e. is a degree sequence of some graph. According to Erdős–Gallai theorem, A sequence of non-negative integers $d_1\geq\cdots\geq d_n$ can be represented as the degree sequence of a finite simple graph on $n$ vertices if and only if $d_1+\cdots+d_n$ is even and

$\sum^{k}_{i=1}d_i\leq k(k-1)+ \sum^n_{i=k+1} \min(d_i,k)$ holds for $1\leq k\leq n.$

My questions are

(1) If Erdős–Gallai theorem holds, what is the condition that this graph is unique?

(2) If those graphs are not unique, how to find a connected graph with smallest connectivity among them?

$\endgroup$
8
  • 4
    $\begingroup$ in what sense can you talk about the smallest graph here? All such graphs have the same number of vertices and edges. $\endgroup$ Jul 31 '14 at 20:31
  • 1
    $\begingroup$ regarding the uniqueness, very few graphs are characterized by their degree sequences. E.g. cubic graphs (all $d_k=3$) on $n$ vertices form a very big family... $\endgroup$ Jul 31 '14 at 20:34
  • $\begingroup$ smallest connected can be both smallest vertex connected and smallest edge connected. $\endgroup$
    – user39815
    Jul 31 '14 at 20:39
  • $\begingroup$ I don't understand. The number of vertices and the number of edges are already GIVEN! $\endgroup$ Jul 31 '14 at 20:43
  • 2
    $\begingroup$ ok, i edited the question as to make it clear here. $\endgroup$ Jul 31 '14 at 21:11
8
$\begingroup$

A theorem of Hakimi says that any pair of degree-equivalent graphs can be obtained one from the other by a sequence of "elementary $2$-switchings" (probably known under many other names), which involve the subgraph switch on the subgraph induced by four vertices, as illustrated in one instance below.


  GDegSeqs
So whatever you seek to minimize (cf. the comments), likely it could be pursued by searching for the minimum via these $2$-switchings.


Hakimi, S. Louis. "On realizability of a set of integers as degrees of the vertices of a linear graph. I." Journal of the Society for Industrial & Applied Mathematics. 10.3 (1962): 496-506.

Hakimi, S. Louis. "On realizability of a set of integers as degrees of the vertices of a linear graph II. Uniqueness." Journal of the Society for Industrial & Applied Mathematics. 11.1 (1963): 135-147.

$\endgroup$
1
  • $\begingroup$ @RupeiXu: You are welcome :-). But perhaps the min-connectivity is not easy to find. It is a nice problem you have isolated, as superficially it is not clear if it is polynomial or NPC... $\endgroup$ Jul 31 '14 at 23:05

Your Answer

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