Conference graph

This article defines a property that can be evaluated to true/false for any undirected graph, and is invariant under graph isomorphism. Note that the term "undirected graph" as used here does not allow for loops or parallel edges, so there can be at most one edge between two distinct vertices, the edge is completely described by the vertices it joins, and there can be no edge from a vertex to itself.
View other such properties

Definition

A conference graph is a strongly regular graph with parameters $v,k=(v-1)/2,\lambda =(v-5)/4,\mu =(v-1)/4$. In other words, there is a positive integer $v$ such that:

1. The graph has $v$ vertices.
2. Every vertex of the graph has degree $(v-1)/2$.
3. For any two adjacent vertices, the number of vertices adjacent to both is $(v-5)/4$.
4. For any two non-adjacent vertices, the number of vertices adjacent to both is $(v-1)/4$.

Facts

• Note that for a conference graph on $v$ vertices to exist, a necessary condition is that $v$ be 1 mod 4. It turns out that a necessary and sufficient condition is that $v$ be 1 mod 4 and also be a sum of two squares. This in turn is equivalent to saying that it is a product of prime powers, each of which is 1 mod 4.
• The one-point graph can be considered a trivial example of a conference graph, though it is usually ignored.
• Paley graphs are conference graphs: In particular, this shows that there exists a conference graph on $q$ vertices whenever $q$ is a prime power that is 1 mod 4. In particular, this explicitly constructs conference graphs on vertex sets of size 5, 9, 13, 17, 25, 29.