Japanese


Picture by Yoko and Fukiko Saito



Akira Saito


by Yoko and Fukiko Saito

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.


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 K1,n-free graphs with large connectivity and large edge-connectivity, Journal of Graph Theory, 68 (2011) 77-89.

  76. (with J. Fujisawa, S. Fujita, M.D. Plummer and I. Schiermeyer) A pair of forbidden subgraphs and perfect matching in graphs of high connectivity, Combinatorica, 31 (2011) 703-723.

  77. (with H. Bruhn) Alique or hole in claw-free graphs, Journal of Combinatorial Theory, Series B, 102 (2012) 1-13.

  78. (with M. Kano, A. Kyaw, H. Matsuda, K. Ozeki and T. Yamashita) Spanning trees with a bounded number of leaves in a claw-free graph, Ars Combinatoria, 103 (2012) 137-154.

  79. (with G. Chen, Y. Egawa and R.J. Gould) Forbidden pairs for k-connected hamiltonian graphs, Discrete Mathematics, 312 (2012) 938-942.

  80. (with G. Chen, K. Ota and Y. Zhao) Hamiltonian cycles with all small even chords, Discrete Mathematics, 312 (2012) 1226-1240..

  81. (with J. Fujisawa) A pair ot forbidden subgraphs and 2-factors, Combinatorics, Probability and Computing, 21 (2012) 149-158.

  82. (with M. Kano) Star-factors with large components, Discrete Mathematics, 312 (2012) 2005-2008.

  83. (with J. Harant, A. Kemnitz and I. Schiermeyer) Closures, cycles and path, Journal of Graph Theory, 69 (2012) 314-323.


Invited Talks

  1. Cycles modulo k in graphs, Petersen Graph Theory Conference, Hinsgavl, Denmark (1990)

  2. Recent topics on hamiltonian graphs (in Japanese), The Mathematical Society of Japan Autumn Meeting, Nagoya University, Nagoya, Japan (1992)

  3. Closure and cycle properties of claw-free graphs, Fifth Czeck-Slovak International Symposium on Combinatorics, Graph Theory , Algorithms and Applications, Charles University, Praha, Czech Republic (1998)

  4. Forbidden subgraphs and matchings in graphs, International Workshop on Combinatorics, Keio University, Yokohama, Japan (2004)

  5. Factors and forbidden subgraphs, Atlanta International Colloquium on Graph Theory, Gerogia State University, Atlanta, U.S.A. (2004)

  6. Cycles within specified distance from each vertex, SIAM Conference on Discrete Mathematics, Loews Vanderbilt Plaza Hotel, Nashville, U.S.A. (2004)

  7. Chvatal-Erdos condition -Old theorem with new aspects, Workshop Cycles and Colouring '04, Hotel Meander, Tatranska Strba. Slovakia (2004)

  8. Transformations of graphs (in Japanese), The Mathematical Society of Japan Autumn Meeting, Hokkaido University, Sapporo, Japan (2004)

  9. A dominating cycle and dominating cycles in a graph, The 9th. C5 Graph Theory Workshop, Pension Panorama, Kurort Rathen, Germany (2005)

  10. Forbidden subgraphs and matchings in graphs, Third Pacific Rim Conference on Mathematics, Fudan University, Shanghai, China (2005)

  11. Transformations of graphs -contraction and closure-, The 13th. National Mathematics Conference and Indonesian Mathematical Society Congress, Semarang State University, Semarangm Indonesia (2006)

  12. Chvatal-Erdos theorem -ole theorem with new aspects-, Kyoto International Conference on Computational Geometry and Graph Theory, Kyoto University, Kyoto, Japan (2007)

  13. Forbidden subgraphs and matchings in graphs, The 21st. Cumberland Conference on Graph Theory, Combinatorics and Computing, Vanderbilt University, Nashville, U.S.A. (2008)

  14. Bipartite graphs, The Second International Conference on Mathematics and Natural Sciences, Bandung Institute of Technology, Bandung, Indonesia (2008)

  15. Forbidden subgraphs and 2-factors, 2009 SIAM Annual Meeting, Colorado Convention Center, Denver, U.S.A. (2009)

  16. Cycles of length modulo k, Paths, Cycles and Graph Structures Workshop, University of Colorado Denver, Denver, U.S.A. (2009)

  17. Forbidden subgraphs and factors in graphs, The 8th. French Combinatorial Conference, University of Paris XI, Orsay, France (2010)

  18. Forbidden subgraphs generating a finite set, Workshop Cycles and Colourings 2010, Tatranska Strba, Slovakia (2010)

  19. Forbidden subgraphs and 2-factors, The 4th. International Conference on Combinatorics, Graph Theory and Applications, Elgersburg, Germany (2011)

  20. Forbidden subgraphs and 2-factors, Atlanta Lecture Series in Combinatorics and Graph Theory IV, Georgia State University, Atlanta, U.S.A. (2011)

  21. Forbidden subgraphs generating a finite set, The 5th International Workshop on Optimal Network Topologies, Bandung Institute of Technology, Bandung, Indonesia (2012)


Awards