On Certain Connected Resolving Parameters of Hypercube Networks

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.

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.

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.

B. Rajan, A. William, I. Rajasingh and S. Prabhu, "On Certain Connected Resolving Parameters of Hypercube Networks,"

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

[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