Traceable Graphs and the
Faculty Mentor: Dr. E. DeLaVina
The purpose of this undergraduate research project in graph theory was to resolve conjectures generated by Graffiti.pc about graphs that are traceable.
Part-time project that began in the spring.
A graph is said to be traceable (or has a Hamiltonian Path) if the all of the vertices of the graph can be visited exactly once.
The degree of a vertex is the number of edges incident to the vertex. The minimum of the degrees of the vertices is called the minimum degree of the graph.
G. A. Diracís Theorem
Theorem (Dirac 1952). Let n be the number of vertices of the graph. If the minimum degree of a graph is greater than or equal to (n-1)/2, then the graph is traceable.
If there are at most two vertices of degree 1 in a graph G, then the graph is traceable
Another Form of Conjectures
Graffiti.pc was also asked to make necessary conditions for traceable graphs.
Conjecture. If the graph G is traceable, then the minimum degree of G is at least half of k, where k is the number of vertices of minimum degree.
"We resolved 29 conjectures of..."
We resolved 29 conjectures of which 2 were true.
An example of a conjecture that was proven:
Theorem. If G is a traceable graph, then number of vertices of degree 1 is at most twice the minimum degree.
Future project direction: Narrow the topic a little bit, by asking the program, Graffiti.pc to focus on bipartite graphs that are traceable.