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
PDF HTML
4,544
Downloads
7,214
Views
Citations

Department of Mathematics, Loyola College, Chennai, India.

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.

Share and Cite:

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.

Conflicts of Interest

The authors declare no conflicts of interest.

[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 |

Journals Menu

Copyright © 2021 by authors and Scientific Research Publishing Inc.

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