Over the summer break, John and I each supervised a 2nd year undergraduate student in a research project, and the previous post summarised Michael Martis’ project. I supervised Melissa Lee, who learned about the energy of graphs and this is what she did
Hello everyone! My name is Melissa Lee and I’m about to start my third year of Chemical Engineering and Pure Mathematics at UWA. Over these summer holidays, I’ve been given the opportunity to take on a six week research project with Professor Gordon Royle. The area that I have researched is the energy of graphs, with a particular focus on extremal cases. It’s been a new and exciting time for me, being my first experience of research and also my first taste of graph theory.
The idea of the energy of a graph was first introduced by Serbian mathematician Ivan Gutman at a conference in Austria in 1978. Its origins lie in chemistry, where it is defined as “the total electron energy of a conjugated hydrocarbon as calculated with the Hückel Molecular Orbital method”. The concept didn’t receive much attention from mathematicians for many years. However, sometime around the turn of the century, mathematicians realised its value and since then, increasing numbers of papers have been published each year about the energy of graphs.
Suppose is a simple graph with vertices and an adjacency matrix . Then suppose are the eigenvalues of . The energy of a graph is then defined as
For example, since the spectrum of a complete graph of order is
it follows that the energy of a complete graph is
The energy of a star graph is calculated to be , since its only non-zero eigenvalues are and . After a great deal of reading and frustrating dead ends, I’ve been able to prove that the star graph on vertices actually has the least energy of all connected graphs of order .
However, finding a general structure of the highest energy graph on vertices wasn’t as clear cut.
It was originally conjectured by Gutman that the complete graph was the highest energy graph of order ; this was soon disproved by Chris Godsil and others. Graphs that have energies that exceed that of the complete graph on the same number of vertices are said to be hyperenergetic.
I found that there is a notable upper bound on the energy of graphs discovered by Jack Koolen and Vincent Moulton. For a graph with order ,
This bound is sharp if and only if is a strongly regular graph with parameters
Willem Haemers et al. have shown that all strongly regular graphs with these parameters exist. This means that the highest energy graphs on vertices, where is an even square, are known.
This is where the computation part of my project came in. Gordon suggested that I use the Sage package to generate and calculate the energy of graphs. This worked quite well for graphs up to order eight, and I was also able to plot energy against edges for all graphs of a particular order quite efficiently. However, we soon found that Sage was very slow in calculating energies when it came to processing relatively large quantities of graphs and was retaining information about every graph it processed which, of course, led to memory problems.
So instead of working directly through Sage, I used Brendan McKay’s nauty package to generate graph6 strings of each graph, which turned out to be much quicker than using Sage. I also wrote some programs to split the data and process it in batches of 100,000 graphs to stop the process consuming too much memory and becoming extraordinarily slow. Using Gordon’s computer, I was able to run several of these processes in parallel and could find around 500,000 graph energies per hour. I then graphed all of this data by writing a C program to interface with nauty and GNUplot.
I found there were no hyperenergetic graphs on fewer than eight vertices. On eight vertices, there are 23 hyperenergetic graphs which accounts for approximately 0.186% of the total number of graphs of order eight. Similarly, there are 2542 graphs of order nine and 454127 graphs of order ten which are hyperenergetic, and these account for around 0.925% and 3.78% of total graphs respectively. Although it may seem surprising from these results, the majority of graphs are hyperenergetic.
I couldn’t find a pattern between the highest energy graphs of order eight, nine and ten. It became impractical to investigate graphs larger than ten vertices because of the sheer number of graphs involved.
Undeterred, decided to focus my efforts on specific families of graphs. I researched some connected regular graphs and found their extremal energy cases, using similar techniques to those mentioned above. Conveniently, nauty allows the user to specify restraints on the graphs the program produces and so I didn’t need to sort through the graphs myself to find those that I needed.
From my investigation, I have made a couple of conjectures about the least energy cubic and quartic connected graphs. Firstly, for cubic (i.e. 3-regular) graphs, I conjecture that the lowest energy cubic graph on vertices for is composed of elements similar to modules and modules. A single edge is removed from the modules and the vertices adjacent to the removed edge are used to add edges to connect the components of the graph. Since the vertices of the modules have degree two, each of their vertices has an additional edge added between it and a vertex of another module to connect the graph. For example, the least energy graph of order 16 is composed of two modules and a module in between them.
The lowest energy cubic graph on sixteen vertices
I have also made two conjectures about the lowest energy quartic (4-regular) graphs. I conjecture that the lowest energy connected quartic graph on an even number of vertices is the lexicographical product of an -cycle and two isolated vertices . This conjecture is supported by all of the lowest energy graphs on an even number of vertices , .
I also conjecture that the lowest energy graph on an odd number of vertices is obtained by taking two smaller least energy quartic graphs, removing an edge from each of them and then connecting the two components with a pair of edges. The least energy graph on 13 vertices is a good example of this. It is composed of and the lowest energy graph on 8 vertices, with the modifications described above.
The lowest energy quartic graph on thirteen vertices
There is still a great deal that is unknown about extremal energy graphs. Although various upper bounds have been found for graph energy, such as the one by Koolen and Moulton mentioned above, no general form of the highest energy graph on vertices has been found and it remains an open problem.
Overall, this project has been extremely rewarding and enlightening for me. I have been introduced to the extraordinarily interesting world of graph theory and have developed a plethora of useful skills. I’ve come to the realisation that research is something I enjoy immensely and I plan on incorporating more of it into my studies as soon as I can. I am so grateful to Gordon and John for giving me this opportunity and I highly recommend this experience to any mathematics student who loves a challenge and wants to learn about some awesome areas of mathematics.