9
$\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?

Improve this question
$\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$
    – Dima Pasechnik
    Jul 31, 2014 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$
    – Dima Pasechnik
    Jul 31, 2014 at 20:34
  • $\begingroup$ smallest connected can be both smallest vertex connected and smallest edge connected. $\endgroup$
    – user39815
    Jul 31, 2014 at 20:39
  • $\begingroup$ I don't understand. The number of vertices and the number of edges are already GIVEN! $\endgroup$
    – Dima Pasechnik
    Jul 31, 2014 at 20:43
  • 2
    $\begingroup$ ok, i edited the question as to make it clear here. $\endgroup$
    – Dima Pasechnik
    Jul 31, 2014 at 21:11

1 Answer 1

Reset to default
9
$\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.

Improve this answer
$\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$
    – Joseph O'Rourke
    Jul 31, 2014 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.