文献

J-GLOBAL ID：201902223701126081   整理番号：19A1667617

表面における(n,k)-拡張可能グラフ

The (n, k)-Extendable Graphs in Surfaces

著者 (3件)： Ma Yushan (School of Mathematics and Statistics, Lanzhou University, Lanzhou, Gansu, People’s Republic of China) ,  Li Qiuli (School of Mathematics and Statistics, Lanzhou University, Lanzhou, Gansu, People’s Republic of China) ,  Zhang Heping (School of Mathematics and Statistics, Lanzhou University, Lanzhou, Gansu, People’s Republic of China)
資料名： Graphs and Combinatorics (Web)  (Graphs and Combinatorics (Web))
巻： 35  号： 4  ページ： 941-957  発行年： 2019年 
JST資料番号： U1590A  ISSN： 0911-0119  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 少なくとも2k+2頂点を持つ連結グラフGは,サイズkのマッチングを持ち,すべてのマッチングがGにおける完全マッチングに拡張できるならば,k-拡張可能と呼ばれる。グラフGは,n頂点の任意の集合Sに対して部分グラフG-Sがk-拡張可能であるならば,(n,k)-グラフである。表面Σに対して,LuとWangは,Σ-埋込み可能なグラフがパラメータnを固定することにより(n,k)-グラフとならないような最小数k=μ(n,Σ)の明快な公式を確立した。本論文において,著者らは他のパラメータkを固定して,Σ-埋込み可能なグラフが(n,k)-グラフとならないように最小数n=ρ(k,Σ)を見出した。この方法により,良く知られたDeanの式(定理1.1)を再現できる。さらに,k≧1,n+2k≧6かつ(n,k)≠(0,3)となる任意の非負整数n,kに対して,Σに埋め込まれた(n,k)-グラフの次数の上限値を見出し,以下の結果を得た:(i)n+2k≦4のとき,そのときにのみ,球(投射平面に対応)に埋め込まれた無限に多くの(n,k)-グラフが存在する;(ii)球面とも射影平面とも位相同型でない各表面Σに対して,n+2k≦5あるいは(n,k)=(0,3)であるとき,そのときに限って,無限に多くのΣに埋め込み可能な(n,k)-グラフが存在する。Copyright 2019 Springer Japan KK, part of Springer Nature Translated from English into Japanese by JST.

シソーラス用語： 表面 ,  *グラフ ,  マッチング ,  *頂点 ,  拡大 ,  理論 ,  パラメータ
準シソーラス用語： グラフ埋込み ,  拡張 ,  *連結グラフ

著者キーワード (5件)： 完全マッチング ,  拡張性のマッチング ,  因子臨界性 ,  [数式:原文を参照]-グラフ ,  表面におけるグラフ

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

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