英語

斎藤 明

• 住所
  
  

• 研究
  
  

• 論文一覧
  
  

• 賞

住所

〒156-8550
東京都世田谷区桜上水 3-25-40
日本大学文理学部情報システム解析学科
斎藤 明

メールアドレス： asaito@chs.nihon-u.ac.jp

研究

私はグラフ理論の研究をしています。今は以下のような問題に取り組んでいます。

• 可縮な辺の分布

  グラフの辺の両端点を同一視する操作を辺の縮約と言います（辺を１点につぶす、というイメージで考えると分かりやすいかもしれません）。縮約することによりk-連結なグラフが得られるとき、その辺はk-可縮であると言います。k-連結グラフにk-可縮な辺があれば、その辺を縮約することによりより位数の小さいk-連結グラフが得られます。従って、k-連結グラフの性質を位数に関する帰納法で調べる可能性が広がります。私はこのk-可縮辺の分布に大いに関心を持ち、研究を進めています。

• ハミルトンサイクルおよび関連する話題

  グラフの全ての頂点を通るサイクルをハミルトンサイクルと呼びます。グラフにハミルトンサイクルが存在するための非自明な必要十分条件は知られていません。しかし十分条件はいろいろと知られていて、その中には、一見ハミルトン性とは無関係に見えるグラフの性質と深く関わるものがあります。私はこうしたハミルトン性と深く関わる性質を調べています。また、各種のハミルトンサイクルの拡張概念についても研究しています。

• マッチングと禁止部分グラフ

  互いに端点を共有しない辺の集合をグラフのマッチングと呼びます。 もし全て頂点がマッチングのどれかの辺の端点となっていれば、そのマッチングは完全マッチングと呼ばれます。1976年に Sumner は「クローとよばれるグラフを（誘導部分グラフとして）含まない偶位数の連結なグラフは、完全マッチングを持つ」ということを証明しました。私は最近の M.D.Plummer との共同研究で、この逆、すなわち連結グラフ H に対し、「Hを（誘導部分グラフとして）含まない偶位数の連結グラフは完全マッチングを持つ」という命題を成り立たせる H は本質的にクローしか存在しないことを示しました。これは１個のグラフを禁止した状況ですが、その後の研究（M.D. Plummer , K. Kawarabayashi との共同研究）で２個のグラフを禁止する場合の問題も解決できました。しかし、まだ関連する多くの問題が残っており、研究を進めています。

論文一覧

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. Kawaranayashi and M.D. Plummer) Domination in a graph with a 2-factor, J. Graph Theory, 52 (2006) 1--6.
    
    
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 a 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 aspectc ---, Lecture Notes in Computer Science, 4535 (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 (2009) 5000--5010.
    

賞

• 論文賞, 電子情報通信学会, 1989年
  
  
• Editors' Choice, Discrete Mathematics, Elsevier Science, 2000年