Misplaced Pages

Robertson–Wegner graph

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
5-regular undirected graph with 30 vertices and 75 edges
Robertson–Wegner graph
Named afterNeil Robertson
Vertices30
Edges75
Radius3
Diameter3
Girth5
Automorphisms20
Chromatic number4
Chromatic index5
PropertiesCage
Table of graphs and parameters

In the mathematical field of graph theory, the Robertson–Wegner graph is a 5-regular undirected graph with 30 vertices and 75 edges named after Neil Robertson and Gerd Wegner.

It is one of the four (5,5)-cage graphs, the others being the Foster cage, the Meringer graph, and the Wong graph.

It has chromatic number 4, diameter 3, and is 5-vertex-connected.

Algebraic properties

The characteristic polynomial of the Robertson–Wegner graph is

( x − 5 ) ( x − 2 ) 8 ( x + 1 ) ( x + 3 ) 4 ( x 4 + 2 x 3 − 4 x 2 − 5 x + 5 ) 2 ( x 4 + 2 x 3 − 6 x 2 − 7 x + 11 ) 2 . {\displaystyle (x-5)(x-2)^{8}(x+1)(x+3)^{4}(x^{4}+2x^{3}-4x^{2}-5x+5)^{2}(x^{4}+2x^{3}-6x^{2}-7x+11)^{2}.}

References

  1. Weisstein, Eric W. "Class 2 Graph". MathWorld.
  2. Weisstein, Eric W. "Robertson–Wegner Graph". MathWorld.
  3. Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 238, 1976.
  4. Wong, P. K. "A note on a paper of G. Wegner", Journal of Combinatorial Theory, Series B, 22:3, June 1977, pgs 302-303, doi:10.1016/0095-8956(77)90081-8
Categories: