Degree sequence of connected graphs
Given graph degree sequence . What is the condition that it can be degree sequence of connected graph. Can anyone please share link to theorem?
Solution 1:
Note that there are two notions here which should be distinguished: potentially and forcibly realizable sequences.
Let $d=(d_1,\ d_2,\ \cdots,\ d_n)$ be a degree sequence, increasingly ordered $$d_1 \le d_2 \le \cdots \le d_n$$
We say that $G$ is a realization of $d$ if the degree sequence of $G$ is equal to $d$.
We say that $d$ is forcibly connected if every realization of $d$ is connected.
We say that $d$ is potentially connected if there exists a realization of $d$ which is connected.
Analogous definitions hold for any property $P$ of graphs, in which we say that a sequence $d$ is potentially/forcibly $P$-realizable if some/every realization of $d$ satisfies $P$. There are some beautiful results related to such sequences. Regarding connectivity, here are some of the basic results.
Theorem 1 (Bondy and Boesch): Let $d=(d_1,\ \cdots,\ d_n)$ be a degree sequence. Let $k$ be an integer such that $1\le k \le n-1$. If $$d_i \le i + k - 2 \implies d_{n-k+1} \ge n-i$$ for $1 \le i \le \left\lfloor \frac{n-k+1}{2}\right\rfloor$, then $d$ is forcibly $k$-connected.
Theorem 2 (Bauer, Hakimi, Kahl, Schmeichel): Let $d=(d_1,\ \cdots,\ d_n)$ be a degree sequence. Let $\lambda \ge 1$ be an integer. If $d_1 \ge \lambda$ and $$d_{i-\lambda+1} \le i - 1 \land d_i \le i +\lambda -2 \implies d_n \ge n-i+\lambda-1$$ for $\lambda+1 \le i \le \left\lfloor\frac{n}{2}\right\rfloor$, then $d$ is forcibly $\lambda$-edge-connected.
Theorem 3: Let $d = (d_1,\ \cdots,\ d_n)$ be a degree sequence. Then $d$ is potentially connected if and only if $d_1 \ge 1$ and $$\sum_{i=1}^nd_i \ge 2(n-1)$$
Theorem 4 (Edmonds): Let $d = (d_1,\ \cdots,\ d_n)$ be a degree sequence. Then $d$ is potentially $\lambda$-edge-connected ($\lambda \ge 2$) if and only if $d_1 \ge \lambda$.
Theorem 5 (Wang & Kleitman): Let $d = (d_1,\ \cdots,\ d_n)$ be a degree sequence. Then $d$ is potentially $k$-connected ($k\ge 2$) if and only if $d_1 \ge k$ and $$\frac{1}{2}\sum_{i=1}^n d_i - \sum_{i=n-k}^n d_i + \frac{(k-1)(k-2)}{2} \ge n-k$$
There is also an interesting result regarding degree sets, i.e. the multiplicities of the terms are not specified.
Theorem 6 (Kapoor, Polimeni & Wall): Let $S=\{s_1,\ \cdots,\ s_k\}$ be a set of positive integers. Then $S$ is realizable as the degree set of a connected graph. Moreover, we may take the order of the graph to be $M+1$ where $M$ is the largest member of $S$.
References (by theorem number):
1 and 2: Bauer, Hakimi, Kahl, Schmeichel. Sufficient Degree Conditions for $k$-Edge-Connectedness of a Graph.
3: Berge, Graphs and Hypergraphs. The result is not too difficult to prove using induction. There are quite a few other interesting results given in Berge's book. Especially relevant are sections of chapters 6 and 9.
4: Edmonds, Existence of $k$-edge-connected ordinary graphs with prescribed degrees.
5: Wang, Kleitman. On the existence of N-connected graphs with prescribed degrees ($n \ge 2$).
6: Kapoor, Polimeni, Wall. Degree sets for graphs, Fund. Math. 95 (1977) 189–194.
Solution 2:
Recently, there has been some new research on this problem. Delen and Cangul defined a new invariant for graphs (and degree sequences) called omega invariant which helps to determine many properties of all the realizations of a given degree sequence including connectedness, realizability, cyclicness, number of loops, multiple edges, chords, maximum cycle length etc., see [Delen, S., Cangul, I. N., A New Graph Invariant, Turkish Journal of Analysis and Number Theory, 6 (1), (2018), 30-33 DOI: 10.12691/tjant-6-1-4] for the definition and fundamental properties and [212) Delen, S., Cangul, I. N., Extremal Problems on Components and Loops in Graphs, Acta Mathematica Sinica, English Series, 35 (2) (2019), 161-171, https://doi.org/10.1007/s10114-018-8086-6, WOS:000458139300011 (https://link.springer.com/content/pdf/10.1007%2Fs10114-018-8086-6.pdf)] for some properties. Some results are as follows: If omega of a degree sequence is less than or equal to -4, all realizations of it must be disconnected. If omega is at least -2, then the realizations could be connected or disconnected (that is, DS is potentially connected). If omega = -2, then every connected realization must be acyclic (tree).If omega is non-negative, all realizations are cyclic, etc...
This new invariant also helps to prove many existing results like Edmonds' theorem.