著書 【 表示 ／ 非表示 】

著書 【 表示 ／ 非表示 】

• IT Text 離散数学

  松原良太,大嶌彰昇,藤田慎也,小関健太,中上川友樹,佐久間雅,津垣正男 (担当： 共著 , 担当範囲: 4章　グラフと木 )

  オーム社  2010年10月

  　概要を見る

  情報系を学ぶ学生にとっての基礎数学として、わかりやすい言葉と高校までに学んだ範囲で離散数学を基礎からていねいに解説した教科書。システム開発者や他分野の方にも基礎概念の整理に役立つ一冊。

論文 【 表示 ／ 非表示 】

論文 【 表示 ／ 非表示 】

• A Note on Enumeration of 3-Edge-Connected Spanning Subgraphs in Plane Graphs

  MATSUI Yasuko, OZEKI Kenta

  IEICE Transactions on Information and Systems ( 一般社団法人 電子情報通信学会 )  104 ( 3 ) 389 - 391   2021年

  共著

  　概要を見る

  <p>This paper deals with the problem of enumerating 3-edge-connected spanning subgraphs of an input plane graph. In 2018, Yamanaka et al. proposed two enumeration algorithms for such a problem. Their algorithm generates each 2-edge-connected spanning subgraph of a given plane graph with <i>n</i> vertices in O(<i>n</i>) time, and another one generates each <i>k</i>-edge-connected spanning subgraph of a general graph with <i>m</i> edges in O(<i>mT</i>) time, where <i>T</i> is the running time to check the <i>k</i>-edge connectivity of a graph. This paper focuses on the case of the 3-edge-connectivity in a plane graph. We give an algorithm which generates each 3-edge-connected spanning subgraph of the input plane graph in <i>O</i>(<i>n</i>²) time. This time complexity is the same as the algorithm by Yamanaka et al., but our algorithm is simpler than theirs.</p>

  DOI CiNii

• Thomassen's conjecture for line graphs of 3-hypergraphs

  Li Binlong, Ozeki Kenta, Ryjacek Zdenek, Vrana Petr

  DISCRETE MATHEMATICS   343 ( 6 )   2020年06月  [査読有り]

  共著

  Web of Science DOI

• Long Paths in Bipartite Graphs and Path-Bistar Bipartite Ramsey Numbers

  Furuya Michitaka, Maezawa Shun-ichi, Ozeki Kenta

  GRAPHS AND COMBINATORICS   36 ( 1 ) 167 - 176   2020年01月  [査読有り]

  共著

  Web of Science DOI

• A degree sum condition on the order, the connectivity and the independence number for hamiltonicity

  Chiba Shuya, Furuya Michitaka, Ozeki Kenta, Tsugaki Masao, Yamashita Tomoki

  ELECTRONIC JOURNAL OF COMBINATORICS   26 ( 4 )   2019年12月  [査読有り]

  共著

  Web of Science

• On the minimum leaf number of cubic graphs

  Goedgebeur Jan, Ozeki Kenta, Van Cleemput Nico, Wiener Gabor

  DISCRETE MATHEMATICS   342 ( 11 ) 3000 - 3005   2019年11月  [査読有り]

  共著

  Web of Science DOI

全件表示 >>

総説・解説記事 【 表示 ／ 非表示 】

総説・解説記事 【 表示 ／ 非表示 】

• エレガントな解答を求む 2021年4月号出題 2

  小関 健太

  数学セミナー ( 日本評論社 )    2021年04月  [依頼有り]

  総説・解説（商業誌）   単著

  　概要を見る

  図1 はあるホテルの見取り図で，斜線部が部屋で白 い部分が廊下を表している．すべての廊下には電灯が ついており，丸数字が表すスイッチにより隣接する廊 下の電灯のon–off を切り替えられる．ただし1 つの スイッチは連動しており，例えば1 のスイッチを押す と，図2 のように，1 と2 の間の廊下，1 と3 の間の 廊下，1 と4 の間の廊下の3 つの電灯のon–off が同時 に変わってしまう．(他の廊下の電灯のon–off は変わ らない) (1) 以下のどの状況のときに全部の廊下の電灯をoff に できるでしょうか？ (A) 全部の電灯がon． (B) 1 と2 の間の廊下と5 と6 の間の廊下だけ 電灯がoff，他はon， (C) 1 と2 の間の廊下と4 と5 の間の廊下だけ 電灯がoff，他はon， (2) 他の状態からはじめたときや別のホテルでも考え てみてください．すべてをoff にできるための必 要十分条件を，すっきりした形で言えないでしょ うか？ (1) のみの解答でも構いませんので，ぜひ考えてみて ください．

• エレガントな解答を求む 2020年4月号出題 2

  小関 健太,阿部 敏生

  数学セミナー ( 日本評論社 )    2020年04月  [依頼有り]

  総説・解説（商業誌）   共著

  　概要を見る

  平面上にある点の集合 S に対し，次の 3 つのルールで何本かの線を引くことを考える． 各線は S のある点からスタートし，S の点をちょうど 1 つ通過し S の点で終わる． 線同士は S の点以外で交差しない（各線は自分自身とも S の点以外では交差できない）． S の各点で線の出入りは合計 3 回まで可能である． 例えば図 1 のように進行すると，3 本の線を引いた時点ですべての点で線の出入りがちょうど 3 回行われ，これ以上線が引けなくなる．特に，各線はスタートの点を通過したり，S の同じ点に戻ってきたりしてもよいことに注意されたい．一方で図 2 のように進行すると，線を 2 本引いた時点で線が引けなくなってしまう． (1) S が 6 点のとき，最大で何本の線が引けるか ? (2) S が 6 点のとき，それ以上線が引けなくなるまでに少なくとも何本の線を引く必要があるか ? 余裕のある方は，S が n 点のときも考えてみてください．

• ネットワークとグラフ理論

  小関 健太

  数理科学 ( 株式会社サイエンス社 )    2020年02月  [依頼有り]

  総説・解説（商業誌）   単著

• すごい反例　組合せ論・グラフ理論

  小関 健太

  日本評論社     2019年11月  [依頼有り]

  総説・解説（商業誌）   単著

• エレガントな解答を求む 2019年4月号出題 1

  小関 健太

  数学セミナー ( 日本評論社 )    2019年04月

  総説・解説（大学・研究所紀要）   単著

  　概要を見る

  正三角形が並んでいる図形をn段の三角格子とよぶ．ただし，nは外側の各辺に並んでいる正三角形の数である． 三角格子の頂点を何色かで塗り，3 頂点がすべて同じ色の正三角形(単色三角形とよぶ) を見つけたい．ただし，ここでいう単色三角形はいくつかの小三角形を組合わせたもののみであり，向きは上向きでも下向きでも構わないとする． (1) 4段の三角格子は，頂点をどのように2色で塗っても単色三角形を持つことを示せ． (2) 5段の三角格子の3色での頂点の塗り方で，単色三角形を持たないものを一つ示せ． (3) 10; 000段の三角格子は頂点をどのように3色で塗っても単色三角形を持つことを示せ．

全件表示 >>

科研費（文科省・学振）獲得実績 【 表示 ／ 非表示 】

科研費（文科省・学振）獲得実績 【 表示 ／ 非表示 】

• トポロジー的な性質を持つハミルトン閉路を利用した， 閉曲面上のグラフの頂点彩色 研究課題

  基盤研究(C)

  研究期間:  2018年04月  -  2021年03月  代表者:  小関 健太

  　概要を見る

  本研究の目的は，閉曲面上のグラフについて，ハミルトン閉路を利用した新しい彩色の手法を提案することである

その他競争的資金獲得・外部資金受入状況 【 表示 ／ 非表示 】

その他競争的資金獲得・外部資金受入状況 【 表示 ／ 非表示 】

• グラフのハミルトン閉路に関する Nash-Williams と Grunbaum 予想の解決

  提供機関:  公益財団法人 住 友 財 団  住友財団 基礎科学研究助成

  研究期間： 2014年11月  -  2015年11月  代表者:  小関 健太

  　概要を見る

  グラフとは，頂点集合と辺集合（頂点集合の二元部分集合族）からなる構造として定義される．グラフの全ての頂点をちょうど一度ずつ通る閉路をハミルトン閉路と呼び，ちょうど一度ずつ通る道をハミルトン道と呼ぶ．「与えられたグラフがハミルトン閉路をもつかどうか決定する」という問題は，組み合わせ最適化の分野において特に重要な巡回セールスマン問題とも密接に関係しているため，グラフ理論の中でも非常に多くの研究がなされている． ここで, グラフを平面グラフなどトポロジー的な閉曲面上のものに限ると，この問題は四色定理とも関わりを持つこともあり，多くの研究が行われている．本研究もこの流れに沿うものである．閉曲面上のグラフのハミルトン性については，表 1 にあるように 1956年の Tutte の結果以来様々な研究者が研究を行ってきた．例えば，1983年に Thomassen が「平面上の任意の 4-連結グラフはハミルトン連結である」と示したことを意味している．なお，グラフが，``任意の 2頂点に対し，それらを結ぶハミルトン道が存在する'' という性質を満たすとき，ハミルトン連結であるという． このように，この分野についていくつかの結果が示されているが，未解決な部分も存在する．特に，次の命題は，40年以上未解決であり，グラフ理論全体の中でも重要なものとなっている．この予想の完全解決が研究の目的である． 予想 (Grunbaum `70, Nash-Williams `73) トーラス上の任意の 4-連結グラフはハミルトン閉路を持つ．

研究発表 【 表示 ／ 非表示 】

研究発表 【 表示 ／ 非表示 】

• グラフの出次数制約のある向き付け

  小関健太

  第31回 位相幾何学的グラフ理論研究集会  2019年11月15日  

• An orientation of graphs with out-degree constraint

  Kenta Ozeki  [招待有り]

  The 2nd East Asia Workshop on Extremal and Structural Graph Theory  2019年11月01日  

• Spanning trees with few leaves in graphs on surfaces

  Kenta Ozeki  [招待有り]

  International Conference on Graph Theory, Combinatorics and Applications  2019年06月18日  

• Spanning trees with few number of leaves in 4-connected graphs on higher genus surface

  Kenta Ozeki

  Structural Graph Theory and Graph Colorings  2019年04月29日  

• Spanning trees with few leaves in graphs on surfaces

  Kenta Ozeki

  Joint Mathematics Meetings  (Baltimore)  2019年01月18日   American Mathematical Society, Mathematical Association of America

全件表示 >>

学会誌・論文誌編集等 【 表示 ／ 非表示 】

学会誌・論文誌編集等 【 表示 ／ 非表示 】

• Journal of Algebra Combinatorics Discrete Structures and Applications

  Editorial Board 

  2014年05月

  -

  継続中

   

• Theory and Applications of Graphs

  Editorial Board 

  2014年01月

  -

  継続中

   

• Graphs and Combinatorics

  Managing Editor 

  1985年01月

  -

  継続中

   

担当授業科目（学内） 【 表示 ／ 非表示 】

担当授業科目（学内） 【 表示 ／ 非表示 】

全件表示 >>

担当経験のある授業科目(学外) 【 表示 ／ 非表示 】

担当経験のある授業科目(学外) 【 表示 ／ 非表示 】