Independent Domination In Permutation Graphs

  • J. Chithra Lady Doak College
  • S.P. Subbiah Mannar Thirumalai Naicker College


The permutation graph Gπ is given by (Vπ,Eπ) where π is a permutation on a finite set V={1,2,…,p},Vπ=V and for i,j Î Vπ, (i,j) belongs to Eπ if  i appears after j in its image sequence.  A subset D of V whose closed neighborhood is V in π is a dominating set of π. An algorithm for finding the domination number and strong domination number of a permutation was developed by us earlier. In this paper the procedure to investigate the independent domination number and the strong independent domination number of a permutation is established. The independent domination number and a strong independent domination number of the permutations realizing a path, complete graph, complete bipartite graph, complete tripartite are also found.


[1]     Pnueli, A., Lempel, A., & Even, S. (1971). Transitive orientation of graphs and identification of permutation graphs. Canad. J. math23(1), 160-175.

[2]     Brandstädt, A., & Kratsch, D. (1985, September). On the restriction of some NP-complete graph problems to permutation graphs. In Fundamentals of Computation Theory (pp. 53-62). Springer Berlin Heidelberg.

[3]     Colbourn, C. J., & Stewart, L. K. (1991). Permutation graphs: connected domination and Steiner trees. Annals of Discrete Mathematics48, 179-189.

[4]     Farber, M., & Keil, J. M. (1985). Domination in permutation graphs. Journal of algorithms6(3), 309-321.

[5]     Atallah, M. J., Manacher, G. K., & Urrutia, J. (1988). Finding a minimum independent dominating set in a permutation graph. Discrete Applied Mathematics21(3), 177-183.

[6]     Field, R. H., & Codes, C. Text Books.    

[7]     Kumar, A. A., Athisayanathan, S., & Antonysamy, A. (2010). Algorithm to Find All Cliques in a Graph. International Journal of Advanced Networking and Applications2(02), 597-601.

[8]     Haynes, T. W., Hedetniemi, S., & Slater, P. (1998). Fundamentals of domination in graphs. CRC Press.

[9]     Chithra, J., Subbiah, S. P., & Swaminathan, V. Domination in Permutation Graphs. a a2(1), 1.

Mar 3, 2016
How to Cite
CHITHRA, J.; SUBBIAH, S.P.. Independent Domination In Permutation Graphs. IOSRD International Journal of Applied Mathematics, [S.l.], v. 2, n. 1, mar. 2016. Available at: <>. Date accessed: 20 aug. 2017.