- Given a degree sequence, whether there exists a simple graph whose nodes satisfy the given degree sequence?
To solve the problem with 1 degree sequence, we have combinatorial recursive and matching approach as described
here
- Given a degree sequence and a template, does there exist a sub-graph (having the given degree sequence)
within the template? [P]
- Given 2 degree sequences, say red sequence and blue sequence, does there exist a simple graph (having edges
of red and blue colors) and satisfying the given degree sequences?
- Given 2 degree sequences, say red sequence and blue sequence, and a template, does there exist a sub-graph
(satisfying the given degree sequences) within the template? [NP-Hard]
- Given 3 (or more than 3 degree sequences) and a template, does there exist a sub-graph (satisfying the
given degree sequences) within the template? [NP Hard]
Linear Programming Characterization
Relevant Papers
-
[1] On Generating
Graphs with Prescribed Degree Sequences for Complex Network Modeling
Applications, Milena Mihail and Nisheeth Vishnoi.
-
[2] Random Walks on Colored
Graphs, Anne Condon and Diane Hernek.
-
[3] Upper Degree-Constrained
Partial Orientations, Harold N. Gabow.
-
[4] A local switch Markov
chain on given degree graphs with application in connectivity of Peer-to-Peer
networks, Amin Saberi, Milena Mihail, Adam Guetz and
Tomas Feder.
-
[5] A Sequential Algorithm
for Generating Random Graphs, Mohsen Bayati, Jeong Han Kim and
Amin Saberi.
-
[6] Efficient Generation of
Graphical Partitions, Tiffany M. Barnes and Carla D. Savage.
-
[7] A Recurrence for
Counting Graphical Partitions, Tiffany M.
Barnes and Carla D. Savage.
-
[8] A Remark concerning
Graphical Sequences, GeirDahl and Truls Flatberg.
Some Useful Links