文献

J-GLOBAL ID：201202228216850198   整理番号：12A1072936

次数制約を有したグラフ中の最大有向切断

Maximum Directed Cuts in Graphs with Degree Constraints

著者 (2件)： XU Baogang (Nanjing Normal Univ., Nanjing, CHN) ,  YU Xingxing (Georgia Inst. Technol., GA, USA)
資料名： Graphs and Combinatorics  (Graphs and Combinatorics)
巻： 28  号： 4  ページ： 563-574  発行年： 2012年 
JST資料番号： X0108A  ISSN： 0911-0119  CODEN： GRCOE5  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 最大切断問題はNP困難問題であり,広範に研究されて来た。Alon等(J Graph Theory 55:1-13,2007)は最大切断問題の有向版を研究し,グラフのHall比に対するその関係を観察した。彼らはその他の間で,もし非循環有向グラフがm個のエッジを持ち,各頂点が高々1の入次数あるいは出次数を持つならば,それが少なくても2m/5のサイズの有向切断を持つ事を証明した。Lehel等(J Graph Theory 61:140-156,2009)は”非循環有向グラフ”を”有向三角形を含まない有向グラフ”に置き換える事によってこの結果を拡張した。本論文において,筆者らはその最大有向切断が正確に2m/5のエッジを持つm個のエッジを有した非循環有向グラフを特徴付けて,そして筆者らのアプローチはLehel等の結果の代替証明を与えた。また,筆者らは有向グラフD(有向三角形を有した)の各頂点が高々1の入次数あるいは出次数を持ち,そしてD中の任意の最大有向切断が正確にβ|E(D)|のサイズを持つようなDに対して無限に多くの正有理数β<2/5が存在する事を示した。(翻訳著者抄録)

シソーラス用語： グラフ理論 ,  最大値 ,  *有向グラフ ,  *切断 ,  制約条件 ,  三角形 ,  頂点
準シソーラス用語： エッジ ,  *次数 ,  特徴付け ,  *非循環有向グラフ

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

引用文献 (18件)：

• 1. Alon, N.: Bipartite subgraphs. Combinatorica 16, 301-311 (1996)
• 2. Alon, N., Bollobás, B., Gyárfás, A., Lehel, J., Scott, A.: Maximum dicuts in acyclic digraphs. J. Graph Theory 55, 1-13 (2007)
• 3. Berman, P., Karpinski, M.: On some tighter inapproximability results. (extended abstract.) In: Lecture Notes in Computer Science, vol. 1644, pp. 200-209. Springer, Berlin (1999)
• 4. Bondy, J.A., Locke, S.C.: Largest bipartite subgraphs in triangle-free graphs with maximum degree three. J. Graph Theory 10, 477-504 (1986)
• 5. Cropper, M., Gyárfás, A., Lehel, J.: Hall ratio of the Mycielski graphs. Discrete Math. 306, 1988-1990 (2006)

タイトルに関連する用語 (3件)： 次数 ,  制約 ,  グラフ