Conference graph
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, − 1 ± v 2 , {\displaystyle {\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.
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.[1]
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.[2] The next smallest, v = 65, was found over 4 decades later in 2021.[3][4] As of now, the smallest open case is v = 85.[4]
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,
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.
References
[edit]- ^ Brouwer, A.E.; Cohen, A.M.; Neumaier, A. (1989). Distance Regular Graphs (PDF). Berlin, New York: Springer-Verlag. ISBN 978-3-540-50619-5.
- ^ Mathon, Rudolf (1978). "Symmetric Conference Matrices of Order pq² + 1". Canadian Journal of Mathematics. 30 (2): 321–331. doi:10.4153/CJM-1978-029-1.
- ^ Gritsenko, Oleg (2021). "On strongly regular graph with parameters (65; 32; 15; 16)". arXiv:2102.05432 [math.CO].
- ^ a b Brouwer, Andries E.; Van Maldeghem, Hendrik (2022). "8.2 Conference matrices and conference graphs". Strongly regular graphs (PDF). New Mathematical Monographs. Vol. 41. American Mathematical Society. pp. 189–190. ISBN 978-1-316-51203-6.
External links
[edit]- (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.
 | This graph theory-related article is a stub. You can help Wikipedia by adding missing information. |