A little (combinatorial) graph problem
For what 
is it possible to have a 
-regular graph on vertices?
I thought about this a little while last night: it’s equivalent to asking how many hollow (the diagonal is zero) symmetric binary 
matrices satisfy 
for all 
. I haven’t seen a way to exploit this equivalence, so maybe there is another approach that would be more fruitful.
Possibly relevant posts:
- A do-it-yourself random graph result (5/21/2008)
- Practical Graph Theory (2/18/2003)
- Connectedness of the set of feasible
-colorings (2/21/2007)
Nice warm up to start the day. At noon.
The answer is any n greater than k, provided nk is even. It’s pretty easy to construct example graphs with circulant connectivity matrices.
BTW, you forgot to sum the LHS of your equation. =D
Comment by Pete — 7/14/2008 @ 12:12 pm
heh, circulant matrices work, true. The LHS isn’t a sum. So, why won’t it work if nk is odd?
Comment by Alex — 7/14/2008 @ 1:47 pm
As stated, the LHS is a vector, which you’re saying is equal to the number k.
nk is the total number of vertex-edge pairs, which must be even since each edge touches 2 vertices. Or another way to look at it, it’s the number of nonzeros in the incidence matrix, which must be even since it’s symmetric hollow.
Comment by Pete — 7/14/2008 @ 2:01 pm
Oh. Thanks
Comment by Alex — 7/14/2008 @ 5:28 pm