Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Regular graph
Summary
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 directed graph must also satisfy the stronger condition that the indegree and outdegree of each internal vertex are equal to each other. A regular graph with vertices of degree k is called a k‐regular graph or regular graph of degree k. Also, from the handshaking lemma, a regular graph contains an even number of vertices with odd degree.
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 a disjoint union of cycles and infinite chains.
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 k‐regular graph on 2k + 1 vertices has a Hamiltonian cycle.
Image:0-regular_graph.svg|0-regular graph
Image:1-regular_graph.svg|1-regular graph
Image:2-regular_graph.svg|2-regular graph
Image:3-regular_graph.svg|3-regular graph
It is well known that the necessary and sufficient conditions for a regular graph of order to exist are that and that is even.
Proof: As we know a complete graph has every pair of distinct vertices connected to each other by a unique edge. So edges are maximum in complete graph and number of edges are and degree here is . So . This is the minimum for a particular . Also note that if any regular graph has order then number of edges are so has to be even.
In such case it is easy to construct regular graphs by considering appropriate parameters for circulant graphs.
Let A be the adjacency matrix of a graph.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.