Regular graph - Revision history

Vipul: /* Definition */

2012-05-28T03:13:14Z

Definition

← Older revision		Revision as of 03:13, 28 May 2012
Line 5:		Line 5:
	===For finite degrees===		===For finite degrees===

	Suppose <math>d</math> is a nonnegative integer. An [[undirected graph]] is termed <math>d</math>-'''regular''' or '''degree-regular''' if the [[degree of a vertex\|degrees]] of all vertices of the graph are equal to <math>d</math>. Note that <math>d</math> must be strictly less than the total number of vertices in the graph.		Suppose <math>d</math> is a nonnegative integer. An [[undirected graph]] is termed <math>d</math>-'''regular''' or '''degree-regular''' if it satisfies the following equivalent definitions:

			# The [[degree of a vertex\|degrees]] of all vertices of the graph are equal to <math>d</math>. Note that <math>d</math> must be strictly less than the total number of vertices in the graph.
			# The [[adjacency matrix]] of the graph is <math>d</math> times a [[doubly stochastic matrix]].

	Note that if the graph is a [[finite graph]], then we need only concern ourselves with the definition above for finite degrees.		Note that if the graph is a [[finite graph]], then we need only concern ourselves with the definition above for finite degrees.

Vipul at 02:23, 28 May 2012

2012-05-28T02:23:53Z

← Older revision		Revision as of 02:23, 28 May 2012
Line 6:		Line 6:

	Suppose <math>d</math> is a nonnegative integer. An [[undirected graph]] is termed <math>d</math>-'''regular''' or '''degree-regular''' if the [[degree of a vertex\|degrees]] of all vertices of the graph are equal to <math>d</math>. Note that <math>d</math> must be strictly less than the total number of vertices in the graph.		Suppose <math>d</math> is a nonnegative integer. An [[undirected graph]] is termed <math>d</math>-'''regular''' or '''degree-regular''' if the [[degree of a vertex\|degrees]] of all vertices of the graph are equal to <math>d</math>. Note that <math>d</math> must be strictly less than the total number of vertices in the graph.

			Note that if the graph is a [[finite graph]], then we need only concern ourselves with the definition above for finite degrees.

	===For arbitrary degrees===		===For arbitrary degrees===

Vipul at 19:45, 27 May 2012

2012-05-27T19:45:35Z

@@ Line 3: / Line 3: @@
 ==Definition==
-An [[undirected graph]] is termed '''regular''' or '''degree-regular''' if the [[degree of a vertex|degrees]] of all vertices of the graph are equal. Here, the degree of a vertex refers to the number of vertices adjacent to it.
+===For finite degrees===
-More specifically, if the value of degree is <math>d</math>, we say that the graph is <math>d</math>-regular.
+Suppose <math>d</math> is a nonnegative integer. An [[undirected graph]] is termed <math>d</math>-'''regular''' or '''degree-regular''' if the [[degree of a vertex|degrees]] of all vertices of the graph are equal to <math>d</math>. Note that <math>d</math> must be strictly less than the total number of vertices in the graph.
-Note that <math>d</math> must be strictly less than the total number of vertices in the graph.
+===For arbitrary degrees===
 ==Particular cases==
@@ Line 29: / Line 33: @@
 |-
 | finite number <math>n</math> || <math>n - 2</math> || [[complement of a graph|complement]] of a [[matching graph]] || 1
 |}

Vipul at 19:36, 27 May 2012

2012-05-27T19:36:11Z

← Older revision		Revision as of 19:36, 27 May 2012
Line 27:		Line 27:
	\|-		\|-
	\| finite number <math>n</math> \|\| <math>n - 1</math> \|\| [[complete graph]] (i.e., clique) on <math>n</math> vertices) \|\| 1		\| finite number <math>n</math> \|\| <math>n - 1</math> \|\| [[complete graph]] (i.e., clique) on <math>n</math> vertices) \|\| 1
			\|-
			\| finite number <math>n</math> \|\| <math>n - 2</math> \|\| [[complement of a graph\|complement]] of a [[matching graph]] \|\| 1
	\|}		\|}

Vipul at 19:35, 27 May 2012

2012-05-27T19:35:20Z

← Older revision		Revision as of 19:35, 27 May 2012
Line 26:		Line 26:
	\| infinite \|\| 2 \|\| union of pairwise disjoint cyclic graphs and chains extending infinitely in both directions \|\| infinite		\| infinite \|\| 2 \|\| union of pairwise disjoint cyclic graphs and chains extending infinitely in both directions \|\| infinite
	\|-		\|-
	\| finite number <math>n</math> \|\| <math>n - 1</math> \|\| [[complete graph]] (i.e., clique) on <math>n</math> vertices)		\| finite number <math>n</math> \|\| <math>n - 1</math> \|\| [[complete graph]] (i.e., clique) on <math>n</math> vertices) \|\| 1
	\|}		\|}

Vipul: Created page with "{{undirected graph property}} ==Definition== An undirected graph is termed '''regular''' or '''degree-regular''' if the degrees of all vertices of..."

2012-05-27T19:34:44Z

Created page with "{{undirected graph property}} ==Definition== An undirected graph is termed '''regular''' or '''degree-regular''' if the degrees of all vertices of..."

New page

{{undirected graph property}}

==Definition==

An [[undirected graph]] is termed '''regular''' or '''degree-regular''' if the [[degree of a vertex|degrees]] of all vertices of the graph are equal. Here, the degree of a vertex refers to the number of vertices adjacent to it.

More specifically, if the value of degree is <math>d</math>, we say that the graph is <math>d</math>-regular.

Note that <math>d</math> must be strictly less than the total number of vertices in the graph.

==Particular cases==

{| class="sortable" border="1"
! Condition on number of vertices !! Condition on degree !! What can we say about the graph? !! Number of isomorphism classes possible after fixing number of vertices and degree
|-
| any || 0 || [[empty graph]] (graph with no edges) || 1
|-
| 2 || 1 || [[2-clique]] (two vertices with an edge joining them) || 1
|-
| even or infinite|| 1 || [[matching graph]]: a disjoint union of 2-cliques || 1
|-
| odd finite || 1 || no possibility || 0
|-
| finite number <math>n</math> || 2 || union of pairwise disjoint cyclic graphs with cycle lengths of size at least three || number of unordered integer partitions where all parts are at least 3
|-
| infinite || 2 || union of pairwise disjoint cyclic graphs and chains extending infinitely in both directions || infinite
|-
| finite number <math>n</math> || <math>n - 1</math> || [[complete graph]] (i.e., clique) on <math>n</math> vertices)
|}