Irregularity of a digraph

Материал из WikiGrapp
Перейти к навигации Перейти к поиску

Irregularity of a digraph --- нерегулярность орграфа.

An irregularity of a digraph [math]\displaystyle{ D }[/math] is defined as [math]\displaystyle{ i(D) = \max |d^{+}(x) - d^{-}(y)| }[/math] over all vertices [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] of [math]\displaystyle{ D }[/math] (possibly [math]\displaystyle{ x = y }[/math]). There are two other measures of regularity, namely, the local irregularity of a digraph [math]\displaystyle{ D }[/math], which is [math]\displaystyle{ i_{l}(D) = \max |d^{+}(x) - d^{-}(x)| }[/math] over all vertices [math]\displaystyle{ x }[/math] of [math]\displaystyle{ D }[/math] and global irregularity of [math]\displaystyle{ D }[/math], which is [math]\displaystyle{ i_{g}(D) = \max \{d^{+}(x), d^{-}(x) : x \in V(D)\} - \min \{d^{+}(y), d^{-}(y) ; y \in V(D)\} }[/math]. Clearly, [math]\displaystyle{ i_{g}(D) \geq i(D) \geq i_{l}(D). }[/math]