On the Metric Dimension of Biregular Graph

情報処理学会

この論文をさがす

説明

The metric dimension of a connected graph G is the minimum number of vertices in a subset W of V(G) such that all other vertices are uniquely determined by its vector distance to the vertices in W. In this paper, we consider a connected graph G where every vertex of G has relatively same probability to resolve some distinct vertices in G, namely a (μ, σ)-regular graph. We give tight lower and upper bounds on the metric dimension of a connected (μ, σ)-regular graphs of order n ≥ 2 where 1 ≤ µ ≤ n-1 and σ=n-1. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.25(2017) (online) DOI　http://dx.doi.org/10.2197/ipsjjip.25.634 ------------------------------

The metric dimension of a connected graph G is the minimum number of vertices in a subset W of V(G) such that all other vertices are uniquely determined by its vector distance to the vertices in W. In this paper, we consider a connected graph G where every vertex of G has relatively same probability to resolve some distinct vertices in G, namely a (μ, σ)-regular graph. We give tight lower and upper bounds on the metric dimension of a connected (μ, σ)-regular graphs of order n ≥ 2 where 1 ≤ µ ≤ n-1 and σ=n-1. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.25(2017) (online) DOI　http://dx.doi.org/10.2197/ipsjjip.25.634 ------------------------------

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ