Research ArticleOpen AccessGoogle Scholar indexed
On Certain Connected Resolving Parameters of Hypercube Networks
Department of Mathematics, Loyola College, Chennai, India
Department of Mathematics, Loyola College, Chennai, India
Department of Mathematics, Loyola College, Chennai, India
Department of Mathematics, Loyola College, Chennai, India
- 1 Department of Mathematics, Loyola College, Chennai, India
- 2 Department of Mathematics, Loyola College, Chennai, India
- 3 Department of Mathematics, Loyola College, Chennai, India
- 4 Department of Mathematics, Loyola College, Chennai, India
Copy link · social · email
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.
KeywordsResolving SetBasisPath Resolving SetStar Resolving SetHypercube Network
- 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
- 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
- F. Harary and R. A. Melter, “On the Metric Dimension of a Graph,” Ars Combinatoria, Vol. 2, 1976, pp. 191-195.
- P. J. Slater, “Leaves of Trees,” Congressus Numerantium, Vol. 14, 1975, pp. 549-559.
- P. J. Slater, “Dominating and Reference Sets in a Graph,” Journal of Mathematical and Physical Sciences, Vol. 22, No. 4, 1988, pp. 445-455.
- 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
- 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
- M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” Freeman, New York, 1979.
- 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
- 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.
- 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
- 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
- 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.
- 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.