Level structure

From Wikipedia, the free encyclopedia

 This article does not cite any references or sources. (January 2008)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

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.

[edit] 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

L0(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).