文献

J-GLOBAL ID：201802211260857221   整理番号：18A1789087

三角に含まれないエッジを有する4-接続グラフにおける縮小可能エッジ数の下限

Lower Bound on the Number of Contractible Edges in a 4-Connected Graph with Edges Not Contained in Triangles

著者 (3件)： EGAWA Yoshimi (Tokyo Univ. Sci., Tokyo, JPN) ,  KOTANI Keiko (Tokyo Univ. Sci., Tokyo, JPN) ,  NAKAMURA Shunsuke (Tokyo Univ. Sci., Tokyo, JPN)
資料名： Graphs and Combinatorics  (Graphs and Combinatorics)
巻： 34  号： 5  ページ： 965-987  発行年： 2018年 
JST資料番号： X0108A  ISSN： 0911-0119  CODEN： GRCOE5  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： ・4-接続グラフをG,Gのエッジで三角に含まれないものの集合を~E(G),Gの4-縮小可能エッジの集合をE_c(G)と定義。
・さらに,4-非縮小可能エッジの集合をE_n(G),~E(G)とE_n(G)の集合積のエッジから生成される部分グラフを^E(G)と定義。
・一定の条件で,|E_c(G)|≧(|~E(G)|+4)/2 が成立することを命題として証明。
・|~E(G)|≧1であれば,|E_c(G)|≧(|^E(G)|+8)/4 が成立することを定理として証明。

シソーラス用語： *グラフ ,  *端部 ,  頂点 ,  ループ ,  *縮小 ,  下限 ,  グラフ理論
準シソーラス用語： *エッジ ,  下限値

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

引用文献 (7件)：

• Ando, K., Egawa, Y.: Contractible edges in a 4-connected graph with vertices of degree greater than four. Gr. Combin. 23(Suppl. 1), 99-115 (2007)
• Ando, K., Egawa, Y.: Edges not contained in triangles and the distribution of contractible edges in a 4-connected graph. Discrete Math. 308, 3449-3460 (2008)
• Ando, K., Egawa, Y.: Edges not contained in triangles and the number of contractible edges in a 4-connected graph. Discrete Math. 308, 5463-5472 (2008)
• Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Berlin (2010)
• Egawa, Y., Kotani, K., Nakamura, S.: Structure of edges in a 4-connected graph not contained in triangles and the number of contractible edges. https://doi.org/10.1016/j.akcej.2017.09.002

タイトルに関連する用語 (5件)： 三角 ,  エッジ ,  グラフ ,  縮小 ,  下限