Universal dominating sequences of graphs
Abstract
Let G be a nontrivial connected graph of order n with V(G) = {v1 , V2 , ... , Vn}. A sequence ki , k2 , ... , kn of positive integers, where 1 ≤ ki, ≤ e(vi) for each integer i with 1 ≤ i ≤ n, is called a universal dominating sequence for G if ∪ni=1 NKi(vi) = V(G). We examine properties of universal sequences and determine special universal sequences for different classes of graphs. We consider the universal sequences for both paths and cycles to illustrate different attributes of universal sequences. We characterize those graphs G for which V(G) = {v1 , v2 , ... , Vn} and Σni=1 |Nki(vi)| is constant for any universal dominating sequence {ki}. A sequence tℓ1 , ℓ2 , ... , ℓt (t ≤ n) of positive integers is called a planetary dominating sequence if 1 ≤ ℓi ≤ e(vi) for each i (1 ≤ i ≤ n) and ∪ti=1 Nℓi,(vi) = V(G). Properties of planetary sequences are studied as well as determining special planetary sequences for paths.
