On Orbital Domination Numbers of Graphs

Gary Chartrand1, Michael A.Henning2, Kelly Schultz3
1Western Michigan University
2University of Natal, Pietermaritzburg
3Western Michigan University

Abstract

If the distance between two vertices \(u\) and \(v\) in a graph \(G\) is \(k\), then \(u\) and \(v\) are said to \(k\)-step dominate each other. A set \(S\) of vertices of \(G\) is a \(k\)-step dominating set if every vertex of \(G\) is \(k\)-step dominated by some vertex of \(S\). The minimum cardinality of a \(k\)-step dominating set is the \(k\)-step domination number \(\rho_k(G)\) of \(G\). A sequence \(s: \ell_1, \ell_2, \ldots, \ell_k\) of positive integers is called an orbital dominating sequence for \(G\) if there exist distinct vertices \(v_1, v_2, \ldots, v_k\) of \(G\) such that every vertex of \(G\) is \(\ell_i\)-step dominated by \(v_i\) for some \(i\) (\(1 \leq i \leq k\)). An orbital dominating sequence \(s\) is minimal if no proper subsequence of \(s\) is an orbital dominating sequence for \(G\). The minimum length of a minimal orbital dominating sequence is the orbital domination number \(\gamma_{o}(G)\), while the maximum length of such a sequence is the upper orbital domination number \(\Gamma_{o}(G)\) of \(G\).

It is shown that for every pair \(i, j\) of positive integers with  \(i < j\), there exist graphs \(G\) and \(H\) such that both \(\rho_i(G) – \rho_j(G)\) and \(\rho_j(H) – \rho_i(H)\) are arbitrarily large. Also, there exist graphs \(G\) of arbitrarily large radius such that \(\gamma_{o}(G) < \rho_i(G)\) for every integer \(i\) (\(1 \leq i \leq \text{rad} G\)). All trees \(T\) with \(\gamma_{o}(T) = 3\) are characterized, as are all minimum orbital sequences of length 3 for graphs. All graphs \(G\) with \(\Gamma_{o}(G) = 2\) are characterized, as are all trees \(T\) with \(\Gamma_{o}(T) = 3\).