0

Suppose I have a number of airports which have a set number of routes. Large airports have 7, medium airports have 4, and small airports have 1.

First of all, what would I call a graph of this type where it is undirected, has no parallel edges, no loops, and every edge is connected to another (that is no route goes unused)?

Second of all, how can I determine if I get a number number of airports if it'll work / is connected? Example: 1 large, 3 medium, and 7 small will produce a connected graph but that same combination with 8 small will not.

I'm writing a computer program and looking for a simple way to determine (using some theorem or whatnot) if it works or not. I've attached an image below of what I'm searching for.

Example

Seth Killian
  • 251

1 Answers1

1

Both the Erdős-Gallai Theorem and the Havel-Hakimi algorithm will determine whether a given degree sequence is graphical, that is whether there is a simple graph with that degree sequence. These results do not determine whether there is a connected graph with the given degree sequence. For that you need the following additional result:

Result 1. For a graphical degree sequence $d_1, d_2, \dots, d_n$, there is a connected graph with that degree sequence if and only if $\sum_{i=1}^{n} d_i \geq 2(n-1)$.

See this question for references on this result.

Because your degree sequence consists only of 1, 4 and 7, you could tailor your algorithm to this fact. The following is a simplified version of Erdős-Gallai:

Result 2. A degree sequence $d_1, d_2, \dots, d_n$ with $d_i \geq d_{i+1}$ for all $i=1,2,\dots,n-1$ is graphical if and only if $\sum_{i=1}^n d_i$ is even and for each $k$ with $d_k > d_{k+1}$ and for $k=n$,

$$\sum_{i=1}^k d_i \leq k(k-1) + \sum_{i=k+1}^n \mathrm{min}(d_i,k).$$

Now suppose $d_1 = d_2 = \dots = d_p = 7$, $d_{p+1} = d_{p+2} = \dots d_{p+q} = 4$, and $d_{p+q+1} = d_{p+q+2} = \dots = d_{p+q+r} = 1$, where $p+q+r=n$. Combining Results 1 and 2, we have:

There is a connected graph with such a degree sequence $d_1, d_2, \dots, d_n$ if and only if the following 5 conditions hold:

  1. $\sum_{i=1}^{n} d_i \geq 2(n-1)$

  2. $\sum_{i=1}^{n} d_i$ is even

  3. $\sum_{i=1}^p d_i \leq p(p-1) + \sum_{i=p+1}^n \mathrm{min}(d_i,p)$

  4. $\sum_{i=1}^{p+q} d_i \leq (p+q)(p+q-1) + \sum_{i=p+q+1}^n \mathrm{min}(d_i,p+q)$

  5. $\sum_{i=1}^n d_i \leq n(n-1)$

We can simplify each of these conditions to inequalities in terms of $p$, $q$, and $r$, for the final result:

Theorem. Given $d_1 = d_2 = \dots = d_p = 7$, $d_{p+1} = d_{p+2} = \dots d_{p+q} = 4$, and $d_{p+q+1} = d_{p+q+2} = \dots = d_{p+q+r} = 1$, there is a connected graph with degree sequence $d_1, d_2, \dots, d_{p+q+r}$ if and only if the following 5 conditions hold:

  1. $7p+4q+r \geq 2(p+q+r-1)$

  2. $7p+4q+r$ is even (either both $p$ and $r$ are even or both are odd)

  3. $7p \leq p(p-1) + q(\mathrm{min}(4,p)) + r$

  4. $7p+4q \leq (p+q)(p+q-1) + r$

  5. $7p+4q+r \leq (p+q+r)(p+q+r-1)$

Perry Elliott-Iverson
  • 4,462