A little (combinatorial) graph problem

July 14th, 2008 ~ Posted in: Mathematics

For what n is it possible to have a k-regular graph on n vertices?

I thought about this a little while last night: it’s equivalent to asking how many hollow (the diagonal is zero) symmetric binary n \times n matrices satisfy \|Ae_i\|_1 = k for all i. I haven’t seen a way to exploit this equivalence, so maybe there is another approach that would be more fruitful.

Mathematics ~

4 Responses to “A little (combinatorial) graph problem”

  • 1. Pete
    July 14th, 2008 at 12:12 pm

    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

  • 2. Alex
    July 14th, 2008 at 1:47 pm

    heh, circulant matrices work, true. The LHS isn’t a sum. So, why won’t it work if nk is odd?

  • 3. Pete
    July 14th, 2008 at 2:01 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.

  • 4. Alex
    July 14th, 2008 at 5:28 pm

    Oh. Thanks :P

This entry was posted on Monday, July 14th, 2008 at 8:30 am and is filed under Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply