O'Reilly logo

Analysis of Complex Networks by Frank Emmert-Streib, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

13.6 Maximal Cubes in Median Graphs of Circular Split Systems

Let S be a nonempty collection of splits (bipartitions of [n]) also called a split system. Graph G(S) has as vertices all sets X that contain exactly one element of each split from S and have the property that every pair of elements from X intersects. Two vertices U and V of G(S) are adjacent if there exist exactly one split S ={A, B} from S such that either AUV or BUV. Barthélemy [14] introduced a similar construction by extending Buneman's construction of trees [24] (from a set of compatible splits). Graph G(S) is always a median graph [14], and it can be easily seen that the isometric embedding into the corresponding hypercube together with the corresponding binary labeling of vertices is already encoded in the definition of vertices of G(S). Moreover, every median graph can be obtained by such a construction (just consider the set of its splits). G(S) is also called a median network or Buneman graph [32, 33, 60]. In [13, 64] the number of vertices of the median graph G(S), where S is the split system of all possible splits of set [n], is calculated for n ≤ 7.

Bandelt and Dress introduced in [9] circular split systems. For n ≥ 3, consider an n-cycle Cn and label its vertices with elements from [n]. For n ≥ 2, the full circular split system S(n) on [n] is defined as follows. The full circular split systemS(2) consists of only one possible split of the set [2]; in other words, S(2) = {{{1},{2}}}. For n

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required