Japanese

Akira Saito

• Contact Address
  
  

• Research Interest
  
  

• List of Papers
  
  

• Awards

Contact Address

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.

• Contractible and Related 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.

• Hamiltonian Cycles and Related Topics

  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.

• Matchings and Forbidden Subgraphs

  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.

List of Papers

1. (with M. Kano) [a,b]-factors of graphs, Discrete Mathematics 47 (1983) 113--116.
   
   
2. (with H. Enomoto) Disjoint shortest paths in graphs, Combinatorica 4 (1984) 275--279.
   
   
3. (with H. Enomoto, B. Jackson and P. Katerinis) Toughness and the existence of k-factors, J. Graph Theory 9 (1985) 87--95.
   
   
4. (with B. Bollobas and N. Wormald) Rugular factors of regular graphs, J. Graph Theory 9 (1985) 97--103.
   
   
5. (with T. Songlin) The binding number of line graphs and total graphs, Graphs and Combinatorics 1 (1985) 351--356.
   
   
6. (with Y. Egawa and H. Enomoto) Contractible edges in triangle-free graphs, Combinatorica 6 (1986) 269--274.
   
   
7. (with Y. Egawa and H. Enomoto) On component factors, Graphs and Combinatorics 2 (1986) 223-225.
   
   
8. (with K. Ando and H. Enomoto) Contractible edges in 3-connected graphs, J. Combinatorial Theory (B) 42 (1987) 87--93.
   
   
9. (with Y. Egawa and H. Enomoto) Factors and induced subgraphs, Discrete Mathematics 68 (1988) 179--189.
   
   
10. (with M. Ito and T. Nishizeki) Secret sharing scheme realizing general access structure (Japanese), Trans. IEICE of Japan J71-A (1988) 1592--1598.
    
    
11. (with K. Ota) Non-separating induced cycles in 3-connected graphs, Scientia (A) 2 (1988) 101--105.
    
    
12. Long cycles through specified vertices in a graph, J. Combinatorial Theory (B) 47 (1989) 220--230.
    
    
13. (with D. Holton, B. Jackson and N. Wormald) Removable edges in 3-connected graphs, J. Graph Theory, 14 (1990) 465--473.
    
    
14. Covering contractible edges in 3-connected graphs I: Covers of size three are cutsets, J. Graph Theory, 14 (1990) 635--643.
    
    
15. (with R. Aldred, B. Jackson and D. Lou) Partitioning regular graphs into equi-cardinal linear forests, Discrete Mathematics, 88 (1991) 1--9.
    
    
16. (with Y. Egawa) Contractible edges in non-separating cycles, Combinatorica, 11 (1991) 389--392.
    
    
17. One-factors and k-factors, Discrete Mathematics, 91 (1991) 323--326.
    
    
18. (with A. Kaneko) Cycles intersecting a prescribed vertex set, J. Graph Theory, 15 (1991) 655--664.
    
    
19. Cycles of length 2 modulo 3 in graphs, Discrete Mathematics, 101 (1992) 285--289.
    
    
20. (with M. Ito and T. Nishizeki) Multiple assignment scheme for sharing secret, J. Cryptology, 6 (1993) 15--20.
    
    
21. (with N. Dean and L. Lesniak) Cycles of length 0 modulo 4 in graphs, Discrete Math., 121 (1993) 37--49.
    
    
22. (with M. Watanabe) Partitioning graphs into induced stars, Ars Combinatoria, 36 (1993) 3--6.
    
    
23. (with G. Chen) Graphs with a cycle of length divisible by three, J. Combinatorial Theory (B)., 60 (1994) 277--292.
    
    
24. (with Y. Egawa, K. Ota and X. Yu) Noncontractible edges in 3-connected graphs, Combinatorica, 15 (1995) 357--364.
    
    
25. (with H. Enomoto, J. van den Heuvel and A. Kaneko) Relative length of long paths and cycles in graphs with large degree sums, J. Graph Theory, 20 (1995) 213--225.
    
    
26. (with G. Chen, Y. Egawa and X. Liu), Essential independent sets and hamiltonian cycles, J. Graph Theory, 21 (1996) 243--250.
    
    
27. Local Ore-type conditions for graphs of diameter two to be hamiltonian, J. Combinatorial Mathematics and Combinatorical Computing, 20 (1996) 155--159.
    
    
28. (with T. Nishimura) Two recursive theorems on n-extendability, Discrete Mathematics, 162 (1996) 319--323.
    
    
29. Fan-type theorem for path-connectivity, Combinatorica, 16 (1996) 433--437.
    
    
30. (with B. Bollobas, O. Riordan, Z. Ryjacek and R.H. Schelp) Closure and hamiltonian-connectivity of claw-free graphs, Discrete Mathematics, 195 (1999) 67--80.
    
    
31. Long paths, long cycles and their relative length, J. Graph Theory, 30 (1999) 91--99.
    
    
32. Degree sums and graphs that are not covered by two cycles, J. Graph Theory, 32 (1999) 51--61.
    
    
33. (with H. Enomoto and M.D. Plummer) Neighborhood unions and factor-critical graphs, Discrete Mathematics, 205 (1999) 217--220
    
    
34. (with Z. Ryjacek and R.H. Schelp) Closure, 2-factors and cycles coverings in claw-free graphs, J. Graph Theory, 32 (1999) 109--117.
    
    
35. (with M.D. Plummer) Closure and factor-critical graphs, Discrete Mathematics, 215 (2000) 171--179.
    
    
36. (with G. Chen, J.R. Faudree and R.J. Gould) 2-Factors in claw-free graphs, Discussiones Mathematicae Graph Theory, 20 (2000) 165--172.
    
    
37. (with G. Chen, H. Enomoto, K. Kawarabayashi, D. Lou and K. Ota) Vertex-disjoint cycles containing specified edges in a bipartite graph, Australasian Journal of Combinatorics, 23 (2001) 37--48.
    
    
38. (with R. Ryjacek and R.H. Schelp) Claw-free graphs with complete closure, Discrete Mathematics, 236 (2001) 325--338.
    
    
39. (with Rao Li and R.H. Schelp) Relative length of longest paths and cycles in 3-connected graphs, J. Graph Theory, 37 (2001) 137--156.
    
    
40. (with K. Kawarabayashi and K. Ota) Hamiltonian cycles in n-factor-critical graphs, Discrete Mathematics, 240 (2001) 71--82.
    
    
41. (with K. Kawarabayashi and K. Ota) Hamiltonian cycles in n-extendable graphs, J. Graph Theory, 40 (2002) 75--82.
    
    
42. (with G. Chen, B. Wei and X. Xhang) The hamiltonicity of bipartite graphs involving neighborhood unions, Discrete Mathematics, 249 (2002) 45--56.
    
    
43. (with R.J. Faudree, R.J. Gould, A.V. Kostochka, L. Lesniak and I. Schiermeyer) Degree conditions for k-ordered hamiltonian graphs, J. Graph Theory, 42 (2003) 199--210.
    
    
44. (with. N. Ananchuen) Factor-criticality and complete closure of graphs, Discrete Mathematics, 265 (2003) 13--21.
    
    
45. (with K. Ando, M. Hagita, M. Kano, A. Kaneko, K. Kawarabayashi) Cycles having the same modularity and removable edges in 2-connected graphs, Discrete Mathematics, 265 (2003) 23--30.
    
    
46. (with K. Kawarabayashi and M.D. Plummer) On two equimatchable graph classes, Discrete Mathematics, 266 (2003) 263--274.
    
    
47. Splitting and contractible edges in 4-connected graphs, J. Combinatorial Theory (B), 88 (2003) 227--235.
    
    
48. (with R.E.L. Aldred, D.A. Holton and D. Lou) M-alternating paths in n-extendable bipartite graphs, Discrete Mathematics, 269 (2003) 1--11.
    
    
49. (with T. Yamashita) A note on dominating cycles in tough graphs, Ars Combinatoria, 69 (2003) 3--8.
    
    
50. (with D. Lou and L. Teng) To determine 1-extendable graphs and its algorithm, Ars Combinatoria, 69 (2003) 223-228.
    
    
51. (with T. Yamashita) Cycles within specified distance from each vertex, Discrete Mathematics, 278 (2004) 219--226.
    
    
52. (with H. Enomoto, A. Kaneko and B. Wei) Long cycles in triangle-free graphs with prescribed independence number and connectivity, J. Combinatorial Theory (B), 91 (2004) 43--55.
    
    
53. (with G. Chen, H. Enomoto, K. Kawarabayashi, D. Lou and K. Ota) Vertex-disjoint cycles containing specified vertices in a bipartite graph, J. Graph Theory, 46 (2004) 145-166.
    
    
54. (with R.J. Faudree, R.J. Gould, M.S. Jacobson and L. Lesniak) Toughness, degrees and 2-factors, Discrete Mathematics, 286 (2004) 245--249.
    
    
55. (with D. Lou and Lihua Teng) A note on internally disjoint alternating paths in bipartite graphs, Discrete Mathematics, 290 (2005) 105--108.
    
    
56. (with M.D. Plummer) Forbidden subgraphs and bounds on the size of a maximum matching, J. Graph Theory, 50 (2005) 1--12.
    
    
57. (with R.J. Faudree, R.J. Gould, M.S. Jacobson and L. Lesniak) A note on 2-factors with two components, Discrete Mathematics, 300 (2005) 218--224.
    
    
58. (with K. Kawarabayashi and M.D. Plummer) Domination in a graph with a 2-factor, J. Graph Theory, 50 (2006) 1--12.
    
    
59. (with S. Fujita, K. Kawarabayashi, C.L. Lucchesi, K. Ota and M.D. Plummer) A pair of forbidden subgraphs and perfect matchings, J. Combinatorial Theory (B), 96 (2006) 315--324.
    
    
60. Contractible edges and removable edges in a graph with large minimum degree, Australasian Journal of Combinatorics, 35 (2006) 313--318.
    
    
61. (with R.J. Faudree, R.H. Schelp and I. Schiermeyer) Degree conditions for hamiltonicity : counting the number of missing edges, Discrete Mathematics, 307 (2007) 873--877
    
    
62. (with Y. Hasegawa) Graphs with small boundary, Discrete Mathematics, 307 (2007) 1801--1807
    
    
63. (with S. Bau) Reduction for 3-connected graphs of minimum degree at least four, Graphs and Combinatorics, 23 (Supplement) (2007) 135--144.
    
    
64. (with S. Fujita and T. Yamashita) Edge-disjoint cycles in graphs, Discrete Mathematics, 307 (2007) 2934--2942.
    
    
65. (with G. Chen, R.J. Gould, K. Kawarabayashi, K. Ota and I. Scheiermeyer) The Chvatal-Erdos condition and 2-factors with a specified number of components, Discussiones Mathematicae Graph Theory, 27 (2007) 401--407.
    
    
66. (with J. Fujisawa, A. Hansberg, T. Kubo, M. Sugita and L. Volkmann) Independence and 2-domination in bipartite graphs, Australasian J. Combinatorics, 40 (2008) 265--268.
    
67. Chvatal-Erdos Theorem --- old theorem with new aspects ---, Lecture Notes in Computer Science, 2535 (2008) 191--200.
    
    
68. (with R.E.L. Aldred and J. Fujisawa) Two forbidden subgraphs and the existence of a 2-factor in graphs, Australasian Journal of Combinatorics, 44 (2009) 235--246.
    
    
69. (with L. Xiong) Closure, stability and iterated line graphs with a 2-factor, Discrete Mathematics, 309 (200) 5000-5010.
    
    
70. (with R.E.L. Aldred and J. Fujisawa) Forbidden subgraphs and the existence of a 2-factor, Journal of Graph Theory, 64 (2010) 250-266.
    
    
71. (with Kenji Kimura and Masayuki Koyama) Small alliances in a weighted graph, Discrete Applied Mathematics, 158 (2010) 2071-2074.
    
    
72. (with S. Akbari, A. Doni, M. Ghanbari and S. Jahanbekam) List-coloring of graphs and cycles of length divisible by a given number, Contemporary Mathematics, 531 (2010) 117-125.
    
    
73. (with J. Fujisawa and I. Schiermeyer) Closure for spanning trees and distant area, Discussiones Mathematicae Graph Theory, 31 (2011) 143-159.
    
    
74. (with K. Ota and M.D. Plummer) Forbidden triples for perfect matchings, Journal of Graph Theory, 67 (2011) 250-259.
    
    
75. (with R.E.L. Aldred, Y. Egawa, J. Fujisawa and K. Ota) The existence of a 2-factor in K_1,n-free graphs with large connectivity and large edge-connectivity, Journal of Graph Theory, 68 (2011) 77-89.
    

Awards

• Best Paper Awards, IEICE Japan, 1989
  
  
• Editors' Choice, Discrete Mathematics, Elsevier Science, 2000