In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, the Biggs–Smith graph is a 3-
regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegr ...
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 graph
In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices and , the number of vertices at distance from and at distance from depends only upon , , and the distance between and .
...
s are known. The Biggs–Smith graph is one of the 13 such graphs.
Algebraic properties
The automorphism group of the Biggs–Smith graph is a group of order 2448 isomorphic to the
projective special linear group
In mathematics, especially in the group theoretic area of algebra, the projective linear group (also known as the projective general linear group or PGL) is the induced action of the general linear group of a vector space ''V'' on the associat ...
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
In the mathematical field of graph theory, a graph is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices and of , there is an automorphism
:f : V(G) \rightarrow V(G)
such that
:f(u_1) = u_2 and f(v_1) = v_2.
In oth ...
. 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
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
.
[E. R. van Dam and W. H. Haemers, Spectral Characterizations of Some Distance-Regular Graphs. J. Algebraic Combin. 15, pages 189–202, 2003]
The
characteristic polynomial of the Biggs–Smith graph is :
.
Gallery
Image:Biggs-Smith graph 3COL.svg, The chromatic number
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...
of the Biggs–Smith graph is 3.
Image:Biggs-Smith graph 3color edge.svg, The chromatic index
In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blu ...
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.
References
*On trivalent graphs, NL Biggs, DH Smith - Bulletin of the London Mathematical Society, 3 (1971) 155-158.
{{DEFAULTSORT:Biggs-Smith graph
Individual graphs
Regular graphs