文献

J-GLOBAL ID：201802250448923136   整理番号：18A0328359

グラフの完全マッチングの極値非強制数【Powered by NICT】

Extremal anti-forcing numbers of perfect matchings of graphs

著者 (3件)： Deng Kai (School of Mathematics and Statistics, Lanzhou University, Lanzhou, Gansu 730000, PR China) ,  Deng Kai (School of Mathematics and Information Science, Beifang University of Nationalities, Yinchuan, Ningxia 750027, PR China) ,  Zhang Heping (School of Mathematics and Statistics, Lanzhou University, Lanzhou, Gansu 730000, PR China)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 224  ページ： 69-79  発行年： 2017年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： グラフGの完全マッチングMの非強制数は,その除去により得られたグラフのユニークな完全マッチングとしてのMにMではなくエッジの最小数である。Gの全ての完全マッチングの非強制数の集合とは,Gの非強制スペクトルである。本論文では,最小アンチ強制数が1である平面初等的二部グラフを特性化した。グラフの最大非強制数は最大でそのサイクル数であることを示した。特に,最大非強制数上限を達成しグラフを特徴付け,そのような極値グラフを平面二部グラフのクラスである。最後に,線形時間でも多角形鎖の非強制スペクトルを決定した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： スペクトル ,  *グラフ ,  線形性 ,  キャラクタリゼーション ,  *マッチング
準シソーラス用語： 二部グラフ , 【Automatic Indexing@JST】

著者キーワード (6件)： 完全マッチング ,  初等二部グラフ ,  サイクロマティック数 ,  抗強制数 ,  抗強制スペクトル ,  偶数多角形鎖

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

タイトルに関連する用語 (4件)： グラフ ,  マッチング ,  極値 ,  強制