Regular graph

Regular graph

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i.e. every vertex has the same degree or valency. A regular graph with vertices of degree k is called a kregular graph or regular graph of degree k.

Regular graphs of degree at most 2 are easy to classify: A 0-regular graph consists of disconnected vertices, a 1-regular graph consists of disconnected edges, and a 2-regular graph consists of disconnected cycles.

A 3-regular graph is known as a cubic graph.

A strongly regular graph is a regular graph where every adjacent pair of vertices has the same number "l" of neighbors in common, and every non-adjacent pair of vertices has the same number "n" of neighbors in common. The smallest graphs that are regular but not strongly regular are the cycle graph and the circulant graph on 6 vertices.

The complete graph K_m is strongly regular for any m.

A theorem by Nash-Williams says that every kregular graph on 2k + 1 vertices has a Hamiltonian cycle.

Algebraic properties

Let "A" be the adjacency matrix of the graph. Now the graph is regular if and only if egin{bmatrix}1\ vdots \1 end{bmatrix} is an eigenvector of "A". When it is an eigenvector, the eigenvalue will be the constant degree of the graph.

When the graph is regular with degree "k", the graph will be connected if and only if "k" has algebraic (and geometric) dimension one.

There is also a criterion for regular and connected graphs :a graph is connected and regular if and only if the matrix "J", with J_{ij}=1, is in the adjacency algebra of the graph (meaning it is a linear combination of powers of "A").

See also

* Strongly regular graph

References

*
*
* Citation | last=Nash-Williams | first=Crispin |authorlink = Crispin St. J. A. Nash-Williams
contribution=Valency Sequences which force graphs to have Hamiltonian Circuits
title=University of Waterloo Research Report | publisher=University of Waterloo
place=Waterloo, Ontario | year=1969


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Distance-regular graph — Graph families defined by their automorphisms distance transitive distance regular strongly regular …   Wikipedia

  • Strongly regular graph — Let G = (V,E) be a regular graph with v vertices and degree k . G is said to be strongly regular if there are also integers λ and μ such that:* Every two adjacent vertices have λ common neighbours.* Every two non adjacent vertices have μ common… …   Wikipedia

  • Random regular graph — A random d regular graph is a graph from mathcal{G} {n,d}, which denotes the probability space of all d regular graphs on vertex set [n] , where nd is even and [n] :={1,2,3,...,n 1,n}, with uniform distribution. Pairing ModelPairing Model, also… …   Wikipedia

  • Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges …   Wikipedia

  • Graph factorization — Not to be confused with Factor graph. 1 factorization of Desargues graph: each color class is a 1 factor …   Wikipedia

  • Graph operations — Operations on graphs produce new graphs from old ones. They may be separated into the following major categories. Contents 1 Unary operations 1.1 Elementary operations 1.2 Advanced operations 2 …   Wikipedia

  • Regular — The term regular can mean normal or obeying rules. Regular may refer to:In organizations: * Regular Army for usage in the U.S. Army * Regular clergy, members of a religious order subject to a rule of life * Regular Force for usage in the Canadian …   Wikipedia

  • Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia

  • Graph paper — Regular graphing paper (upper); Logarithmic graphing paper (lower). Graph paper, graphing paper, grid paper or millimeter paper is writing paper that is printed with fine lines making up a …   Wikipedia

  • Regulär — hat in verschiedenen Bereichen der Mathematik verschiedene Bedeutungen: In der abstrakten Algebra heißt ein Element einer algebraischen Struktur mit einer zweistelligen Operation regulär, wenn es kürzbar ist. Eine Halbgruppe heißt regulär, wenn… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”