文献

J-GLOBAL ID：201802266489853306   整理番号：18A0329315

距離正則グラフにおけるマッチングの最大カットと拡張可能性【Powered by NICT】

Max-cut and extendability of matchings in distance-regular graphs

著者 (3件)： Cioaba Sebastian M. (Department of Mathematical Sciences, University of Delaware, Newark, DE 19716-2553, USA) ,  Koolen Jack (Wu Wen-Tsun Key Laboratory of Mathematics of CAS, School of Mathematical Sciences, University of Science and Technology of China, 96 Jinzhai Road, Hefei, 230026, Anhui, PR China) ,  Li Weiqiang (Department of Mathematical Sciences, University of Delaware, Newark, DE 19716-2553, USA)
資料名： European Journal of Combinatorics  (European Journal of Combinatorics)
巻： 62  ページ： 232-244  発行年： 2017年 
JST資料番号： A1229A  ISSN： 0195-6698  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 完全マッチング,t<v/2を含んでいても,次の連結グラフGは,t-は拡張可能と呼ばれtエッジのマッチングは,いくつかの完全マッチングに含まれている。Gがt-拡張可能であるようなGの拡張性は最大tである。1980年代のPlummerによるその導入以来,この組合せパラメータは多くのクラスの興味深いグラフ研究されてきた。2005年,BrouwerとHaemersは偶数位数の全ての距離正則グラフである1-拡張可能な2014例,CioabaとLiは偶数次のどのような連結強正則グラフは,少数の例外を除いて3拡張可能であることを示したことを証明した。本論文では,これらの結果を拡張し,一般化した。直径D≧3のすべての距離正則グラフは2拡張可能であり,ここではまた,k,λとμに依存することを原子価K≧3の距離正則グラフの拡張性のためのいくつかのより良い下界を得る,λは二隣接頂点の共通近傍の数であり,μは距離二の二頂点の共通近傍の数であることを証明した。多くの状況では,原子価Kの距離正則グラフの拡張性はKで直線的に成長することを示した。偶数次数と原子価Kの距離正則グラフの拡張性は,少なくとも[k/2] 1であり,二部距離正則グラフのためのこの事実を証明することを予想した。本研究の過程で,著者らは最大カットのためのいくつかの新しい限界とそれらのサイズと奇ガースの距離正則グラフの独立数を得て,筆者らは筆者らの不等式はこれらの組合せのパラメータについて既知の固有値限界と比較できないことを証明した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 偶数 ,  不等式 ,  *グラフ ,  *マッチング ,  固有値 ,  リチウム ,  原子価
準シソーラス用語： 次数 ,  近傍 ,  下界 ,  位数 ,  連結グラフ ,  *正則グラフ , 【Automatic Indexing@JST】

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

タイトルに関連する用語 (4件)： 正則グラフ ,  マッチング ,  拡張 ,  可能性