Cycle graph - Revision history

Vipul at 03:46, 28 May 2012

2012-05-28T03:46:13Z

← Older revision		Revision as of 03:46, 28 May 2012
Line 5:		Line 5:
	===For a finite graph with three or more vertices===		===For a finite graph with three or more vertices===

	An [[undirected graph]] with three or more (but finitely many) vertices is termed a '''~~cyclic~~ graph''' if it satisfies the following equivalent conditions:		An [[undirected graph]] with three or more (but finitely many) vertices is termed a '''cycle graph''' if it satisfies the following equivalent conditions:

	# It is a [[connected graph]] as well as a 2-[[defining ingredient::regular graph]], i.e., every vertex has degree two.		# It is a [[connected graph]] as well as a 2-[[defining ingredient::regular graph]], i.e., every vertex has degree two.
Line 11:		Line 11:
	# A slightly slicker version of (2): it is the [[Cayley graph]] of a [[groupprops:finite cyclic group\|finite cyclic group]] of order three or more where the generating set is chosen as a cyclic generator and its inverse.		# A slightly slicker version of (2): it is the [[Cayley graph]] of a [[groupprops:finite cyclic group\|finite cyclic group]] of order three or more where the generating set is chosen as a cyclic generator and its inverse.

	Note that, up to [[graph isomorphism]], there is a unique ~~cyclic~~ graph for every size of vertex set.		Note that, up to [[graph isomorphism]], there is a unique cycle graph for every size of vertex set.

	===For the case of two or fewer vertices===		===For the case of two or fewer vertices===

	For two vertices, if we allow undirected graphs and do not allow parallel edges, the correct analogue to ~~cyclic~~ graph is the [[2-clique]]. If we allow parallel edges, the correct analogue is a graph with two vertices and two edges between them.		For two vertices, if we allow undirected graphs and do not allow parallel edges, the correct analogue to cycle graph is the [[2-clique]]. If we allow parallel edges, the correct analogue is a graph with two vertices and two edges between them.

	For one vertex, if we allow undirected graphs and do not allow loops, the correct analogue is the only possible graph with one vertex. If we allow loops, the correct analogue is a graph with one vertex and one loop at that vertex.		For one vertex, if we allow undirected graphs and do not allow loops, the correct analogue is the only possible graph with one vertex. If we allow loops, the correct analogue is a graph with one vertex and one loop at that vertex.

Vipul: moved Cyclic graph to Cycle graph

2012-05-28T03:45:35Z

moved Cyclic graph to Cycle graph

← Older revision	Revision as of 03:45, 28 May 2012
(No difference)

Vipul: Created page with "{{undirected graph property}} ==Definition== ===For a finite graph with three or more vertices=== An undirected graph with three or more (but finitely many) vertices is..."

2012-05-28T02:21:24Z

Created page with "{{undirected graph property}} ==Definition== ===For a finite graph with three or more vertices=== An undirected graph with three or more (but finitely many) vertices is..."

New page

{{undirected graph property}}

==Definition==

===For a finite graph with three or more vertices===

An [[undirected graph]] with three or more (but finitely many) vertices is termed a '''cyclic graph''' if it satisfies the following equivalent conditions:

# It is a [[connected graph]] as well as a 2-[[defining ingredient::regular graph]], i.e., every vertex has degree two.
# We can arrange a bijection between the vertex set and the [[groupprops:group of integers modulo n|group of integers modulo n]] (where <math>n</math> is the number of vertices) such that there is an edge between two vertices if and only if the corresponding group elements differ by 1 modulo <math>n</math>.
# A slightly slicker version of (2): it is the [[Cayley graph]] of a [[groupprops:finite cyclic group|finite cyclic group]] of order three or more where the generating set is chosen as a cyclic generator and its inverse.

Note that, up to [[graph isomorphism]], there is a unique cyclic graph for every size of vertex set.

===For the case of two or fewer vertices===

For two vertices, if we allow undirected graphs and do not allow parallel edges, the correct analogue to cyclic graph is the [[2-clique]]. If we allow parallel edges, the correct analogue is a graph with two vertices and two edges between them.

For one vertex, if we allow undirected graphs and do not allow loops, the correct analogue is the only possible graph with one vertex. If we allow loops, the correct analogue is a graph with one vertex and one loop at that vertex.