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
Biggs–Smith graph
Summary
In the mathematical field of graph theory, the Biggs–Smith graph is a 3-regular graph with 102 vertices and 153 edges.
It has chromatic number 3, chromatic index 3, radius 7, diameter 7 and girth 9. It is also a 3-vertex-connected graph and a 3-edge-connected graph.
All the cubic distance-regular graphs are known. The Biggs–Smith graph is one of the 13 such graphs.
The automorphism group of the Biggs–Smith graph is a group of order 2448 isomorphic to the projective special linear group PSL(2,17). It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore, the Biggs–Smith graph is a symmetric graph. It has automorphisms that take any vertex to any other vertex and any edge to any other edge. According to the Foster census, the Biggs–Smith graph, referenced as F102A, is the only cubic symmetric graph on 102 vertices.
The Biggs–Smith graph is also uniquely determined by its graph spectrum, the set of graph eigenvalues of its adjacency matrix.
The characteristic polynomial of the Biggs–Smith graph is :
Image:Biggs-Smith graph 3COL.svg|The [[chromatic number]] of the Biggs–Smith graph is 3.
Image:Biggs-Smith graph 3color edge.svg|The [[chromatic index]] of the Biggs–Smith graph is 3.
Image:BiggsSmith.svg|Alternative drawing of the Biggs–Smith graph.
Image:Biggs-Smith graph - circle-based drawing.jpg|Decomposition of the Biggs–Smith graph into 6 sets of size 17.
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.