Span-labeling

Материал из WikiGrapp
Версия от 17:56, 23 июня 2011; Glk (обсуждение | вклад) (Новая страница: «'''Span-labeling''' --- Span-разметка. An <math>L(j,k)</math>-labeling of a graph <math>G</math>, where <math>j \geq k</math>, is defined as a function <ma…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Span-labeling --- Span-разметка.

An [math]\displaystyle{ L(j,k) }[/math]-labeling of a graph [math]\displaystyle{ G }[/math], where [math]\displaystyle{ j \geq k }[/math], is defined as a function [math]\displaystyle{ f: V(G) \rightarrow Z^{+} \cup \{0\} }[/math] such that if [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] are adjacent vertices in [math]\displaystyle{ G }[/math], then [math]\displaystyle{ |f(u) - f(v)| \geq j }[/math], while if [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] are vertices such that [math]\displaystyle{ d(u,v) = 2 }[/math], then [math]\displaystyle{ |f(u) - f(v)| \geq k }[/math]. The largest label used by [math]\displaystyle{ f }[/math] is the span of [math]\displaystyle{ f }[/math], denoted [math]\displaystyle{ span(f) }[/math]. The smallest span among all [math]\displaystyle{ L(j,k) }[/math]-labelings of [math]\displaystyle{ G }[/math], denoted [math]\displaystyle{ \lambda_{j,k}(G) }[/math], is called the span of [math]\displaystyle{ G }[/math]. An [math]\displaystyle{ L(j,k) }[/math]-labeling of [math]\displaystyle{ G }[/math] that has a span of [math]\displaystyle{ \lambda_{j,k}(G) }[/math] is called a span-labeling of [math]\displaystyle{ G }[/math].