Profile numbering

Profile numbering --- профильная нумерация.

For a proper numbering [math]\displaystyle{ f }[/math], the profile width of a vertex [math]\displaystyle{ v }[/math] is defined as

[math]\displaystyle{ w_{f}(v) = f(v) - \min_{x \in N[v]} f(x), }[/math]

where [math]\displaystyle{ N[v] }[/math] is the closed neighborhood of [math]\displaystyle{ v }[/math]. The profile of numbering [math]\displaystyle{ f }[/math] for [math]\displaystyle{ G }[/math] is defined as

[math]\displaystyle{ P_{f}(G) = \sum_{v \in V} w_{f}(v). }[/math]

The profile of [math]\displaystyle{ G }[/math] is the minimum value

[math]\displaystyle{ P(G) = \min_{f}(P_{f}(G)), }[/math]

where [math]\displaystyle{ f }[/math] is taken over all proper numberings of [math]\displaystyle{ G }[/math]. A proper numbering [math]\displaystyle{ f }[/math] that attains the minimum value is called a profile numbering.