Gary Chartrand1, Michael A. Henning2, Kelly Schultz 3
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\).

E-mail Alert

Add your e-mail address to receive upcoming issues of Journal of Combinatorial Mathematics and Combinatorial Computing (JCMCC).

Special Issues

The Combinatorial Press Editorial Office routinely extends invitations to scholars for the guest editing of Special Issues, focusing on topics of interest to the scientific community. We actively encourage proposals from our readers and authors, directly submitted to us, encompassing subjects within their respective fields of expertise. The Editorial Team, in conjunction with the Editor-in-Chief, will supervise the appointment of Guest Editors and scrutinize Special Issue proposals to ensure content relevance and appropriateness for the journal. To propose a Special Issue, kindly complete all required information for submission;