Regular graph - Citizendia

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i. In Mathematics and Computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects In Mathematics and Computer science, a graph is the basic object of study in Graph theory. e. every vertex has the same degree or valency. In Graph theory, the degree (or valency) of a vertex of a graph is the number of edges incident to the vertex A regular graph with vertices of degree $k$ is called a $k$ ‑regular 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. Cycle in Graph theory and Computer science has several meanings A closed walk with repeated vertices allowed

A 3-regular graph is known as a cubic graph. In the mathematical field of Graph theory, a cubic graph is a graph where all vertices are incident to exactly three edges

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. Let G = (VE be a Regular graph with v vertices and degree k. G is said to be strongly regular if there are also Integers The smallest graphs that are regular but not strongly regular are the cycle graph and the circulant graph on 6 vertices. In Graph theory, a cycle graph is a graph that consists of a single cycle, or in other words some number of vertices connected in a closed chain In Linear algebra, a circulant matrix is a special kind of Toeplitz matrix where each Row vector is rotated one element to the right relative to the preceding

The complete graph $K m$ is strongly regular for any $m$ . In the mathematical field of Graph theory, a complete graph is a Simple graph in which every pair of distinct vertices is connected by an

A theorem by Nash-Williams says that every $k$ ‑regular graph on $2 k + 1$ vertices has a Hamiltonian cycle. Crispin St John Alvah Nash-Williams ( December 19, 1932 — January 20, 2001) was a British and Canadian mathematician In the mathematical field of Graph theory, a Hamiltonian path is a path in an Undirected graph which visits each vertex exactly once

0-regular graph

1-regular graph

2-regular graph

3-regular graph

Algebraic properties

Let A be the adjacency matrix of the graph. In Mathematics and Computer science, the adjacency matrix of a finite directed or undirected graph G on n vertices is the Now the graph is regular if and only if $\begin{bmatrix}1\\ \vdots \\1 \end{bmatrix}$ is an eigenvector of A. ↔ In Mathematics, given a Linear transformation, an of that linear transformation is a nonzero vector which when that transformation is applied to it changes 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 i j = 1$ , is in the adjacency algebra of the graph (meaning it is a linear combination of powers of A).

References

Eric W. Weisstein, Regular Graph at MathWorld. Let G = (VE be a Regular graph with v vertices and degree k. G is said to be strongly regular if there are also Integers Eric W Weisstein (born March 18, 1969, in Bloomington Indiana) is an Encyclopedist who created and maintains MathWorld MathWorld is an online Mathematics reference work created and largely written by Eric W
Eric W. Weisstein, Strongly Regular Graph at MathWorld. Eric W Weisstein (born March 18, 1969, in Bloomington Indiana) is an Encyclopedist who created and maintains MathWorld MathWorld is an online Mathematics reference work created and largely written by Eric W
Nash-Williams, Crispin (1969), “Valency Sequences which force graphs to have Hamiltonian Circuits”, University of Waterloo Research Report, Waterloo, Ontario: University of Waterloo

Crispin St John Alvah Nash-Williams ( December 19, 1932 — January 20, 2001) was a British and Canadian mathematician

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Algebraic properties

See also

References