| 講演名 | 2012/5/7 完全独立全域木の十分条件について 荒木 徹, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | T_1, T_2をグラフGの二つの全域木とする.Gの任意の2頂点u, vに対して,T_1上のu-vパスとT_2上のu-vパスが内素であるとき,T_1とT_2は完全独立であるという.本報告では,グラフに二つの完全独立全域木が存在するための必要十分条件を示す.その特徴付けを用いて,さらに二つの十分条件を証明する.まず,n頂点のグラフの最小次数がn/2以上であるなら,そのグラフに二つの完全独立全域木が存在することを示す.続いて,Gが2連結ならその2乗G^2に二つの完全独立全域木が存在することを示す.これらの条件は,いずれもグラフにハミルトニアンサイクルが存在するための十分条件として知られている条件である. |
| 抄録(英) | Two spanning trees T_1 and T_2 of a graph G are completely independent if, for any two vertices u and v, the paths from u to v in T_1 and T_2 are internally disjoint. In this report, we show that two sufficient conditions for the existence of completely independent spanning trees. First we show that a graph of n vertices has two completely independent spanning trees if the minimum degree of the graph is at least n/2. Then we prove that the square of a 2-connected graph has two completely independent spanning trees. These conditions are known to be sufficient conditions for Hamiltonian graphs. |
| キーワード(和) | 全域木 / 完全独立全域木 / Diracの定理 / Fleischnerの定理 |
| キーワード(英) | Spanning tree / Completely independent spanning trees / Dirac's Theorem / Fleischner's Theorem |
| 資料番号 | Vol.2012-AL-140 No.5 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2012/5/7(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 完全独立全域木の十分条件について |
| サブタイトル（和） | |
| タイトル（英） | Sufficient Conditions for Completely Independent Spanning Trees |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 全域木 / Spanning tree |
| キーワード(2)（和/英） | 完全独立全域木 / Completely independent spanning trees |
| キーワード(3)（和/英） | Diracの定理 / Dirac's Theorem |
| キーワード(4)（和/英） | Fleischnerの定理 / Fleischner's Theorem |
| 第 1 著者 氏名（和/英） | 荒木 徹 / TORU ARAKI |
| 第 1 著者 所属（和/英） | 群馬大学大学院工学研究科情報工学専攻 Department of Computer Science, Gunma University |
| 発表年月日 | 2012/5/7 |
| 資料番号 | Vol.2012-AL-140 No.5 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | 24 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |