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 ﬁnal 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 ﬁnally 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)