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