CHARACTERIZATION OF GRAPH WITH METRIC DIMENSION TWO
Let ????=(????(????),????(????)) be a graph and ????={????1,????2,…,????????} be an ordered set, with ?????????(????),??????. For every ?????????(????), the metric representation of ???? with respect to ???? is defined by ????-vector ????(????|????)=(????(????,????1),????(????,????2),…,????(????,???...
Saved in:
| Main Author: | |
|---|---|
| Format: | Final Project |
| Language: | Indonesia |
| Online Access: | https://digilib.itb.ac.id/gdl/view/42431 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Institut Teknologi Bandung |
| Language: | Indonesia |
| Summary: | Let ????=(????(????),????(????)) be a graph and ????={????1,????2,…,????????} be an ordered set, with ?????????(????),??????. For every ?????????(????), the metric representation of ???? with respect to ???? is defined by ????-vector ????(????|????)=(????(????,????1),????(????,????2),…,????(????,????????)). The set ???? is a resolving set of ???? if for all ????,?????????(????) with ????????? implies that ????(????|????)?????(????|????). The set ???? with minimum cardinality is called a basis, noted by ????(????). And the cardinality of ????(????) is called metric dimension of graph ????, noted by ????????????(????).
Let ???? be a simple graph with vertex set ????(????) and ???? be a vertex in ????. Then, {????0,????1,…,????????} is called a distance partition of ????(????) with reference to the vertex ???? if ????0={????} and ???????? contains vertices which are at distance ???? from ????, for 0<?????????, where ???? is the eccentricity of ???? in graph ????.
In this final project, we construct an exhaust4e algorithm and implement the algorithm in MATLAB to search for all undirected, unweighted graphs on ???? vertices with 3??????8, that have metric dimension two. |
|---|