I've been at this for a couple of days now and I guess I just can't find a decent bijection to combinatorics for this.

In the end what I really need is the probability of the graph to be connected / disconnected, but any 2 of the 3 numbers will get me that.

  • How many undirected graphs exist for a given a number of vertices $v$ and a degree $d$ if self-connections are allowed (but are discarded and not taken into account for equality purposes, so technically the degree ends up being $d$ or $d-1$ for all vertices in the graph)?
  • How many of these graphs are connected or disconnected?

I've been going at this with sieving. What I've got is that for any given $d$, there obviously exist graphs with $[\lceil\frac{v(d - 1)}{2}\rceil; vd]$ edges -- since two nodes can sample "overlapping" connections. Given that a $v$-vertex graph has $\frac{v(v-1)}{2}$ edge "slots", for each particular number of edges there obviously are $\binom{\frac{v(v-1)}{2}}{e}$ unique graphs. What I find particularly troublesome is sieving out the unneeded graphs. The $d$ parameter limits the lower (and upper) bound of every vertex's degree, i.e., for $v = 5,\, d = 2$ if we want all graphs with 5 edges, we take all graphs $\binom{10}{5}$ and sieve out the ones that contain a vertex with degree $0$ (the answer is 222, btw). This case is easy. I don't get how to sieve out graphs with one or more vertices of degree $1$. If I manage this sieving, then I can obviously find the total number of graphs by just summing the values for each particular number of edges.

The other part of the question about how to find the number of those graphs that are disconnected I don't even know where or how to begin.

The practical purpose that this came from is this: I have a large set of input data and a distance function that I can calculate for every two of the items. The distance function is expensive to calculate, but the distance property is strongly transitive. Calculating the full adjacency matrix is impossible and I'd like to minimize the number of distance calculations but still get a connected graph with some high enough probability. The amount of data is large enough to force parallelization, so each node would calculate a constant number of distances to randomly selected other nodes independently.

  • $\begingroup$ I don't understand what you mean by $A \rightarrow B$ or $A$ sampling a connection to $B$. The edge is either present or not. You also have your binomials upside down. If you want to pick $5$ of $10$ it is ${10 \choose 5}$ $\endgroup$ – Ross Millikan Feb 3 '13 at 23:07
  • $\begingroup$ You want to know the number of regular grpahs of degree $d$ on $v$ vertices. Even for $d=3$ I doubt there is a closed-form formula for this. You could calculate the first few cases and then look it up at the Online Encyclopedia of Integer Sequences to get some useful information. $\endgroup$ – Gerry Myerson Feb 3 '13 at 23:26
  • $\begingroup$ @RossMillikan Sorry 'bout that, I've been at this for too long I guess. You're right about the edges, it's just an undirected graph. Added some clarifications and explained the practical purpose in the last paragraph. The "sampling" esentially means that self-connections are allowed during construction but are discarded later. $\endgroup$ – TC1 Feb 3 '13 at 23:26
  • $\begingroup$ @GerryMyerson Yeah, relaxing this to $d$-regular graphs didn't help me much so I didn't bother and somehow started getting the idea that I've stumbled upon something messy. I'm guessing that getting the number of disconnected graphs won't be viable too... $\endgroup$ – TC1 Feb 3 '13 at 23:30

Presumably the problem shouldn't get harder if we drop the possibility to have degree $d-1$ and just try to count the $d$-regular graphs on $v$ labeled vertices. The answers to this MO question say that no closed form is known for this, so I doubt you'll find one for your problem. They do give asymptotic results and potentially useful references, though. You might also want to take a look at the MathWorld article on regular graphs.

Regarding connected and disconnected graphs, note that quite generally whenever a property of graphs is such that a graph has the property if and only if all its connected components have the property, then the exponential generating functions $g(x)$ for the number of graphs with the property and $c(x)$ for the number of non-empty connected graphs with the property are related by $g(x) = \exp(c(x))$. Thus, if you can determine $g(x)$, which will generally be easier than determining $c(x)$ directly, you can get $c(x)$ as $\log g(x)$.

  • $\begingroup$ So, would the 2nd paragraph mean that the number of connected $d$-regular graphs is logarithmic of all $d$-regular graphs? This seems rather counter-intuitive, at least a quick Python script that I did produces results the other way around, and these two sequences say otherwise... $\endgroup$ – TC1 Feb 4 '13 at 0:10
  • $\begingroup$ @TC1: There are a number of errors in that comment. First, taking the logarithm of a generating function is quite different from taking the logarithm of a single count. You might want to read up on generating functions, e.g. in this book, or in particular on exponential generating functions in these excellent notes. Second, while the relationship between the counts isn't logarithmic, there are indeed fewer connected graphs than general graphs with a property, not vice versa. $\endgroup$ – joriki Feb 4 '13 at 0:19
  • 1
    $\begingroup$ @TC1: Third, the sequences you link to don't show the number of $d$-regular graphs but the number of regular graphs. Whereas the property of being $d$-regular is of the kind I mention in the second paragraph, the property of being regular isn't, since a graph with only regular connected components need not be regular. $\endgroup$ – joriki Feb 4 '13 at 0:21
  • $\begingroup$ Thanks, things about generating functions start to dawn up somewhere in the back of my head now, it's been a while since I took combinatorics. Thanks for the pointers. $\endgroup$ – TC1 Feb 4 '13 at 0:25
  • $\begingroup$ @TC1: To give you an example: A001205 has the number of $2$-regular graphs and gives the exponential generating function $\exp(-x/2-x^2/4)/\sqrt{1-x}$. The logarithm is $-x/2-x^2/4-\frac12\log(1-x)$. Expanding that, you find that there are $(n-1)!/2$ non-empty connected $2$-regular graphs on $n$ vertices, beginning with $n=3$, which is right, since a connected $2$-regular graph is a cycle. $\endgroup$ – joriki Feb 4 '13 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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