# Regular graph

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