文献

J-GLOBAL ID：202202290927703639   整理番号：22A0468174

完全解決可能なグラフ

Completeness-Resolvable Graphs

著者 (3件)： Feng Min (School of Mathematics and Statistics, Nanjing University of Science and Technology, Nanjing, China) ,  Ma Xuanlong (School of Science, Xi’an Shiyou University, Xi’an, China) ,  Xu Huiling (School of Mathematics and Statistics, Nanjing University of Science and Technology, Nanjing, China)
資料名： Graphs and Combinatorics (Web)  (Graphs and Combinatorics (Web))
巻： 38  号： 2  ページ： 32  発行年： 2022年 
JST資料番号： U1590A  ISSN： 0911-0119  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 連結グラフG=(V(G),E(G))が与えられたとき,ある頂点uからある頂点vへの最短経路の長さをd(u,v)で表す。V(G)の適切な部分集合Wについて,Wを範囲とするu及びV(G)\Wを範囲とするvとしてのd(u,v)の最大値をm(W)とする。Ψ_W:V(G)\W→[m(W)]^|W|,u→(d(w₁,u),・・・,d(w_|W|,u))が全単射であり,ここにおいてi=1,...,|W|について[m(W)]^|W|={(a₍₁₎,...a_(|W|))|1≦a_(i)≦m(W)}であるならば,適切な部分集合W={w₁,・・・,w_|W|}は完全解決可能集合である。本論文では,まず,与えられた2部グラフでのいくつかの頂点における辺被覆を利用することにより全ての完全解決可能グラフの集合を構成し,次に,スパニング部分グラフの関係によりこの集合のいくつかの部分集合に対して半順序集合を確立する。各半順序集合に基づき,最大グラフを求めさらに最小グラフにおける辺数の下界と上界を与える。さらに,下界または上界を満たす最小グラフの特徴を明らかにする。Copyright The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature 2021 Translated from English into Japanese by JST.

シソーラス用語： *部分集合 ,  部分グラフ ,  *半順序 ,  スパンニング木 ,  端部 ,  写像 ,  *経路 ,  定理証明 ,  直積 ,  限界
準シソーラス用語： スパニングツリー ,  二部グラフ ,  下界 ,  *最短経路 ,  上界 ,  全単射 ,  *頂点被覆 ,  辺 ,  連結グラフ

著者キーワード (5件)： 完全性解決可能 ,  集合の解決 ,  距離 ,  エッジ被覆 ,  二部グラフ

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

タイトルに関連する用語 (1件)： グラフ