This is part of my Fall 2017 Undergraduate Research project, attempting to progress towards proving or disproving the Graph Reconstruction Conjecture.

This was my first experience programming for a specific purpose, not for an assignment, and my first experience coding to generate data for others to use.

This project was supervised by Dr. Ken W. Smith. Roughly 20 students participated in this research, working as a full group once a week and working more closely in smaller groups of 3-5 meeting once a week. However, most of the students were Mathematics students, and I was the most experienced Computer Science student and programmer.

Each small group was assigned a couple of cubic graphs to manually generate the Kocay graphs and decks from. Not wanting to do that, I wrote a program to do it for me. I used that program to go ahead and generate all of the cards. After that, Dr. Smith would ask me for specific data sets, which I would write programs for and get to him. All of the data generated was checked against the manual data that the other students generated.

This is not a complete report of the entire projects findings, just a report of my own work on it.

All code was written in SageMath, which is essentially a math extension and environment of Python 2. My code would be stored in files, and to run it I would open a new workbook, use the command load() to load that file into the current workbook, and then use the desired functions. The University had a SageMath server, however I did all my work on a virtual machine on my home computer.

Final Report.pdf is a complete walkthrough of all of my group's work over the semester, and includes brief explanations of the subject matter.

The GRC is an unproven conjecture in Graph Theory about simple graphs. For a simple graph, a card is a graph generated by taking the original graph and removing one specific vertex and all edges that connect to that vertex. The deck of a graph is the set of all its cards, that is, the set of cards where each card was generated by deleting a different vertex from the original graph. The GRC states simply that a graph can be reconstructed using only its deck, with no knowledge of the original graph (including no knowledge of the original vertex labels). While this is certainly true of some simple graphs (for example, any graph with a bridge, a single edge connecting two different sections of a graph, is very easy to reconstruct), it has yet to be proven or disproven for all simple graphs. However, it is generally thought to be true.

During this project we mostly worked with Kocay Graphs, which are generated by taking a graph of degree n (meaning each vertex is connected to n other vertices) and removing one edge from it. If k is the number of vertices, a Kocay graph has k-2 vertices of degree n, and 2 vertices of degree n, and 2 vertices of degree n-1. Kocay graphs are known to be relatively hard to reconstruct.

Specifically, this project was interested in Kocay graphs generated from cubic graphs on 10 vertices. A list of these 19 cubic graphs on 10 vertices can be found in Graph-Reconstruction-Research/Data/Cubic graphs with 10 vertices.pdf

While we did not expect to find a counterexample in these graphs because the GRC has been proven for graphs on 0 - 11 vertices, we were looking for specific types of graphs and observations that when expanded to larger graphs might contain a counterexample.

The easiest way to disprove the Graph Reconstruction Conjecture would be to find two seperate graphs that produce the same deck. We looked at these possibilities by examining Kocay graphs which shared a subset of their deck, and examining partial automorphisms among the Kocay graphs. A partial automorphism, simply put, is the graph version of a partial function. In short, it doesn't directly map from x to y, but it almost does. Partial automorphisms and why they were important to this project are explained in Graph-Reconstruction-Research/Data/2_PartialAutomorphisms.pdf

Isomorphism is a concept used heavily in this research. Two graphs are isomorphic if they are essentially the same. That is, they have the same structure, while labels and representation can be different. If you can use a function to directly map from one graph to the other, the two are isomorphic.

For those interested in the subject matter, the folder Further Reading contains Kocay's original paper on the subject, which sets the grounds for all of our work, an explanation of Partial Automorphisms by Dr. Smith, and an explanation of the method we used to generate interesting graphs towards the end of the project.

All of the following data was generated by my code, which will be explained later. Most of the PDFs are just copies of the ouput of the code, also showing which files and functions were used for that specific data. There are also .txt files of some of the data, and a couple of our final data sets were put into Excel and made prettier. A detailed explanation of the labeling system can be found in Final Report.pdf, but in general, the main labeling system is G for one of the original cubic graphs, H for a Kocay graph, and V for a card. The following four digit number is the original graph it came from, the two numbers after the e are numbers of the vertices connected to the deleted edge (for Kocay graphs), and the number after the underscore is the number of the vertice deleted (for cards).

Graph6 is a format for storing graphs. The graph6 stings we used are essentially the adjacency matrix of the graph stored in binary then interpereted as ASCII strings.

Cubic graphs with 10 vertices.pdf is a pdf of the wikipedia article of the same name, which is the original 19 graphs we were given to work with.

MainList.pdf is the same list of the original 19 graphs with their labels, graph6 format string, and degree sequence.

KocayList.pdf is a list of all of the Kocay graphs generated from the original 19 cubic graphs, their graph6 string, and their degree sequence.

CardList.pdf is a list of all cards generated from all of the Kocay graphs generated from the original 19 cubic graphs. (19 graphs * 15 edges to delete to make Kocay graphs * 10 vertices to delete to make cards) = 2850 total cards.

CardIsoList.pdf is a list of all the cards grouped into isomorphisms. First the graph6 string that defines that unique graph, then the different labels of cards are isomorphic to that.

KocayIsoList.pdf is a list of all the Kocay graphs grouped into isomorphisms, similar to CardIsoList.pdf

CardIsoDegreeList.pdf is the same as CardIsoList.pdf but it is sorted by degree sequence.

UniqueCardList.txt is a list assigning each unique card a simple label, in the format cXX where XX is the number of unique graph that is, in the order they were generated. There were 240 unique cards from the 2850 total cards, from c0 to c239. After the label, the graph6 string is listed, followed by the original labels of all the cards from the 2850 that belong to that isomorphism group.

UniqueKocayList.txt is the same as UniqueCardList.txt except for Kocay graphs. There were 91 unique Kocay graphs from the 285 Kocay graphs generated, h0 - h90.

AppearanceChart.txt is a chart of how many times each unnique card appeared in the deck of each unique Kocay graph. Each column sums up to 10 because each Kocay graph had a deck of 10 cards.

UniqueCardDegrees.txt is a list of the unique cards sorted by degree sequence, using the unique labels assigned in UniqueCardList.txt

SortedAppearanceChart.txt the same as AppearanceChart.txt except that it is sorted by degree sequence.

KocayCardSharing.txt is a chart of how many cards the deck of a each Kocay graph has in common with the deck of every other Kocay graph.

KocayCardSharing.xlsx is an Excel spreadsheet version of KocayCardSharing.txt, much prettier. Entries of 2 and 3 are highlighted, while there were no entries higher than 3.

KocayCardSharingList.txt is a list of exactly which Kocay graphs share which cards.

KocayGraphsThatShareNoMoreThan1CardWithAnyOtherKocayGraph.txt is fairly self explanatory.

GraphDatabaseFinal.xlsx is an Excel spreadsheet version of SortedAppearanceChart.txt, much prettier. It contains the appearance chart sorted by degree sequence, explanations of what each degree sequence means, all original labels, unique labels, and graph6 strings, and a link to an image of each graph.

All of the code was written by me in SageMath, saved in .py files. SageMath is an open source Math oriented software system based off of Python 2. All of my code was stored in files and functions. To use the code, in my current Sage workbook I would use the command load() to load one of the files into that workbook and then call whatever functions I needed.

Most of this code is just Python list operations, and lots of comparisons using SageMath's isIsomorphic() function.

All the code in the folder Array Hardcodes is simply hardcodings of several different arrays generated by these programs, so that when testing I wouldn't have to regenerate them each time. However, for all of the final data sets all of the data was completely regenerated from the original 19 graphs.

G10.0-G10.18.py is a hardcoding of the original 19 cubic graphs, used to generate all of the other data.

BD_Decks.py is code to generate all of the decks from all of the Kocay graphs from one cubic graph.

AllCards.py is code for making all of the cards, and checking for isomorphisms. It uses BD_Decks.py and G10.0-G10.18.py.

AppearanceChart.py is code for generating the appearance charts.

SortIsoList.py is code for sorting the isomorphism lists by degree sequence.

KocaySharing.py is code for generating the Kocay card sharing chart and lists of Kocay graphs that share cards.

The biggest operation in this code was checking for isomorphisms in the cards. Worst case, you had to compare 2850 cards against 2850 cards which is 8,122,500 comparisons. However, it is unneccessary to compare a card to itself, saving you 2850 comparisons. It is also unneccesary to compare cards both directions. Basically, if you compare y to x, you don't need to later compare x to y, so that saves you a great deal of comparisons. You also don't need to compare cards with cards that you know are isomorphic with cards you've already compared them to, saving many comparisons. I don't know exactly how many comparisons it took, I should record that number sometime.

D8 stuff is a folder containing basically the same things listed above except for graphs on 8 vertices instead of 10. The code in that folder is the same as the other code only modified slightly so that it would work for graphs on 8 vertices. The code in that folder was actually modified so that it would work for graphs of any size, so theoretically it could replace the original code, but this hasn't been tested so I kept them seperate anyway.