8
$\begingroup$

Is there a known (efficient) algorithm to construct a non-connected graph with a given degree sequence (if it exists)?

Examples

  • The sequence $\{3, 2, 2, 2, 2, 2, 1\}$ has both connected and non-connected realizations as simple graphs:

    enter image description here

    All non-connected realizations of this sequence are isomorphic to the graph shown above. The algorithm should construct such a graph.

  • All realizations of the sequence $\{3, 3, 1, 1, 1, 1\}$ are connected (it's a forcibly connected sequence) and isomorphic to:

    enter image description here

    The algorithm should either fail on this sequence, or construct a connected graph like the one above.

To help with experimentation, the following is an exhaustive list of degree sequences of size $\le 7$ that have both connected and non-connected realizations:

{2, 2, 2, 1, 1}

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

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

Other interesting sequences: {4, 4, 4, 3, 3, 3, 3, 2, 2} and {4, 4, 4, 3, 3, 3, 2, 2, 1}. Both of these have a single non-connected realization (ignoring isomorphic duplicates) and none of the components of these realizations are cliques.

Improve this question
$\endgroup$
2
  • $\begingroup$ Start by forming and removing large dangling cliques. In your first case, the largest clique possible is a triangle. Picking the three largest degrees, this leaves an extra edge. You have a degree 1 vertex, so use it. You now have one component. In the second case, the largest clique possible is an edge. Picking the two largest degrees, that leaves four edges, which you have to use on all remaining vertices. Gerhard "Is Liking Maximal Cliques Today" Paseman, 2019.05.12. $\endgroup$
    – Gerhard Paseman
    May 12, 2019 at 15:50
  • 1
    $\begingroup$ @GerhardPaseman I was thinking along the same lines, but this is still far from a systematic way (i.e. an algorithm). Once you create a clique, it's not even clear if the remaining degrees can be wired up to form a simple graph (and deciding this is a highly non-trivial problem). $\endgroup$
    – Szabolcs Horvát
    May 12, 2019 at 16:42

1 Answer 1

Reset to default
6
$\begingroup$

A graphic degree sequence is called forcibly connected if all realizations are connected graphs. So, you want to know a given degree sequence is not forcibly connected and then to find a disconnected graph with the degree sequence. Not forcibly connected is also known as potentially disconnected. More generally, there exists literature of forcibly P and potentially P for some property P. These keywords may be helpful in finding results.

One recent paper I found that may be of interest to you is An efficient algorithm to test forcibly-connectedness of graphical degree sequences by K. Wang.

  • The complexity of the algorithm given in the paper is exponential, but the author performs some experiments showing the algorithm can be used in some cases.
  • The problem of testing forcibly connectedness is co-NP, the author believes co-NP hardness is open.
  • The bibliography of the paper points to some sufficient conditions for forcibly connectedness.

This literature deals with the decision problem rather than the construction you ask for. However, the hardness of the decision problem appears to be open. The algorithm in the paper works by partitioning the degree sequence into two parts and testing if each in graphic. The paper suggests some ways to speed up the purely naive approach of testing of splits, but the algorithm is still exponential. If you can split into to graphical sequences you can then construct the graph with the Havel–Hakimi algorithm on each smaller degree sequence.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ The problem is harder than I expected. I also found the Wang paper after having posted the question here, and the presented algorithm does indeed work in a way that makes it easy to add construction. $\endgroup$
    – Szabolcs Horvát
    May 12, 2019 at 19:16
  • 2
    $\begingroup$ "The complexity of the algorithm given in the paper is exponential". Erm... The "fool's algorithm" (split into 2 subsets in all possible ways and check whether both parts are graphic) is also exponential (the parts construction is polynomial after that). I am not sure what happens in the pseudo-code in Wang's paper after line 8. Is it just "observe the obvious and try the fool's algorithm if the problem is not solved yet" or I'm really missing some clever idea? $\endgroup$
    – fedja
    May 12, 2019 at 19:48
  • 1
    $\begingroup$ @fedja I briefly looked and it is better than the completely foolish approach, but obviously nothing so clever that it completely solves the problem. Essentially it looks at the degree sequence as a multiset and considers to the multiset to two types (even and odd). This avoids looking at set partitions which are duplicate as multiset partions and also throws odd things that don't work because of parity. $\endgroup$
    – John Machacek
    May 12, 2019 at 20:26

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.