Suppose a graph G means: * set V of points called vertices; * a collection E of unordered pairs of vertices called edges; * any two vertices have a path of edges connecting them: G is connected. (No edges from a vertex to itself, and no multiple edges between two vertices.) A subgraph H of G is a graph H whose vertices and edges belong to G. Call a graph G "homogeneous" if every isomorphism between subgraphs of G extends to an isomorphism of G with itself. 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 ??? —Dan
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
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
participants (3)
-
Adam P. Goucher -
Andy Latto -
Dan Asimov