Level structure

{{ safesubst:#invoke:Unsubst||$N=Unreferenced |date=__DATE__ |$B= {{#invoke:Message box|ambox}} }} In the mathematical subfield of graph theory a level structure of a graph is a partition of the set of vertices into equivalence classes of vertices with the same distance from a given root vertex.

Definition

Given a connected graph G=(V,E) with V the set of vertices and E the set of edges with

$\epsilon :V\to \mathbb {N}$

the eccentricity of a vertex, for a given vertex v

The partition

$V=\bigcup _{i=0}^{\epsilon (v)}L_{i}(v)=V$

with

$L_{0}(v):={v}$

$L_{i}(v):=\mathrm {Adj} (L_{i-1}(x))\setminus \bigcup _{j=0}^{i-1}L_{j}(x)\qquad {\mbox{ , }}i=1,2,\ldots \epsilon (v)$

is called a level structure of G with root v and depth ε(v).