Share This Article:

On Certain Connected Resolving Parameters of Hypercube Networks

Abstract Full-Text HTML Download Download as PDF (Size:144KB) PP. 473-477
DOI: 10.4236/am.2012.35071    4,109 Downloads   6,736 Views   Citations


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.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

B. Rajan, A. William, I. Rajasingh and S. Prabhu, "On Certain Connected Resolving Parameters of Hypercube Networks," Applied Mathematics, Vol. 3 No. 5, 2012, pp. 473-477. doi: 10.4236/am.2012.35071.


[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

comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.