文献

J-GLOBAL ID：201202238165622808   整理番号：12A0924172

完全独立全域木の十分条件について

Sufficient Conditions for Completely Independent Spanning Trees

著者 (1件)： ARAKI Toru (Gunma Univ.)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 112  号： 24(COMP2012 8-11)  ページ： 33-38  発行年： 2012年05月07日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： T₁,T₂をグラフGの二つの全域木とする。Gの任意の2頂点u,vに対して,T₁上のu-vパスとT₂上のu-vパスが内素であるとき,T₁とT₂は完全独立であるという。本報告では,グラフに二つの完全独立全域木が存在するための必要十分条件を示す。その特徴付けを用いて,さらに二つの十分条件を証明する。まず,n頂点のグラフの最小次数がn/2以上であるなら,そのグラフに二つの完全独立全域木が存在することを示す。続いて,Gが2連結ならその2乗G²に二つの完全独立全域木が存在することを示す。これらの条件は,いずれもグラフにハミルトニアンサイクルが存在するための十分条件として知られている条件である。(著者抄録)

シソーラス用語： *スパンニング木 ,  *十分条件 ,  グラフ ,  頂点 ,  無次元数 ,  接続 ,  キャラクタリゼーション ,  ハミルトニアン ,  次数
準シソーラス用語： *全域木 ,  特性化 ,  連結

分類 (1件)： グラフ理論基礎  (IA02020S)

引用文献 (4件)：

• GEORGAKOPOULOS, A. A short proof of Fleischner's theorem. Discrete Mathematics. 2009, 309, 6632-6634
• HASUNUMA, T. Completely independent spanning trees in the underlying graph of a line digraph. Discrete Mathematics. 2001, 234, 149-157
• HASUNUMA, T. Completely independent spanning trees in maximal planar graphs. Proceedings of WG2002. 2002
• PETERFALVE, F. Two counterexamples on completely independent spanning trees. Discrete Mathematics. 2012, 312, 808-810

タイトルに関連する用語 (2件)： 全域木 ,  十分条件