Analysis of Complex Networks

8.2 A Class of Tree-Like Graphs and Some of Its Derivatives

8.2.1 Preliminary Notions

In this section we briefly define two well-known notions that will be used throughout the chapter to introduce our graph model. This relates to paths in undirected and directed graphs as well as to the notion of geodesic distance in weighted graphs.

Definition 8.1 (Preliminaries) Let G = (V, E, L_V, L_E, μ) be a connected weighted undirected graph whose vertices are uniquely labeled by the function L_V : V → L_V for the set of vertex labels L_V and whose edges are uniquely labeled by L_E : E → L_E for the set of edge labels L_E. Throughout this chapter we assume that L_V ⊂ ₀ and L_E⊂ ₀, that is, vertices and edges are labeled by ordinal numbers. Further, we assume that this numbering is consecutive. Next, let D = (V, A, L_V, L_E, ν) be an orientation of G, that is, a connected weighted digraph such that ∀a ∈ A : ν(a) = μ(e) ⇔ e = {in(a), out(a)} ∈ E. By ≤_V⊂L²_v (≤_E⊂L²_E) we denote the natural order of L_V ⊂ ₀ (L_E ⊂ ₀) such that for all a, b ∈ L_V (a, b ∈ L_E): a <_V b (a <_E b) iff a ≤_V b (a ≤_E b) and a ≠ b. This allows ...