文献

J-GLOBAL ID：201502210996515960   整理番号：15A1239463

3サイクル-2被覆を有したグラフ

Graphs with a 3-Cycle-2-Cover

著者 (4件)： CHEN Zhi-Hong (Butler Univ., Dep. of Computer Sci. and Software Engineering, 46208, Indianapolis, IN, USA) ,  HAN Miaomiao (West Virginia Univ., Dep. of Mathematics, 26506, Morgantown, WV, USA) ,  LAI Hong-Jian (West Virginia Univ., Dep. of Mathematics, 26506, Morgantown, WV, USA) ,  ZHAN Mingquan (Millersville Univ. of Pennsylvania, Dep. of Mathematics, 17551, Millersville, PA, USA)
資料名： Graphs and Combinatorics  (Graphs and Combinatorics)
巻： 31  号： 6  ページ： 2103-2111  発行年： 2015年11月 
JST資料番号： X0108A  ISSN： 0911-0119  CODEN： GRCOE5  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： もしグラフGが,Gの全てのエッジが{C₁,C₂,C₃}の正確に2つのメンバ中にあるような3つの偶部分グラフC₁,C₂及びC₃を持つならば,Gは3サイクル-2被覆を持つと言う。S₃を3サイクル-2被覆を許容するグラフの族を記すとし,S(h,k)={G:Gはk-エッジ-連結となるには高々hのエッジが短い}とする。Catlin(J Gr Theory 13:465~483,1989)はもしその還元がS₃中にあるならばグラフG∈S₃であるような還元法を導入し,グラフ族S(5,4)中のグラフがS₃中にあるあるいはその還元が唯一のグラフから構成される禁止コレクション中にあるいずれかである事を証明した。本論文において,筆者らはもしその弱還元がS₃中にあるならばグラフG∈S₃であるようなS₃に対する弱還元を導入し,整数h≧0に対するS(h,4)を含むこれらの族中のどのようなグラフもS₃中にあるあるいはその弱還元が有限禁止グラフのコレクションへと落ちるいずれかの特性を有した幾つかのグラフ族を同定した。Copyright 2015 Springer Japan Translated from English into Japanese by JST.

シソーラス用語： グラフ理論 ,  *サイクル ,  *被覆 ,  *グラフ ,  還元
準シソーラス用語： 3サイクル-2被覆 ,  *ノーウェアゼロフローグラフ ,  *折り畳み可能グラフ

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

引用文献 (23件)：

• Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, New York (2008)
• Boyd, S., Sitters, R., Ster, S., Stougie, L.: The traveling salesman problem on cubic and subcubic graphs. Math. Progr. Ser. A 144, 227-247 (2014)
• Broersma, H.J., Xiong, L.: A note on minimum degree conditions for supereulerian graphs. Discret. Appl. Math. 120, 35-43 (2002)
• Catlin, P.A.: A reduction method to find spanning Eulerian subgraphs. J. Gr. Theory 12, 29-44 (1988)
• Catlin, P.A.: Double cycle covers and the Petersen graph. J. Gr. Theory 13, 465-483 (1989)

タイトルに関連する用語 (2件)： サイクル ,  グラフ