Wikipedia gives a complete classification of these graphs: https://en.wikipedia.org/wiki/Homogeneous_graph#Classification which implies that the answer to your question is 'precisely when (n, k) is one of the following tuples': (0, 0); (2, 2); (4, 4); (a-1, ab) where a and b are positive integers; (ab, a-1) where a and b are positive integers.
Sent: Thursday, May 14, 2020 at 5:48 PM From: "Andy Latto" <andy.latto@pobox.com> To: "Dan Asimov" <dasimov@earthlink.net>, "math-fun" <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Graph question
On Thu, May 14, 2020 at 11:02 AM Dan Asimov <dasimov@earthlink.net> wrote:
Question: --------- Given a pair of positive integers (n,k), when does there exist a homogeneous graph G such that
* every vertex has valence n, and
* every vertex has just k vertices that are not adjacent to it
???
I left out your definition of "homogeneous" (which is an interesting definition; I would be surprised if this concept didn't already exist in graph theory, possibly under some other name) because your conjecture is false even if you remove the word "homogeneous".
if n and k are both odd, then you are looking for a graph with n+k+1 vertices, each of which has odd degree, which is impossible.
Andy
—Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun