Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Do we have any formula for counting the number of graphs with $n$ vertices, that has exactly $k$ vertices with degree $d$ and the other vertices have different and disjoint degrees? (Different and disjoint are the same, $d_1$ is different or disjoint rather than $d_2$, iff $d_1\neq‎ d_2$.)

For example, for $n=3, k=2, d=1$, we only have one graph($P_3$) with this property. Also, for $n=4, k=2, d=2$, we have the only graph with degree sequence $1, 2, 2, 3$.

share|improve this question
    
What is a "different and disjoint degree"? –  Igor Rivin Dec 16 '11 at 15:31
    
It is the same, $d_1$ is different or disjoint rather than $d_2$, iff $d_1\neq‎ d_2$. –  Shahrooz Janbaz Dec 16 '11 at 15:37
    
Since there isn't even a formula for regular graphs, there is no hope of a formula for this more general problem. –  Brendan McKay Dec 17 '11 at 3:41
    
I think the first example given is wrong; an edge and a vertex apart from it also works. –  Harry Altman Dec 17 '11 at 9:21

2 Answers 2

up vote 2 down vote accepted

The two examples you mention have a very nice generalization but the general counting problem seems hopeless. Let me start with the nice result. It is a fun (and easy) exercise to show that in any simple graph there are at least two vertices with the same degree. Define a $g(n,k,d)$ to be a simple unlabeled graph with $n$ vertices and $n-k+1$ distinct degrees, The degree $d$ taken by exactly $k$ vertices and some other $n-k$ degrees taken once each. Also, let $N(n,k,d)$ be the number of $g(n,k,d)$.

You make two interesting remarks. That $N(4,2,2)=1$ the graph having degrees $1,2,2,3$ (this is true) and that $N(3,2,1)=1$ because of the path $P_3.$ However this number is actually $2$ because the complement (an edge and an isolated vertex) is another example.

It turns out that for each $n \ge 2$ there are exactly two $g(n,2,d)$ : a connected one with $d=\lceil (n-1)/2 \rceil$ and the complement which is not connected and has $d=\lfloor (n-1)/2 \rfloor.$

I'm sure that this is well known but didn't find it in a short bit of looking around. The ingredients of an induction proof are the following operations:

  • The complement of a $g(n,k,d)$ is a $g(n,k,n-d-1).$
  • If an isolated vertex is added to a connected $g(n,k,d)$ then the result is a disconnected $g(n+1,k,d).$ And if the unique isolated vertex of a $g(n+1,k,d)$ is removed, the result is a $g(n,k,d.)$
  • If a new vertex is added to a $g(n,k,d)$ (connected or not) and then an edge is drawn to each old vertex, the result is a $g(n+1,k,d+1).$ And if a $g(n+1,k,d+1)$ has a unique vertex of degree $n$, it may be removed to obtain a $g(n,k,d).$

This leaves a few steps to fill in.

Mathscinet gives little information about On graphs having exact two vertices with the same degree. Nor about On graphs having exact three vertices with the same degree.

At the other extreme, the case $k=n$ of graphs regular of degree $d$ is reasonable but not trivial for $d=2.$ (In that it is the number of partitions of a certain type so at least has a name.) For larger $d$ it would be hopeless to get exact numbers for large $n$ . And the general case seems equally difficult. In a few isolated cases an answer might be fairly easy such as $k=n-2$ vertices of degree $1$ (or maybe $n-m$ for small $m$.)

share|improve this answer
    
Ok I found those articles (but have not read them with any care) ir.kagoshima-u.ac.jp/bitstream/10232/6217/1/… and ir.kagoshima-u.ac.jp/bitstream/10232/6228/1/… I had searched highly irregular graphs without success but it turns out that Behzad, M. and Chartrand, G. "No Graph is Perfect." Amer. Math. Monthly 74, 962-963, 1967. Gives the result on $g(n,2,d)$ –  Aaron Meyerowitz Dec 17 '11 at 8:48

You are looking for the enumeration of graphs with prescribed degree sequence. This is the subject of

Bender, E. A. and Canfield, E. R. (1978). The asymptotic number of labeled graphs with given degree sequences. J. Combinatorial Theory Ser. A 24, 3, 296–307.

McKay, B. D. and Wormald, N. C. (1990a). Asymptotic enumeration by degree sequence of graphs of high degree. European J. Combin. 11, 6, 565–580.

McKay, B. D. and Wormald, N. C. (1991). Asymptotic enumeration by degree sequence of graphs with degrees $o(n^{1/2}).$

These give asymptotic formulas. A numerical method for computing an estimate of the number of graphs with fixed (smallish) $n$ and a given degree sequence is given in:

http://www.people.fas.harvard.edu/~blitz/BlitzsteinDiaconisGraphAlgorithm.pdf

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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