IJPAM: Volume 112, No. 1 (2017)

Title

2-METRIC DIMENSION OF
CARTESIAN PRODUCT OF GRAPHS

Authors

K.N. Geetha$^1$, B. Sooryanarayana$^2$
$^1$Department of Mathematics
Amrita Vishwa Vidyapeetham
Amrita School of Engineering
Bangalore, Karnataka State, INDIA
$^2$Deptartment of Mathematical and Computational Studies
Dr. Ambedkar Institute of Technology
Bangalore, Karnataka State, INDIA

Abstract

Let $G(V,E)$ be a connected graph. A subset $S$ of $V$ is said to be 2-resolving set of $G$, if for every pair of distinct vertices $u,v\notin S$, there exists a vertex $w\in S$ such that $\vert d(u,w)-d(v,w)\vert\geq 2$. Among all $2$-resolving sets of $G$, the set having minimum cardinality is called a 2-metric basis of $G$ and its cardinality is called the 2-metric dimension of $G$ and is denoted by $\beta_k(G)$. In this paper, we determine the 2-metric dimension of cartesian product of complete graph with some standard graphs. Further, we have determined the 2-metric dimension of the graphs $P_m \Box P_n$, $C_m \Box P_n$ and $C_m \Box C_n$.

History

Received: Februray 2, 2016
Revised: November 22, 2016
Published: January 26, 2017

AMS Classification, Key Words

AMS Subject Classification: 05C12
Key Words and Phrases: cartesian product, 2-metric basis, 2-metric dimension

Download Section

Download paper from here.
You will need Adobe Acrobat reader. For more information and free download of the reader, see the Adobe Acrobat website.

Bibliography

1
F. Harary, Graph Theory, Narosa Publishing House, New Delhi, India (1969).

2
Douglas B. West, Introduction to Graph Theory, 2-nd edition, Prentice-Hall of India Pvt. Ltd., New Delhi, India (2001).

3
B. Shanmukha, B. Sooryanarayana and K.S. Harinath, Metricdimension of Wheels, Far. East. J. Appl. Math., 8, No. 3 (2002), 217-229.

4
B. Sooryanarayana, On the metric dimension of graph, Indian Journal of Pure and Appl. Math., 29, No. 4 (1998), 413-415.

5
B. Sooryanarayana and B. Shanmukha, A note on metric dimension, Far. East. J. Appl. Math., 5, No. 3 (2001), 331-339.

6
Gary Chartrand, Linda Eroh, Mark A. Johnson, Orturd R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Applied Mathematics, 105 (2000), 99-113.

7
F. Harary, R.A. Melter, On the metric dimension of a graph, Ars. Combinatoria, 2 (1976), 191-195.

8
B. Sooryanarayana and Geetha K N, On the k-metric dimension in graphs, Journal of Mathematical and Computational Sciences, 5 (2014), 861-878.

9
K.N. Geetha, Invariants in Graphs and their Nice Properties, Ph.D. Thesis, Visvesvaraya Technological University, Belgaum, Karnataka, India (2014).

10
Jose Caceres, Carmen Hernando, Merce Mora, Ignacio M. Pelayo, Maria L. Puertas, Carlos Seara, David R. Wood, On metric dimension of cartesian products of graphs, SIAM Journal of Discrete Mathematics, 2 (2007), 423-441.

11
Samir Khuller, Balaji Raghavachari, Azriel Rosenfeld, Landmarks in graphs, Discrete Applied Mathematics, 70 (1996), 217-229.

12
P.J.Slater, Leaves of trees, Congr. Numer., 14 (1975), 549-559.

13
B. Sooryanarayana, K. Sreedhar, N. Narahari, $k$-metric dimension of a graph, International Journal of Mathematical Combinatorics, 4 (2016), To Appear.

How to Cite?

DOI: 10.12732/ijpam.v112i1.2 How to cite this paper?

Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2017
Volume: 112
Issue: 1
Pages: 27 - 45


Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).