School of Fundamental Science and Technology
|
Name | Kenta Ozeki |
|---|---|---|
| Department | Department of Mathematics, School of Fundamental Science and Technology | |
| Research Fields | Discrete Mathematics, Graph Theory |
Substructures of graphs which are defined by some graph invariants
A graph is defined by a vertex set and an edge set, which is a family of 2-element subsets of a vertex set. In a Graph Theory, we are studying about some properties and structures on a graph.
As one of directions of Graph Theory, the existence of particular substructures has been studied. For example, a cycle is called a Hamilton cycle if it passes through all vertices of a graph and the problem ``Determine whether a graph has a Hamilton cycle'' has been studied by many researchers, because it concerns to Traveling Salesman Problem, which is an important problem in Combinational Optimization. Like a Hamilton cycle, I'm interested in ``Conditions guaranteeing the existence of particular substructures of a graph''.
We viscerally know that the more edges a graph has, the more easily we can find substructures like a Hamilton cycle. For example, it is easily shown that if an n vertices graph has more than (n2 -3n +6)/2 edges, the graph has a Hamilton cycle. Furthermore, it is known that there exists a graph with less than it edges having no Hamilton cycle. However, in this condition, we consider only the number of edges, but not the structure of the graph, and hence many edges are necessary to find a Hamilton cycle.
On the other hand, in 1952, Dirac showed that an n vertices graph with minimum degree (which is the minimum number of edges incident to one vertex) at least n/2 has a Hamilton cycle. This condition is called Dirac type condition. A minimum graph satisfying the Dirac type condition has only n2/4 edges. This value is as almost half as the case on the edges number condition. Therefore the minimum degree is, in a sense, a more essential invariant than the edge number for a Hamilton cycle, and by considering that, we can study the hamiltonicity in more detail.
As stated above, it is an important area of Graph Theory to explore essential invariant condition on the substructures of a graph, and it is the recent topic of my study. In addition to the degree condition, I am studying about concerning the invariants, like the connectivity or the independence number, and the substructures like cycles, paths and spanning trees.