In other words, G is equivalent to the generalized star obtained from G by removing
the edge {i, j} and inserting the edge {i, l}.
Proof: First let G
= π
(i, 0)
(i, 0), (0,l)→(i, l)
(G) so that E(G
)=E(G) ∪{{i, l}} −
{{i, 0}} (notice that G
may not be a generalized star). Now let G
= π
(i, j)
(i, j), (j, 0)→(i, 0)
(G
)
and notice that E(G
)=E(G
)∪{{0,i}}− {{i, j}} =(E(G)∪{{i, l}} − {{i, 0}})∪
{{0,i}} − {{i, j}} = E(G) ∪{{i, l}} − {{i, j}} whichiswhatwewereafter.
Lemma 4.4.7 Suppose we are a generalized star G ∈G(S, k). Enumerate the nodes
of G as 0, 1,...,|S|−1 with 0 denoting a star center. Suppose an edge {i, j}∈E(G)
and {q, l} /∈ E(G) for i, j, q and l>0.ThenG is equivalent via ∼ to the generalized
star G
∈G(S, k) determined by the set of edges E(G
)=E(G)∪{{q, l}} −{{i, j}}.
In other words, G is equivalent to the generalized star obtained from G by removing
the edge {i, j} and inserting the edge {i, l}.
Proof: If q = i the situation is exactly that of lemma 4.4.6 and so we assume that
q = i. In such a case, either one of the following mutually exclusive situations can
occur: either {i, q}∈E(G) or {i, q} /∈ E(G).
Case 1: {i, q}∈E(G). In this case, according to lemma 4.4.6 G ∼ G
with
E(G
)=E(G) ∪{{q, l}} − {{i, q}} and, again thanks to lemma 4.4.6, G
∼ G
with E(G
)=E(G
) ∪{{i, q}} − {{i, j}} =(E(G) ∪{{q, l}} − {{i, q}}) ∪
{{i, q}} − {{i, j}} = E(G) ∪{{q, l}} − {{i, j}}
Case 2: {i, q} /∈ E(G). In this case, according to lemma 4.4.6 G ∼ G
with
E(G
)=E(G) ∪{{i, q}} − {{i, j}} and, again thanks to lemma 4.4.6, G
∼ G
with E(G
)=E(G
) ∪{{q, l}} − {{i, q}} =(E(G) ∪{{i, q}} − {{i, j}}) ∪
{{q, l}} − {{i, q}} = E(G) ∪{{q, l}} − {{i, j}}
Thus, in any of the possible cases we deduce that G ∼ G
with E(G
)=E(G) ∪
{{q, l}} − {{i, j}} so that the desired conclusion follows at once.
Lemma 4.4.7 brings us very close to reaching our final goal. Indeed, let 0, 1,...,|S|−1
enumerate the nodes of a generalized star graph G ∈G(S, k) with 0 denoting the
star center. Notice that G is uniquely determined by the binary sequence of length
(|S|−1)(|S|−2)
2
indexed b y all pairs (i, j) satisfying 1 ≤ i<j≤|S|−1 and having
a 1 in position (i, j) if and only if {i, j}∈E(G). Such a sequence contains exactly
k −|S| +11s and the rest are zeros. Lemma 4.4.7 tells us that transposing a one and
a zero in this sequence results in an equivalent generalized star. It is well known that
every permutation is a product of transpositions and so we d educe
Lemma 4.4.8 Any two generalized stars in G(S, k) h aving a common star center are
equivalent via ∼.
In summary, combining lemmas 4.4.8 with lemma 4.4.5 tells us that any two general-
ized stars are equivalent. Now, given any two graphs G and G
∈G(S, k), according
to lemma 4.4.4, G ∼ G
1
and G
∼ G
2
with G
1
and G
2
being generalized stars and, ac-
cording to the previous sentence, G
1
∼ G
2
so that we finally have G ∼ G
1
∼ G
2
∼ G
so that theorem 4.4.1 now follows.
25 / 26
Del 11.3 Report on hierarchical networks
DBE Project (Contract n° 507953)
