Degree-based graph construction

Details Degree-based graph construction Degree-based graph construction

2009-05-29

arxiv.org/abs/0905.4892v2

Mathematics

Combinatorics

12 pages, 1 figure

Scientific paper

Degree-based graph construction is an ubiquitous problem in network modeling, ranging from social sciences to chemical compounds and biochemical reaction networks in the cell. This problem includes existence, enumeration, exhaustive construction and sampling questions with aspects that are still open today. Here we give necessary and sufficient conditions for a sequence of nonnegative integers to be realized as a simple graph's degree sequence, such that a given (but otherwise arbitrary) set of connections from a arbitrarily given node are avoided. We then use this result to present a swap-free algorithm that builds {\em all} simple graphs realizing a given degree sequence. In a wider context, we show that our result provides a greedy construction method to build all the $f$-factor subgraphs embedded within $K_n\setminus S_k$, where $K_n$ is the complete graph and $S_k$ is a star graph centered on one of the nodes.

Affiliated with

Also associated with

No associations

Rating

Degree-based graph construction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Degree-based graph construction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Degree-based graph construction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-527414