TOPICS
Search

Conference Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A strongly regular graph with parameters (n,k,a,c) has graph eigenvalues k, theta, and tau, where

theta=((a-c)+sqrt(Delta))/2
(1)
tau=((a-c)-sqrt(Delta))/2
(2)

where

Delta=(a-c)^2+4(k-c)
(3)

(Godsil and Royle 2001, pp. 221-222). In the case of theta and tau distinct, call their multiplicities in the graph spectrum m_theta and m_tau. Then a graph with m_theta=m_tau is called a conference graph. All Paley graphs are conference graphs.

A strongly regular graph is either a conference graph, has theta and tau integers and theta-tau a perfect square (correcting a typo in Godsil and Royle 2001, p. 222), or both of the above (Godsil and Royle 2001, p. 222). Paley graphs P(q) with q a square number (including the (2,1)-generalized quadrangle, which is isomorphic to the 9-Paley graph) satisfy both conditions.

In the special case that G is a strongly regular graph with p vertices where p is prime, G is a conference graph (Godsil and Royle 2001, p. 222).

The following table summarizes some conference graphs.

ngraph(n,k,a,c)characteristic polynomial
55-cycle graph(5,2,0,1)(x-2)(x^2+x-1)^2
9(2,1)-generalized quadrangle(9,4,1,2)(x-4)(x-1)^4(x+2)^4
1313-Paley(13,6,2,3)(x-6)(x^2+x-3)^6
1717-Paley(17,8,3,4)(x-8)(x^2+x-4)^8
2525-Paley(25,12,5,6)(x-12)(x-2)^(12)(x+3)^(12)
2525-Paley(25,12,5,6)(x-12)(x-2)^(12)(x+3)^(12)
2525-Paulus graph 1-14(25,12,5,6)(x-12)(x-2)^(12)(x+3)^(12)
2929-Paley(29,14,6,7)(x-14)(x^2+x-7)^(14)
3737-Paley(37,18,8,9)(x-18)(x^2+x-9)^(18)
4141-Paley(41,20,9,10)(x-20)(x^2+x-10)^(20)
4949-Paley(49,24,11,12)(x-24)(x-3)^(24)(x+4)^(24)
5353-Paley(53,26,12,13)(x-26)(x^2+x-13)^(26)
6161-Paley(61,30,14,15)(x-30)(x^2+x-15)^(30)
7373-Paley(73,36,17,18)(x-36)(x^2+x-18)^(36)
8181-Paley(81,40,19,20)(x-40)(x-4)^(40)(x+5)^(40)
8989-Paley(89,44,21,22)(x-44)(x^2+x-22)^(44)
9797-Paley(97,48,23,24)(x-48)(x^2+x-24)^(48)
101101-Paley(101,50,24,25)(x-50)(x^2+x-25)^(50)
109109-Paley(109,54,26,27)(x-54)(x^2+x-27)^(54)
113113-Paley(113,56,27,28)(x-56)(x^2+x-28)^(56)
121121-Paley(121,60,29,30)(x-60)(x-5)^(60)(x+6)^(60)
125125-Paley(125,62,30,31)(x-62)(x^2+x-31)^(62)
137137-Paley(137,68,33,34)(x-68)(x^2+x-34)^(68)
149149-Paley(149,74,36,37)(x+74)(x^2+x-37)^(74)
157157-Paley(157,78,38,39)(x-78)(x^2+x-39)^(78)
169169-Paley(169,84,41,42)(x-84)(x-6)^(84)(x+7)^(84)

See also

C-Matrix, Graph Eigenvalue, Graph Spectrum, Paley Graph, Paulus Graphs, Strongly Regular Graph

Explore with Wolfram|Alpha

References

Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, 1989.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, p. 222, 2001.

Referenced on Wolfram|Alpha

Conference Graph

Cite this as:

Weisstein, Eric W. "Conference Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ConferenceGraph.html