Skip to content

Vacation research scholarship II

February 18, 2013

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 \pi 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 {\Gamma} is a simple graph with {n} vertices and an {n\times n} adjacency matrix {A(\Gamma)}. Then suppose {\lambda_i, i = 1,2, \ldots, n} are the eigenvalues of {A(\Gamma)}. The energy of a graph is then defined as

\displaystyle {\mathscr{E}(\Gamma) = \sum_{i=1}^n |\lambda_i| .}

For example, since the spectrum of a complete graph of order {n} is

\displaystyle \mathrm{Spec}(K_n) = \begin{pmatrix} n-1 & -1\\ 1 & n-1 \end{pmatrix},

it follows that the energy of a complete graph is {\mathscr{E}(K_n) = 1\times(n-1) + |-1|\times(n-1) = 2n-2.}

The energy of a star graph is calculated to be {2\sqrt{n-1}}, since its only non-zero eigenvalues are {\sqrt{n-1}} and {-\sqrt{n-1}}. After a great deal of reading and frustrating dead ends, I’ve been able to prove that the star graph on {n} vertices actually has the least energy of all connected graphs of order {n}.

However, finding a general structure of the highest energy graph on {n} vertices wasn’t as clear cut.

It was originally conjectured by Gutman that the complete graph was the highest energy graph of order {n}; 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 {\Gamma} with order {n},

\displaystyle \mathscr{E}(\Gamma)\leq \frac{n}{2}(1 + \sqrt{n}).

This bound is sharp if and only if {\Gamma} is a strongly regular graph with parameters

{(n, \frac{n+\sqrt{n}}{2},\frac{n+2\sqrt{n}}{4}, \frac{n+2\sqrt{n}}{4})}.

Willem Haemers et al. have shown that all strongly regular graphs with these parameters exist. This means that the highest energy graphs on {k} vertices, where {k} 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 {n\equiv_4 2} vertices for {n\geq 14} is composed of elements similar to {K_{3,3}} modules and {K_{2,2}} modules. A single edge is removed from the {K_{3,3}} 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 {K_{2,2}} 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 {K_{3,3}} modules and a {K_{2,2}} module in between them.

L16

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 {2k} is the lexicographical product of an {n}-cycle and two isolated vertices {C_{2k}[2K_1]}. This conjecture is supported by all of the lowest energy graphs on an even number of vertices {n}, {6\leq n\leq 14}.

I also conjecture that the lowest energy graph on an odd number of vertices {n \geq 13} 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 {K_5} and the lowest energy graph on 8 vertices, with the modifications described above.

4L13

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 {n} 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.

Advertisements
15 Comments leave one →
  1. February 20, 2013 4:34 am

    Great stuff Melissa! Spectral graph theory is a beautiful area of maths. Best of luck!

    • Melissa Lee permalink
      February 20, 2013 11:20 am

      Thanks Adrian! I’ve had heaps of fun 🙂

  2. February 23, 2013 5:39 am

    You say that all the strongly regular graphs with the parameters corresponding to the highest energy on $n=4m^2$ vertices are known. Only very few s.r.g.s are actually characterised by their parameters. Indeed, according to http://www.maths.gla.ac.uk/~es/srgraphs.php, there are at least 180 nonisomorphic graphs with these parameters for $n=36$.

    • February 23, 2013 5:40 am

      Oh, I forgot that on wordpress.com $ is not doing the right job 🙂

    • Melissa Lee permalink
      February 23, 2013 3:13 pm

      I think what I meant to say is that strongly regular graphs with the parameters described exist for all valid values of n. I admit that maybe we don’t know which S.R.G with those parameters is the highest energy graph, but we do know that one of them meets the bound.

      Thanks for the feedback! 🙂

    • Gordon Royle permalink*
      February 23, 2013 3:41 pm

      Actually, what Melissa meant is that for all even squares, SRGs with those parameters exist. Of course they all have the same spectrum and so all equally meet the Koolen-Moulton bound. However, as Dima mentions we do not know ALL the SRGs with those parameters.

  3. February 25, 2013 8:52 pm

    That’s a nice project! Two remarks and a question following:

    1. It is often handy to use nauty within Sage in the following way:

    for G in graphs.nauty_geng(“”):
    # do stuff with G

    2. Maybe I am missing something but the conjecture for the lower energy of a 4-regular graphs appears to be false. The energy of the lexicographic product of C_8 and 2K_1 is approximately 19.313 while the graph on the figure below (graph6 string: O????BoyF_]?DoBo@w?]?) appears to have energy that is approximately 18.583.

    [img]http://shrani.si/f/2x/Qu/sCb4u3r/eng.png[/img]

    As for the question.. What kind of computer was used to run the compuations?

    • Gordon Royle permalink*
      March 11, 2013 2:55 pm

      I’m pretty sure that your example has the minimum energy. Of course, investigating it more closely reveals that it has lots of twin vertices – vertices with the same neighbourhood – each of which generates a zero eigenvalue. Maybe we need to add the adjective “reduced” to make the minimal energy problem more interesting!

      • March 13, 2013 11:38 pm

        Reduced in what sense?

      • March 14, 2013 12:43 am

        Jernej: a graph is called reduced is no two vertices have the same neighbourhoods.

      • Gordon Royle permalink*
        March 15, 2013 11:58 am

        Yes, as Dima says, “reduced” means “no two vertices with identical neighbourhoods”. If there ARE two vertices with identical neighbourhoods, then this adds an eigenvalue of 0 to the spectrum and so the energy does not increase though the total number of vertices and edges does.

        With reflection, this seems like an easy way to get lots of very low energy graphs (just add as many “twins” as possible while staying within the class under consideration), but it seems like this is not an interesting construction.

        So restricting to reduced graphs only would seem like a sensible choice for “minimum energy” problems.

  4. Gordon Royle permalink*
    March 4, 2013 9:50 am

    You are not missing anything; Melissa computed the energies for quartic graphs on up to 15 vertices and made her conjecture based on the examples on that number of vertices.
    Your example shows that on 16 vertices this graph no longer has minimum energy.

    I have never had luck using Sage for long computations because it seems to leak memory – perhaps there is some way of controlling this, but I don’t know it.

    The computations were done on a fairly recent machine running Red Hat Enterprise Linux.

    • March 4, 2013 1:03 pm

      there were memory leaks fixed in recent releases of Sage. There still are memory-leak-like effects when certain types of Sage data are used (e.g. unnecessary bases of vector spaces created), but it’s being worked on. Bug reports are most welcome!

  5. Alumbros permalink
    March 21, 2013 5:07 pm

    Would you mind posting the specs of the computer you used for these computations?

    • Gordon Royle permalink*
      March 22, 2013 8:37 am

      The machine has a number of Intel Xeon E5-2630 chips running at 2.3GHz, providing a total of 24 cores. It is running Red Hat Enterprise Linux Workstation release 6.4 (Santiago)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: