Supporting Software for Mathematics Publication

In discrete mathematics, graphs are networks of connected nodes. These graphs can be used to model a large variety of real world systems by applying attributes to the nodes and edges. These attributes could be in the form of labels, directions and weights.

A challenge in network theory is to apply the notion of curvature from surfaces to discrete structures such as graphs and networks. There are different variants of this curvature property depending on whether it is defined for the edges or nodes. Bakry-Émery curvature describes curvatures on the set of nodes, which are loosely related to the local connectivity of the network. This allows for the classification of networks by properties of their curvatures, for example non-negative and/or infinity curvature sharp.

The aim of this project was to classify all curvature sharp quartic (four-regular) networks. Quartic networks have four edges connected to each node. This research builds upon the research conducted by D. Cushing et. al. in which all cubic (three-regular) graphs with non-negative curvatures were classified. [1]

My role was to help develop software in Python to generate the full classification of local configurations with curvature sharp centres. [2] This was achieved in four stages:

  1. All possible radius two configurations of a quartic graph were generated recursively;
  2. The curvature of each graph was calculated using The Graph Curvature Calculator by G. Stagg and D. Cushing to remove graphs with negative curvature; [3]
  3. All isomorphisms (structurally equivalent graphs) were found and removed;
  4. The curvature sharpness condition was checked for the centres of each of the remaining graphs to provide the final result.

This result was crucial to derive a complete classification of the eight infinity curvature sharp graphs (pictured below). This formed the main theorem of the paper entitled Quartic Graphs that are Bakry-Émery Curvature Sharp which was published in Discrete Mathematics 343(3). [4]

The eight infinity curvature sharp graphs:
The complete graph K_5
The complete graph K5
The octahedral graph O
The octahedral graph
The Cartesian product K_3 x K_3
The cartesian product K3 × K3
The complete bipartite graph K_(4,4)
The complete bipartite graph K4,4
The crown graph C(10)
The crown graph C(10)
The Cayley graph Cay(D_12,S) of the dihedral group D_12 of order 12 with generators S = {r^3,s,sr^2,sr^4}
The Cayley graph Cay(D12,S) of order 12 with generators S = {r3,s,sr2,sr4}
The Cayley graph Cay(D_14,S) of the dihedral group D_14 of order 14 with generators S = {s,sr,sr^4,sr^6}
The Cayley graph Cay(D14,S) of order 14 with generators S = {s,sr,sr4,sr6}
The 4-dimensional hypercube Q^4
The 4-dimensional hypercube Q4
References

[1] Cushing, D., Kangaslampi, R., Lipiäinen, V., Liu, S. and Stagg, G., 2019. The Graph Curvature Calculator and the Curvatures of Cubic Graphs. Experimental Mathematics, [online] Available at: <https://doi.org/10.1080/10586458.2019.1660740>
[2] Gurr, F. and Watson May, L., 2019. Bakry-Émery Curvature Calculations Of Quartic 2-Balls And Graphs Of Diameter 2. [online] Available at: <https://arxiv.org/src/1902.10665v1/anc>.
[3] Cushing, D. and Stagg, G., 2017. The Graph Curvature Calculator. [online] Available at: <http://www.mas.ncl.ac.uk/graph-curvature/>.
[4] Cushing, D., Kamtue, S., Peyerimhoff, N. and Watson May, L., 2020. Quartic graphs which are Bakry-Émery curvature sharp. Discrete Mathematics, [online] 343(3), p.111767. [online] Available at: <https://doi.org/10.1016/j.disc.2019.111767>