Japanese # Akira Saito

by Yoko and Fukiko Saito

• #### List of Papers

• Invited Talks

• #### Awards

Akira Saito
Department of Information Science
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 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.

84. (with J. Fujisawa and M.D. Plummer) Forbidden subgraphs generating a finite set, Discrete Mathematics, 313 (2013) 1835-1842.

85. (with G. Chen and S. Shan) The existence of a 2-factor in a graph satisfying the local Chvatal-Erdos conditions, SIAM Journal of Discrete Mathematics, 27 (2013) 1788-1799.

86. (with C. Ojima and K. Sano) Precoloring extension involving pairs of vertices of small distance, Discrete Applied Mathematics, 166 (2014) 170-177.

87. (with M.D. Plummer) A note on graphs contraction-critical with respect to independence number, Discrete Mathematics, 325 (2014) 85-91.

88. (with Y. Egawa, J. Fujisawa, M. Furuya and M.D. Plummer) Forbidden triples generating s finite set of 3-connected graphs, Electronic Journal of Combinatorics, 22 (2015) #P13.

89. (with Y. Egawa, J. Fujisawa, M.D. Plummer and T. Yamashita) Perfect matchings avoding prescribed edges in a star-free graph, Discrete Mathematics, 338 (2015) 2260-2274.

90. (with K. Sano) Spanning trees homeomorphic to a small tree, Discrete Mathematics, 339 (2016) 677-681.
91. (with. L. Xiong) The Ryjacek closure and a forbidden subgraph, Discussiones Mathematicae Graph Theory, 36 (2016) 621-628.

92. (with N. Ananchuen and W. Ananchuen) Extendability of the complementary prism of bipartite graphs, Aurtralasian Journal of Combinatorics, 66 (2016) 436-448.

93. (with M.D. Plummer) Toughness, binding number and restricted matching extension in a graph, Discrete Mathematics, 340 (2017) 2665-2672.

94. (with J. Fujisawa and R.E.L. Aldred) Edge proximity and matching extension in punctured planar triangulations, Discrete Mathematics, 340 (2017) 2978-2985.

95. (with G. Chen, M.N. Ellingham and S. Shan) Spanning trails with maximum degree at most four in 2K2-free graphs, Grapns and Combinatorics, 33 (2017) 1095-1101.

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)

22. A spanning tree homeomorphic to a small tree, SIAM Conference on Discrete Mathematics, Hyatt Regency Minneaplois, Minneapolis, Minnesota, U.S.A. (2014)

23. Precoloring extension involving pairs of vertices of small distance, Japanese Conference on Combinatorics and Its Applications 2014, Tsukuba, Japan (2014)

24. Spanning trees homeomorphic to a small tree, International Conference on Graph Theory in Honor of Adrian's Bondy's 70th. Birthday, Fuzhou University, Fuzhou, China (2015)

25. Forbidden subgraphs and 2-factors, The Second Japan-Sino Symposium on Graph Theory, Combinatorics and Their Applications, Tokyo University of Science, Tokyo, Japan (2015)

26. Precoloring extension involving pairs of vertices of small distance, Freiberger Graphentheorietage, TU Bergakademie Freiberg, Freiberg, Germany (2015)

27. Precoloring extension involving pairs of vertices of small distance, Symposium on Graph Theory and Applications 2016, Ateneo de Manila University, Manila The Philippines (2016)

28. Forbidden subgraphs and matchings in graphs, Symposium on Graph Theory and Applications 2016, Ateneo de Manila University, Manila, The Philippines (2016)

29. Forbidden subgraphs and 2-factos in graphs, 1117th Meeting of the American Mathematical Society, University of Georgia, Athens, Georgia, U.S.A. (2016)

Awards

• Best Paper Awards, IEICE Japan, 1989

• Editors' Choice, Discrete Mathematics, Elsevier Science, 2000