Conference graph

The Paley graph of order 9, for which v = 9, k = (v - 1)/2 = 4, λ = (v - 5)/4 = 1, and μ = (v − 1)/4 = 2

Unsolved problem in mathematics

Does there exist a conference graph for every number of vertices $v>1$ where $v\equiv 1{\bmod {4}}$ and $v$ is an odd sum of two squares?

More unsolved problems in mathematics

In the mathematical area of graph theory, a conference graph is a strongly regular graph with parameters v, k = (v − 1)/2, λ = (v − 5)/4, and μ = (v − 1)/4. It is the graph associated with a symmetric conference matrix, and consequently its order v must be 1 (modulo 4) and a sum of two squares.

Conference graphs are known to exist for all small values of v allowed by the restrictions, e.g., v = 5, 9, 13, 17, 25, 29, and (the Paley graphs) for all prime powers congruent to 1 (modulo 4). However, there are many values of v that are allowed, for which the existence of a conference graph is unknown. The smallest value of v which has no Paley graph but does have a conference graph is v = 45, found in 1978. The next smallest, v = 65, was found over 4 decades later in 2021. As of now, the smallest open case is v = 85.

The eigenvalues of a conference graph need not be integers, unlike those of other strongly regular graphs. If the graph is connected, the eigenvalues are k with multiplicity 1, and two other eigenvalues,

${\frac {-1\pm {\sqrt {v}}}{2}},$

each with multiplicity (v − 1)/2.

The complement of a conference graph is always a conference graph with the same parameters, and in many cases is self-complementary, such as for all the Paley graphs.

External links

• (sequence A057653 in the OEIS), odd numbers that are the sum of 2 squares
• (sequence A085759 in the OEIS), prime powers of the form 4n+1.