{"title":"Graphs with Metric Dimension Two-A Characterization","authors":"Sudhakara G, Hemanth Kumar A.R","volume":36,"journal":"International Journal of Mathematical and Computational Sciences","pagesStart":1128,"pagesEnd":1134,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/13897","abstract":"

In this paper, we define distance partition of vertex set of a graph G with reference to a vertex in it and with the help of the same, a graph with metric dimension two (i.e. β (G) = 2 ) is characterized. In the process, we develop a polynomial time algorithm that verifies if the metric dimension of a given graph G is two. The same algorithm explores all metric bases of graph G whenever β (G) = 2 . We also find a bound for cardinality of any distance partite set with reference to a given vertex, when ever β (G) = 2 . Also, in a graph G with β (G) = 2 , a bound for cardinality of any distance partite set as well as a bound for number of vertices in any sub graph H of G is obtained in terms of diam H .<\/p>\r\n","references":" Buckley F and Harary F, Distance in graphs, Addison - Wesley (1990).\r\n Christopher Poisson and Ping Zhang. The metric dimension of unicyclic\r\ngraphs. J.Combin. Math. Combin. Comput., 40:17-32, 2002.\r\n F. Harary, Graph theory, Narosa\/Addison Wesley (1969).\r\n Harary F and Melter R.A, On the metric dimension of a graph, Ars\r\nCombinatoria2 (1976), 191-195.\r\n Hartsfield Gerhard, Ringel, Pearls in Graph Theory, Academic press,\r\nUSA (1994).\r\n Jos\u2500\u00f2 C\u251c\u00edceres, Carmen Hernando, Mer\u0107e Mora, Ignacio M. Pelayo, Mar\u251c\u00bca.\r\nPuertas, Carlos Seara and David R. Wood, On the metric dimension of\r\nCartesian product of graphs, arXiv: math.CO\/0507527 v3 2 Mar 2006.\r\n Paul F. Tsuchiya, The landmark hierarchy; A new hierarchy for routing\r\nin very Large networks, ACM 0-89791-279-9\/88\/008\/0035, 1988, page\r\n35-42.\r\n Samir Khuller, Balaji Raghavachari, and Azriel Rosenfeld. Landmarks\r\nin graphs. Discrete Appl. Math., 70(3):217-229, 1996.\r\n Shanmukha B, Certain applications of number theory in graphs with\r\nemphases to networks. PhD. Thesis, 2003.\r\n Shanmukha B, Sooryanarayana B and Harinath K.S, Metric dimension\r\nof Wheels, FEJ. Appl. Math., 8(3)(2002), 217-229.\r\n Sooryanarayana B and Shanmukha B, A note on metric dimension, FEJ.\r\nAppl. Math., 5(3),(2001), 331-339.\r\n Sooryanarayana B, Certain combinatorial connections between groups,\r\ngraphs and surfaces, PhD Thesis, 1998.\r\n Sooryanarayana B, On the metric dimension of a graph, Indian. J. Pure\r\nAppl. Math 29(4),(1998), 413 - 415 (2).\r\n Sooryanarayana B, K.S. Harinath and R.Murali, Some results on metric\r\ndimension of graph of diameter two,( communicated).","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 36, 2009"}