8
votes
Is there a program implementation for generating all non-isomorphic graphs with a given degree sequence?
As far as I am aware, there is no such program. Also, it needs care to interpret gradpart's claims. Gradpart can make counts greater than one graph per machine instruction, which proves that it doesn'...
- 37.7k
6
votes
Accepted
Construct a non-connected graph with a given degree sequence
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 ...
- 7,875
5
votes
Eberhard-type theorems for Fisk triangulations?
This is only a partial answer.
First, a sphere does not admit Fisk triangulations. Fisk has proved it by using the 4-color theorem, but there is a simpler proof using Fisk's method of coloring ...
- 6,337
5
votes
Accepted
A simple requirement for a degree sequence to be graphical
Answering my own question: Almost exactly this result was proved in:
Igor E Zverovich and Vadim E Zverovich. Contributions to the theory of graphic sequences. Discrete Mathematics, 105(1):293–303, ...
- 37.7k
5
votes
Accepted
Simple graphs with prescribed degrees as disjoint union of simple subgraphs with prescribed degrees
The answer to this question is No.
Let us assume $V = \{1,2,3,4,5,6\}$ and consider degree sequences $a = [3,2,2,1,0,0]$, $b = [1,0,0,3,2,2]$ and $c = a+b = [4,2,2,4,2,2]$.
The only simple graph with ...
- 1,444
2
votes
Simple graphs with prescribed degrees as disjoint union of simple subgraphs with prescribed degrees
I think your property is true and can be shown recursively depending on the size $n$ of the graph.
Existence
For $n=2$ well one of the sequences has to be (0,0), so the other one is equal to $c$: it ...
- 21
2
votes
When is a large graph with a given degree sequence likely to be connected?
Second edition
This is a partial answer to the question per the "Clarification Update", but first I'll generalize a little. Suppose that for each $n$ we have a degree sequence $n_0,n_1,n_2,\ldots$, ...
- 37.7k
1
vote
When is a large graph with a given degree sequence likely to be connected?
I think for general random graphs with (very) high probability there cannot be two giant components. For the graph to be connected it should be enough to prove that no small cluster with just a ...
- 4,361
1
vote
When is a large graph with a given degree sequence likely to be connected?
Revised Edition to converge to the OP's notations, and slightly augmented.
Let $f_d$ be the distribution of the degrees, and $gF(u)= \Sigma_{0 \le d} f_d u^d $ its generating function; then I think ...
- 347
1
vote
Degree sequences after vertex removals
Several works study the degree sequence obtained when vertices are removed from random graphs with given degree sequence. Vertices are generally removed by decreasing order of degrees, or uniformly at ...
- 1,444
1
vote
Accepted
Eberhard-type theorems for Fisk triangulations?
Günter Rote has just shown me a (5,6,..,6,7) triangulation of the Klein-bottle where 5 and 7 are neighbors. He has also found several similar higher genus triangulations.
- 18.8k
Only top scored, non community-wiki answers of a minimum length are eligible