Information Security and Cryptography Research Group

Domination Search on Graphs with Low Dominating-Target-Number

Divesh Aggarwal, Shashank Mehta, and Jitender Deogun

Graph-Theoretic Concepts in Computer Science, WG 2005, Lecture Notes in Computer Science, Springer, vol. 3787, pp. 28-37, Jun 2005.

We settle two conjectures on domination-search, a game proposed by Fomin [1], one in affirmative and the other in negative. The two results presented here are (1) domination search number can be greater than domination-target number, (2) domination search number for asteroidal-triple-free graphs is at most 2.

BibTeX Citation

    author       = {Divesh Aggarwal and Shashank Mehta and Jitender Deogun},
    title        = {Domination Search on Graphs with Low Dominating-Target-Number},
    editor       = {Dieter Kratsch},
    booktitle    = {Graph-Theoretic Concepts in Computer Science, WG 2005},
    pages        = {28-37},
    series       = {Lecture Notes in Computer Science},
    volume       = {3787},
    year         = {2005},
    month        = {6},
    publisher    = {Springer},

Files and Links