On Certain Connected Resolving Parameters of Hypercube Networks

Bharati Rajan, Albert William, Indra Rajasingh, S. Prabhu

Department of Mathematics, Loyola College, Chennai, India.

DOI: 10.4236/am.2012.35071                

Abstract

Given a graph , a set is a resolving set if for each pair of distinct vertices there is a vertex such that . A resolving set containing a minimum number of vertices is called a minimum resolving set or a basis for . The cardinality of a minimum resolving set is called the resolving number or dimension of and is denoted by . A resolving set is said to be a star resolving set if it induces a star, and a path resolving set if it induces a path. The minimum cardinality of these sets, denoted respectively by and are called the star resolving number and path resolving number. In this paper we investigate these re-solving parameters for the hypercube networks.

Keywords

Resolving Set; Basis; Path Resolving Set; Star Resolving Set; Hypercube Network

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffman and M. Mihalák, “Network Discovery and Verification,” IEEE Journal on Selected Areas in Communications, Vol. 24, No. 12, 2006, pp. 2168-2181. doi:10.1109/JSAC.2006.884015
[2]	S. Khuller, B. Ragavachari and A. Rosenfield, “Landmarks in Graphs,” Discrete Applied Mathematics, Vol. 70, No. 3, 1996, pp. 217-229. doi:10.1016/0166-218X(95)00106-2
[3]	F. Harary and R. A. Melter, “On the Metric Dimension of a Graph,” Ars Combinatoria, Vol. 2, 1976, pp. 191-195.
[4]	P. J. Slater, “Leaves of Trees,” Congressus Numerantium, Vol. 14, 1975, pp. 549-559.
[5]	P. J. Slater, “Dominating and Reference Sets in a Graph,” Journal of Mathematical and Physical Sciences, Vol. 22, No. 4, 1988, pp. 445-455.
[6]	G. Chartrand, L. Eroh, M. A. Johnson and O. Oellermann, “Resolvability in Graphs and the Metric Dimension of a Graph,” Discrete Applied Mathematics, Vol. 105, No. 1-3, 2000, pp. 99-113. doi:10.1016/S0166-218X(00)00198-0
[7]	M. A. Johnson, “Structure-Activity Maps for Visualizing the Graph Variables Arising in Drug Design,” Journal of Biopharmaceutical Statistics, Vol. 3, No. 2, 1993, pp. 203-236. doi:10.1080/10543409308835060
[8]	M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” Freeman, New York, 1979.
[9]	P. Manuel, M. I. Abd-El-Barr, I. Rajasingh and B. Rajan, “An Efficient Representation of Benes Networks and Its Applications,” Journal of Discrete Algorithms, Vol. 6, No. 1, 2008, pp. 11-19. doi:10.1016/j.jda.2006.08.003
[10]	K. Liu and N. Abu-Ghazaleh, “Virtual Coordinate Backtracking for Void Traversal in Geographic Routing,” 5th International Conference on Ad-Hoc Networks and Wireless, Ottawa, 17-19 August 2006.
[11]	A. Seb? and E. Tannier, “On Metric Generators of Graphs,” Mathematics of Operations Research, Vol. 29, No. 2, 2004, pp. 383-393. doi:10.1287/moor.1030.0070
[12]	S. S?derberg and H. S. Shapiro, “A Combinatory Detection Problem,” American Mathematical Monthly, Vol. 70, No. 10, 1963, pp. 1066-1070. doi:10.2307/2312835
[13]	B. Rajan, I. Rajasingh, J. A. Cynthia and P. Manuel, “On Minimum Metric Dimension,” Proceedings of the Indonesia-Japan Conference on Combinatorial Geometry and Graph Theory, Bandung, 13-16 September 2003.
[14]	P. Manuel, B. Rajan, I. Rajasingh and M. C. Monica, “Landmarks in Torus Networks,” Journal of Discrete Mathematical Sciences & Cryptography, Vol. 9, No. 2, 2006, pp. 263-271.
[15]	P. Manuel, B. Rajan, I. Rajasingh and M. C. Monica, “On Minimum Metric Dimension of Honeycomb Networks,” Journal of Discrete Algorithms, Vol. 6, No. 1, 2008, pp. 20-27. doi:10.1016/j.jda.2006.09.002
[16]	B. Rajan, I. Rajasingh, M. C. Monica and P. Manuel, “Metric Dimension of Enhanced Hypercube Networks,” Journal of Combinatorial Mathematics and Combinatorial Computation, Vol. 67, 2008, pp. 5-15.
[17]	B. Rajan, I. Rajasingh, P. V. Gopal and M. C. Monica, “Minimum Metric Dimension of Illiac Networks,” Ars Combinatoria (accepted for publication).
[18]	V. Saenpholphat and P. Zhang, “Conditional Resolvability of Graphs: A Survey,” International Journal of Mathematics and Mathematical Sciences, Vol. 38, 2003, pp. 1997-2017.
[19]	B. Rajan, S. K. Thomas and M. C. Monica, “Conditional resolvability of Honeycomb and Hexagonal Networks,” Journal of Mathematics in Computer Science, Vol. 5, No. 1, 2011, pp. 89-99. doi:10.1007/s11786-011-0076-3
[20]	H. El-Rewini and M. Abd-El-Barr, “Advanced Computer Architecture and Parallel Processing,” John Wiley & Sons, Inc., Hoboken, 2005.
[21]	J. Xu, “Topological Structures and Analysis of Interconnection Networks,” Kluwer Academic Publishers, Dordrecht, 2001.
[22]	J. Caceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara and D. R. Wood, “On the Metric Dimension of Cartesian Products of Graphs,” SIAM Journal of Discrete Mathematics, Vol. 21, No. 2, 2007, pp. 423441. doi:10.1137/050641867