1
$\begingroup$

I am trying to generate a table of degree sequences for simple connected graphs for a given number of nodes.

Example output for $n=4$:

{{2, 2, 1, 1}, {3, 1, 1, 1}, {2, 2, 2, 2}, {3, 2, 2, 1}, {3, 3, 2, 
 2}, {3, 3, 3, 3}}

Each degree sequence like that follows five rules:

  1. $d_i \in \mathbb{Z} $;
  2. $1 \leq d_i\leq n-1 \quad \forall i \in [1,n]$;
  3. $d_1\geq d_2 \geq \cdots \geq d_n$;
  4. $\frac{\sum_{i=1}^n d_i}{2} \in \mathbb{Z}$ (the sum of degrees is even);
  5. $\sum_{i=1}^y d_i \leq y(y-1) + \sum_{i=y+1}^n \min (d_i,y) \quad \forall y \in [1,n]$.

I could technically use GraphData to get exactly the same sequence, but Wolfram's data is far from complete for any $n>8$, and I require this data for $n\geq 10$. For instance, for $n=10$ it lacks more than 90% of possible sequences.

Any hint would be appreciated.

Explanation of rules

Rule 1. just imposes a limitation that each entry in a degree sequence must be an integer;

Rule 2. limits the minimum and maximum degree in any sequence. In each connected simple network on $n$ nodes, each node cannot have more than $n-1$ connections (loops and multi-edges are not allowed in simple graphs), as well as each node cannot have less than $1$ connection (as I am interested in a family of connected graphs).

Rule 3. Ensures that each degree sequence is an ordered set.

Rule 4. Ensures that the sum of degrees in each network is even -- otherwise the network will have some disconnected edges.

Rule 5. Erdos-Gallai graphicality conditions ensure that one can build a connected graph with a given sequence. Technically, it verifies whether each given node does not have more connections that it can have given the number of connections of all other nodes.

Example how they work with a degree sequence $\{2,2,1,1\}$.

  1. $y=1$ verification for node $1$:

$$d_1 \leq 1(1-1)+\min[2,1]+\min[1,1]+\min[1,1],$$ $$2 \leq 3.$$

  1. $y=2$ verification for node $2$:

$$d_1 + d_2 \leq 2(2-1)+\min[1,2]+\min[1,2],$$ $$2 +2 \leq 4.$$

  1. $y=3$ verification for node $3$:

$$d_1 + d_2 +d_3 \leq 3(3-1)+\min[1,3],$$ $$2 +2 +1 \leq 6+1.$$

  1. $y=4$ verification for node $4$:

$$d_1 + d_2 +d_3 +d_4 \leq 4(4-1),$$ $$2 +2 +1+1 \leq 12.$$

$\endgroup$
4
  • $\begingroup$ This is still one step removed from a Mathematica problem, unless the functionality is already built in or present in e.g. IGraphM. If you can give us an algorithm to calculate those numbers or a reference to that algorithm, then we can help you implement it, but at the moment you are asking to do the whole job for you, and that's probably not going to attract much attention to your question. $\endgroup$
    – MarcoB
    Aug 4 at 15:00
  • $\begingroup$ It would also be really helpful if you defined all symbols in your formulae or perhaps explained at least the last formula in words. I for one do not intuitively understand the condition it is imposing. $\endgroup$
    – MarcoB
    Aug 4 at 15:02
  • $\begingroup$ @MarcoB Fair point, I will elaborate in the main body. $\endgroup$
    – Oleh
    Aug 4 at 15:03
  • 1
    $\begingroup$ @MarcoB I have tried to elaborate more in the main body. I will check IGraphM, it might actually have the required instrument. $\endgroup$
    – Oleh
    Aug 4 at 15:29

0

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.