{{Short description|Special case of a strongly regular graph}} [[File:Paley graph 9.svg|thumb|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|mathematics|Does there exist a conference graph for every number of vertices <math>v>1</math> where <math>v \equiv 1 \bmod 4</math> and <math>v</math> is an odd sum of two squares?}}
In the mathematical area of graph theory, a '''conference graph''' is a strongly regular graph with parameters ''v'', {{nowrap|1=''k'' = (''v'' − 1)/2,}} {{nowrap|1=λ = (''v'' − 5)/4,}} and {{nowrap|1=μ = (''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.<ref name="bcn89"> {{cite book |last1=Brouwer |first1=A.E. |last2=Cohen |first2=A.M. |last3=Neumaier |first3=A. |year=1989 |title=Distance Regular Graphs |location=Berlin, New York |publisher=Springer-Verlag |isbn=978-3-540-50619-5 |url=https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society-new-series/volume-24/issue-2/Review--A-E-Brouwer-A-M-Cohen-and-A/bams/1183656885.pdf}} </ref>
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.<ref>{{cite journal | last = Mathon | first = Rudolf | year = 1978 | title = Symmetric Conference Matrices of Order pq² + 1 | journal = Canadian Journal of Mathematics | volume = 30 | issue = 2 | pages = 321–331 | doi = 10.4153/CJM-1978-029-1 | doi-access = free }}</ref> The next smallest, ''v'' = 65, was found over 4 decades later in 2021.<ref>{{cite arxiv | last = Gritsenko | first = Oleg | year = 2021 | title = On strongly regular graph with parameters (65; 32; 15; 16) | eprint = 2102.05432 | class = math.CO }}</ref><ref name = "bv22">{{cite book | last1 = Brouwer | first1 = Andries E. | last2 = Van Maldeghem | first2 = Hendrik | title = Strongly regular graphs | chapter = 8.2 Conference matrices and conference graphs | pages = 189–190 | year = 2022 | publisher = American Mathematical Society | series = New Mathematical Monographs | volume = 41 | isbn = 978-1-316-51203-6 | url = https://homepages.cwi.nl/~aeb/math/srg/rk3/srgw.pdf }}</ref> As of now, the smallest open case is ''v'' = 85.<ref name = "bv22"/>
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, :<math>\frac{-1 \pm \sqrt v}{2} , </math> each with multiplicity {{nowrap|(''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.
==References== {{reflist}}
==External links== * {{oeis|A057653}}, odd numbers that are the sum of 2 squares * {{oeis|A085759}}, prime powers of the form 4n+1.
Category:Algebraic graph theory Category:Graph families Category:Strongly regular graphs {{graph-stub}}