Vipul at 17:24, 29 May 2012

2012-05-29T17:24:48Z

← Older revision		Revision as of 17:24, 29 May 2012
Line 9:		Line 9:
	# For any two adjacent vertices, the number of vertices adjacent to both is <math>(v - 5)/4</math>.		# For any two adjacent vertices, the number of vertices adjacent to both is <math>(v - 5)/4</math>.
	# For any two non-adjacent vertices, the number of vertices adjacent to both is <math>(v - 1)/4</math>.		# For any two non-adjacent vertices, the number of vertices adjacent to both is <math>(v - 1)/4</math>.

	~~Note that for a conference graph on <math>v</math> vertices to exist, a necessary condition is that <math>v</math> be 1 mod 4.~~

	==Facts==		==Facts==

			* Note that for a conference graph on <math>v</math> vertices to exist, a necessary condition is that <math>v</math> be 1 mod 4. It turns out that a necessary and sufficient condition is that <math>v</math> 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.		* 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 <math>q</math> vertices whenever <math>q</math> is a prime power that is 1 mod 4. In particular, this ~~shows that there are~~ conference graphs of size 5, 9, 13, 17, 25, 29~~. The smallest number that is 1 mod 4 and for which it's not clear whether a conference graph exists is 21~~.		* [[Paley graphs are conference graphs]]: In particular, this shows that there exists a conference graph on <math>q</math> vertices whenever <math>q</math> 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.

Vipul: Created page with "{{undirected graph property}} ==Definition== A '''conference graph''' is a strongly regular graph with parameters $v, k = (v - 1)/2, \lambda = (v - 5)/4, \mu = (v -..."$

2012-05-29T17:22:19Z

Created page with "{{undirected graph property}} ==Definition== A '''conference graph''' is a strongly regular graph with parameters <math>v, k = (v - 1)/2, \lambda = (v - 5)/4, \mu = (v -..."

New page

{{undirected graph property}}

==Definition==

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

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

Note that for a conference graph on <math>v</math> vertices to exist, a necessary condition is that <math>v</math> be 1 mod 4.

==Facts==

* 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 <math>q</math> vertices whenever <math>q</math> is a prime power that is 1 mod 4. In particular, this shows that there are conference graphs of size 5, 9, 13, 17, 25, 29. The smallest number that is 1 mod 4 and for which it's not clear whether a conference graph exists is 21.

Conference graph - Revision history

Vipul at 17:24, 29 May 2012

Vipul: Created page with "{{undirected graph property}} ==Definition== A '''conference graph''' is a strongly regular graph with parameters v, k = (v - 1)/2, \lambda = (v - 5)/4, \mu = (v -..."

Vipul: Created page with "{{undirected graph property}} ==Definition== A '''conference graph''' is a strongly regular graph with parameters $v, k = (v - 1)/2, \lambda = (v - 5)/4, \mu = (v -..."$