|
1
|
- 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.
|
|
2
|
- 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.
|
|
3
|
- 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.
|
|
4
|
- 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.
|
|
5
|
- Conjecture. If there are at most
two vertices of degree 1 in a graph G, then the graph is traceable
- Counter-example
|
|
6
|
- 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.
|
|
7
|
- 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.
|
Notes
