文献

J-GLOBAL ID：202002218064537599   整理番号：20A0275942

グラフの頂点における連結計量次元【JST・京大機械翻訳】

The connected metric dimension at a vertex of a graph

著者 (3件)： Eroh Linda (University of Wisconsin Oshkosh, Oshkosh, WI 54901, USA) ,  Kang Cong X. (Texas A&M University at Galveston, Galveston, TX 77553, USA) ,  Yi Eunjeong (Texas A&M University at Galveston, Galveston, TX 77553, USA)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 806  ページ： 53-69  発行年： 2020年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： グラフGの計量次元,dim(G),および多くのバリアントの概念は,現在良く研究されている。本論文では,cdimG(v)を導入することによりこの概念の局所解析を始め,頂点vにおけるGの連結計量次元を以下のように定義した。Gの頂点Sの集合は,Gの異なる頂点xとyの任意対に対して,zとxの間の距離がzとyの間の距離と異なるような頂点z∈Sがある。著者らは,SがGの連結部分グラフを誘導するならば,分解集合Sが接続されると言うことである。次に,cdimG(v)は,頂点vを含むすべての連結分解集合の基数の最小値であると定義される。CDIM(G)によって表されるGの接続された計量次元は,min{cdimG(v):V∈V(G)}である。Gの頂点vに対して,1≦dim(G)≦CDIM(G)≦cdimG(v)≦|V(G)|-1であることを示し,cdimG(v)が固定グラフGで変化するとき,dimG(v)はdim(G)から|V(G)|-1まですべての正の整数値をとることを示した。グラフGとそれらの頂点vを満たすcdimG(v)∈{1,|V(G)|-1}を特性化した。CDIM(G)=2はGが平面であることを示したが,dim(H)=2の非平面グラフHが存在することは良く知られている。また,CDIM(G)=dim(G)を満足する木と単環グラフGを特性化した。CDIM(G)-2m(G)は任意に大きいことを示した。グラフのいくつかのクラスに対してCDIM(G)とcdimG(v)を決定した。さらに,結合した計量次元に対する頂点またはエッジ削除の影響を調べた。著者らは,いくつかのオープン問題によって結論したCopyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： キャラクタリゼーション ,  *平面グラフ
準シソーラス用語： 基数 , 【Automatic Indexing@JST】

著者キーワード (4件)： 距離 ,  連結分解集合 ,  連結計量次元 ,  計量次元

分類 (2件)： 図形・画像処理一般  (JE04010I) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (4件)： グラフ ,  頂点 ,  計量 ,  次元