Algorithms to determine an independent dominating set of \(ESC (n, k)\)

S. Pious Missier; A. Anto Kinsley; Evangeline Prathibha Fernando

doi:10.26637/mjm204/003

Abstract

The independent dominating set is an interesting property used in the allocation of finite resources in a massively parallel network such as the extended star graph with cross-connections (\(ESC\)). In this paper, we have initially designed algorithms to compute the independent dominating set of \(ESC (n, k)\) for \( n = 2\) and \(n = 3\). Using the hierarchical nature of the \(ESC\) with its basic building block \(ESC (n, 1)\) we have designed a generalized algorithm to compute the independent dominating set of \(ESC (n, k\)) for all \(n\) and \(k\).

Keywords:

Dominating set, Graph Theory

Mathematics Subject Classification:

05C10

Authors Imprint References Funding Related Articles Downloads

S. Pious Missier PG and Research Department of Mathematics, V. O. Chidambaram College, Thoothukudi-628008, Tamil Nadu, India.
A. Anto Kinsley PG and Research Department of Mathematics, St. Xavier’s College, Palayamkottai-627001, Tamil Nadu, India.
Evangeline Prathibha Fernando PG and Research Department of Mathematics, V. O. Chidambaram College, Thoothukudi-628008, Tamil Nadu, India.

Pages: 352-362
Date Published: 01-10-2014
Vol. 2 No. 04 (2014): Malaya Journal of Matematik (MJM)

A. Anto Kinsley, S. Soma Sundaram and C. Xavier, Fault Tolerant Hierarchical Network of Star Graphs, Computer Science and Informatics, Vol. 29, No. 1, March 1999, 16 - 21.

S. Arumugam and R. Kala, Domination Parameters of Hypercubes, Journal of the Indian Mathematical Society, Vol. 65, Nos. 1- 4 (1998), 31-38.

S. Arumugam and R. Kala, Domination Parameters of Star graph, Ars Combinatoria 44(1996), 93-96.

K. Day and A. Tripathi, A Comparative Study of Topological Properties of Hypercubes and Star Graphs, IEEE Transactions on parallel and distribution systems 5(1), (1994), 31-38. DOI: https://doi.org/10.1109/71.262586

Teresa W. Haynes, Stephen T. Hedetniemi, Peter J. Slater , Fundamentals of Domination in Graphs, Marcel Dekker Inc., 1998.