文献

J-GLOBAL ID：201002280753959152   整理番号：10A0578563

グラフの強積の連結性

Connectivity of Strong Products of Graphs

著者 (1件)： SPACAPAN Simon (Univ. Maribor, Maribor, SVN)
資料名： Graphs and Combinatorics  (Graphs and Combinatorics)
巻： 26  号： 3  ページ： 457-467  発行年： 2010年 
JST資料番号： X0108A  ISSN： 0911-0119  CODEN： GRCOE5  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： グラフG=(V₁,E₁)およびH=(V₂,E₂)の強積G<span style=text-decoration:overline>□×</span>Hは,頂点集合V(G<span style=text-decoration:overline>□×</span>H)=V₁×V₂をもつグラフであり,ここでは,i=1,2に対してx_i=y_iあるいはx_iy_i∈E_iであるかその場合に限り2つの個別頂点(x₁,x₂),(y₁,y₂)∈V₁×V₂は,G<span style=text-decoration:overline>□×</span>Hにおける隣接である。強積G<span style=text-decoration:overline>□×</span>HにおけるいわゆるI集合およびL集合を導入し,G<span style=text-decoration:overline>□×</span>Hにおける全ての極小分離集合は,G<span style=text-decoration:overline>□×</span>HにおけるI集合あるいはL集合のいずれかであることを証明した。強積の連結性に対するいくつかの限界および正確な結果は,この特性化から得られた。次にこの結果を,強積における任意数の因子に対して一般化した。(翻訳著者抄録)

シソーラス用語： グラフ ,  *グラフ理論 ,  連結性 ,  頂点 ,  *集合 ,  分離 ,  キャラクタリゼーション ,  因子 ,  *直積
準シソーラス用語： 特性化

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

引用文献 (19件)：

• Balbuena, C., Cera, M., Diánez, A., García-Vázquez, P., Marcote, X.: On the edge-connectivity and restricted edge-connectivity of a product of graphs. Discrete Appl. Math.155, 2444-2455(2007)
• Balbuena, C., Marcote, X., Garcia-Vazquez, P.: On restricted connectivities of permutation graphs. Networks 45, 113-118(2005)
• Bohman, T.: A limit theorem for the Shannon capacities of odd cycles II. Proc. Amer. Math. Soc.133, 537-543(2005)(electronic)
• Brešar, B., Špacapan, S.: Edge connectivity of strong products of graphs. Discuss. Math. Graph Theory 27(2), 333-343(2007)
• Brešar, B., Špacapan, S.: Connectivity of direct products of graphs. Australas. J. Comb.(in press)

タイトルに関連する用語 (3件)： グラフ ,  積 ,  連結性