# Regular graph

From Encyclopedia of Mathematics

2010 Mathematics Subject Classification: *Primary:* 05C99 [MSN][ZBL]

An unoriented graph in which each vertex has the same degree. If the common degree is $k$, the graph may be termed *$k$-regular*.

A **strongly regular graph** is a regular graph in which any two adjacent vertices have the same number of neighbours in common, and any two non-adjacent vertices have the same number of neighbours in common. The complement of a strongly regular graph is again strongly regular.

A **distance regular graph** is one with the property that for any two vertices $x,y$ the number of vertices at distance $i$ from $x$ and $j$ from $y$ depends only on $i$, $j$ and the distance $d(x,y)$.

#### References

- Richard A Brualdi, Herbert J. Ryser, "Combinatorial matrix theory", Cambridge University Press (2014) ISBN 978-0-521-32265-2 Zbl 0746.05002 Zbl 1286.05001
- Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier, "Distance-regular graphs" Springer (1989) ISBN 3-642-74343-6 Zbl 0747.05073

**How to Cite This Entry:**

Regular graph.

*Encyclopedia of Mathematics.*URL: http://encyclopediaofmath.org/index.php?title=Regular_graph&oldid=51410