Difference between revisions of "Regular graph"
From Encyclopedia of Mathematics
(Start article: Regular graph) |
m (→References: isbn) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
{{TEX|done}}{{MSC|05C99}} | {{TEX|done}}{{MSC|05C99}} | ||
| − | An unoriented [[graph]] in which each vertex has the same degree. | + | 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 [[Graph complement|complement]] of a strongly regular graph is again strongly 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 [[Graph complement|complement]] of a strongly regular graph is again strongly regular. | ||
| Line 8: | Line 8: | ||
====References==== | ====References==== | ||
| − | * Richard A Brualdi, Herbert J. Ryser, "Combinatorial matrix theory", Cambridge University Press (2014) ISBN 978-0-521-32265-2 | + | * 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}} | + | * Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier, "Distance-regular graphs" Springer (1989) {{ISBN|3-642-74343-6}} {{ZBL|0747.05073}} |
Latest revision as of 14:17, 12 November 2023
2020 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=51396
Regular graph. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Regular_graph&oldid=51396