Open AccessAlgorithm and computer program to determine metric dimension of graph
Author(s) -
Fahad Muhammad,
Liliek Susilowati
Publication year - 2020
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1494/1/012018
Subject(s) - combinatorics , vertex (graph theory) , mathematics , metric dimension , graph , bound graph , connectivity , discrete mathematics , dimension (graph theory) , undirected graph , graph power , line graph , 1 planar graph
Let G be a simple, connected and undirected graph with vertex set V ( G ) and a subset W = { w 1 , w 2 , w 3 , … w t } ⊆ V ( G ) is order set. A representation of vertex v ∈ V ( G ) with respect to W is an ordered t − tuple r ( v | W ) = ( d ( v , w 1 ), d ( v , w 2 ), d ( v , w 3 ), …, d ( v , w t )) where d ( v , w i ) is the distance between vertices v and w i . The set W is called a resolving set for G if every vertex of G has a distinct representation with respect to W . A resolving set containing a minimum number of vertices is called basis for G . The metric dimension of G denoted as dim ( G ), is the number of vertices in a basis of G . In our study, we construct the algorithm to determine the basis and dimension of graph G . The algorithm is checking all possibility combination of vertex set such that the vertex set has the minimal cardinality of resolving set. Furthermore we design the computer program to find the basis and dimension of graph.