Irregular orbital domination in graphs

Abstract

For a non-negative integer r, the r-orbit $O_r(v)$ of a vertex v in a connected graph G of order n is the set of vertices at distance r from v. A sequence $s:r_1,r_2,\dots ,r_k$ of positive integers with $1\le k\le n$ is called an irregular orbital dominating sequence of G if $r_i\ne r_j$ for every pair i, j of integers with $1\le i<j\le k$ and G contains distinct vertices $v_1,v_2,\dots ,v_k$ such that $\bigcup _{i=1}^k{O}_{r_i}(v_i)=V(G).$ We investigate graphs that possess and graphs do not possess an irregular orbital dominating sequence. It is shown that a non-trivial tree has an irregular orbital dominating sequence if and only if it is neither a star, a path of order 2, nor a path of order 6.

Keywords:

• Distance
• domination
• vertex orbits
• irregular orbital sequence

AMS Subject Classifications:

• 05C05
• 05C12
• 05C15
• 05C69

Acknowledgements

We thank the anonymous referees whose valuable suggestions resulted in an improved paper.

Disclosure statement

No potential conflict of interest was reported by the author(s).