Akira Saito
Department of Computer Science and System Analysis
Nihon University
Sakurajosui 3-25-40
Setagaya-Ku Tokyo 156-8550
JAPAN
email: asaito@chs.nihon-u.ac.jp
Research Interest
My research area is graph theory. I am particularly interested in the following topics.
An edge of a graph is said to be k-contractible if the contraction of this edge results in a k-connected graph. A k-contractible edge can be a useful tool when we study properties of k-connected graphs by inductive arguments. I have obtained useful information on the distribution of k-contractible edges, and hope to gain a deeper understanding about them.
A hamiltonian cycle of a graph is a cycle which contains all the vertices of the graph. A graph having a hamiltonian cycle is called a hamiltonian graph. Although it is an NP-complete problem to decide the hamiltonicity of a graph, there are many sufficient conditions for a graph to be hamiltonian, some of which reveal a strong connection between hamiltonicity and other graph invariants.
A matching is a set of edges which do not share the same endvertices in common. A perfect matching F is a matching such that each vertex is incident to one edge in F. Sumner proved that every connected claw-free graph of even order has a perfect matching. Extending his result, M.D. Plummer and I recently gave a sharp bound to the size of a maximum matching in a star-free graph. Also we determined the graph H such that every connected H-free graph of even order has a perfect matching. We, together with K. Kawarabayashi, further solved the problem of two forbidden subgraphs. But there are still many unsolved problems, and we are working on them.
Awards