IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 49 (2011), 1166
ISSN 2232-2094
HAMMING DIMENSION OF A GRAPH - THE CASE OF
sierpiNski graphs
Sandi Klavžar Iztok Peterin Sara Sabrina Zemljic
Ljubljana, December 6, 2011
Hamming dimension of a graph - the case of Sierpinski
graphs
$H
Sandi Klavžar*
Faculty of Mathematics and Physics, University of Ljubljana Jadranska 19, 1000 Ljubljana, Slovenia and
Faculty of Natural Sciences and Mathematics, University of Maribor Koroska 160, 2000 Maribor, Slovenia sandi.klavzar@fmf.uni-b.si
vO
Iztok Peterin*
Faculty of Electrical Engineering and Computer Science University of Maribor, Smetanova ulica 17, 2000 Maribor ižtok.peterin@uni-mb.si
Sara Sabrina Žemljic Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia sara.zemljic@gmail. com
vO
tí
O
CM
I
CM
Abstract
00 CM CM
The Hamming dimension of a graph G is introduced as the largest dimension of a Hamming graph into which G embeds as an irredundant induced subgraph. An upper bound is proved for the Hamming dimension of Sierpinski graphs S?, k > 3. The Hamming dimension of S? grows as 3n-3. Several explicit embeddings are constructed along the way, in particular into products of generalized Sierpihski triangle graphs. The canonical isometric representation of Sierpihski graphs is also explicitly described.
Keywords: Hamming graphs; Hamming dimension; Sierpinski graphs; Cartesian product of graphs; induced embeddings; isometric embeddings
AMS Subj. Class. (2010): 05C60, 05C76, 05C78
* This work has been financed by ARRS Slovenia under the grant P1-0297 and within the EURO-m	CORES Programme EUROGIGA/GReGAS of the European Science Foundation. The author is also
with the Institute of Mathematics, Physics and Mechanics, Ljubljana.
1
U
a
CD U
CD
vO vO
1 Introduction
Several graph dimensions based on embeddings into product graphs have been studied by now. The isometric dimension of G is the largest number of factors of a Cartesian product graph, such that G is an irredundant, isometric subgraph of the product [6]. The strong isometric dimension is defined analogously, except that one embeds into the strong product of paths [3, 4], while the lattice dimension is defined via embeddings into Cartesian products of paths [2, 13]. The lattice dimension of a graph G is finite if and only if G is isometrically embeddable into some hypercube. For additional related dimensions see [8, Section 15.3].
In this paper we introduce the Hamming dimension Hdim(G) of a graph G as the largest dimension of a Hamming graph into which G embeds as an irredundant induced subgraph. Clearly, Hdim(G) = 1 if and only if G is a complete graph. Moreover, Hdim(G) < to if and only if G admits a certain edge labeling, see Theorem 3.1 below. Note that K4 — e is the smallest graph with Hdim(K4 — e) = to. The general problem of determining the Hamming dimension of a graph seems very demanding, here we will study this concept on Sierpinski graphs.
Sierpinski graphs S^ were introduced and studied for the first time in [15]. The study was motivated in part by the fact that for k = 3 these graphs are isomorphic to the Tower of Hanoi graphs [9] and in part by topological studies. For details about the latter motivation see Lipscomb's book [20]. Sierpinski graphs were later independently introduced in [23].
The graphs S^ were investigated from numerous points of view, we recall some of them. These graphs contain (essentially) unique 1-perfect codes [16], a classification of their covering codes is given in [5]. In [7] a shorter proof is given for the uniqueness CM of 1-perfect codes and their optimal L(2,1)-labelings are presented. Equitable L(2,1)-labelings were later studied in [1]. The crossing number of Sierpinski graphs and their natural regularizations was studied in [17], giving first infinite families of graphs of fractal nature for which the crossing number was determined (up to the crossing number of complete graphs). Metric properties of Sierpinski graphs were investigated in [12, 21]. To determine the chromatic number of these graphs is easy, while in [11] it is proved that they are in edge- and total coloring class 1, except those isomorphic to a complete graph of odd or even order, respectively. Recently, the hub number of Sierpinski graphs was determined in [19].
As already said, Sierpinski graphs are closely related to the Tower of Hanoi. In [24], Romik used the Sierpinski labeling of S^ to construct an appealing finite automaton that solves the decision problem of whether the largest disc moves once or twice on a shortest path from a regular to another regular configuration in the Tower of Hanoi problem. For connections between the Sierpinski graphs SJ (alias Hanoi graphs) and the Stern's diatomic sequence see [10].
We proceed as follows. In the rest of this section we give necessary definitions. In the next section Sierpinski graphs and generalized Sierpinski triangle graphs are introduced
£ CO CO
CD
u
CD
m
u
a
CD U
CD
vo vO
and some of their properties recalled. Then, in Section 3, the theory from [18] on induced embeddings into Hamming graphs and more generally, into Cartesian product graphs, is recalled. It is applied to describe induced embeddings of Sierpinski graphs into Cartesian products of generalized Sierpinski triangle graphs. In Section 4 it is proved that for any n > 2,
7	3 9
Hdim(S,3) > - • 3ra-3 + 3 • 2ra-4 + —n — — .
4 24
In the subsequent section an upper bound for Hdim(Sn), k > 3. Together with the lower bound it implies that Hdim(S™) asymptotically grows as 3n-3. As proved in [6], an irredundant isometric embedding into the largest number of factors is unique and called the canonical isometric representation. In the last section we explicitly describe this embedding of Sn.
The Cartesian product G □ H of graphs G and H is the graph with the vertex set V(G) x V(H), where the vertex (g,h) is adjacent to the vertex (g', h') whenever gg' € E(G) and h = h', or g = g' and hhh € E(H). The Cartesian product is commutative and associative, products whose all factors are complete are called Hamming graphs. The dimension of a Hamming graph is the number of its factors, that is, the number of coordinates of its vertices. We say that a graph G is an irredundant subgraph of □ f=1Gj if each Gj has at least two vertices and any vertex of Gj appears as a coordinate of some vertex of G. With these concepts we can thus state:
Hdim(G) = max{p | G is irredundant induced subgraph of □ P=1KPi} .
The distance d(u,v) = dG(u, v) between vertices u and v of a graph G is the length of a shortest u, v-path in G. A subgraph H of a graph G is isometric if for each pair of vertices u, v of H there exists a shortest u, v-path in G that lies entirely in H. Finally, by a labeled graph we mean a graph together with a labeling of its edges.
CO
2 Sierpinski graphs
The Sierpinski graph S^, k,n > 1, is defined on the vertex set {1,..., k}n, two different CO vertices u = (u1,..., un) and v = (v1,..., vn) being adjacent if and only if there exists an h € {1,..., n} such that
(i)	ut = vt, for t = 1,..., h - 1;
(ii)	uh = vh; and
(iii)	ut = vh and vt = uh for t = h + 1,..., n.
In the rest we will use abbreviation (u1u2 ... un) for (u1 ,u2,... ,un). On figures, this will be further simplified to u1u2 ... un. The Sierpinski graph S4 together with the corresponding vertex labeling is shown on Fig. 1.
A vertex of the form (ii... i) of Sn is called an extreme vertex. Note that Sn contains k extreme vertices and that |V(Sn)| = kn. Let n
Jh
3
U
a
CD U
vo
$H
CD
CD O CD
VO VD
0
tí ^
&
O
CM
1
CM CO CM CM
£ CO CO
m
CD
$H
CD
m
2223 2233 2323 2333 3222 3232 3322 3332 2232 2322 2332	3223 3233 3323
Figure 1: The Sierpinski graph S4
the subgraph of S'n induced by the vertices of the form (iv2 ... vn). More generally, for given ii,...,ir € {1,...,k}, we denote with i\... ir
by the vertices of the form (il... irvr+l... vn). Note that iSn-1 is isomorphic to Sn^, and, more generally, il... irS'n-r is isomorphic to Sn-r.
An edge of Sn of the form (ulu2 ... un-li)(ulu2 ... un-lj), i = j, will be called a clique edge. A clique edge is contained in a unique subgraph Kk of S^. The other edges will be called non-clique edges. Let i = j. Then the edge (ijj ... j)(jii... i) is the unique edge between iSn- and jS^n-1. It will be denoted with ej = ej™ Consider the subgraph il... ir Sl-r of Sn. Then the edge between (il... ir j£.. .£) and (il... ir £j .. .j) will be denoted il... ir ejn-r).
U
a
CD U
Setting
p.. = J 1 i = j pij = \ 0 i = j
CM vD
u
a
CD U
the following holds:
Lemma 2.1 [15] Let (uiu2 .. .un) and (ii... i) be vertices of S^- Then
U
dsn? ((ui U2 ...Un), (ii... i)) = pultipu2,i ■ ■ ■ Pun,i ,
where the right-hand side is a binary number with digits puj >i. Moreover, a shortest path between (uiu2 ... un) and (ii... i) is unique.
o
The unique path in Sn between (ii... i) and (jj .. .j) will be denoted pjn). Similarly, in the subgraph ii... ir Sn-r, there is a unique path between (ii... ir jj .. .j) and (ii... irii.. .i), it will be denoted ii... irBy the uniqueness of the shortest paths between extreme vertices, it follows that there is also a unique shortest cycle of Sn containing the edges ej1'', e^, and e^, where i,j,i € {1,2,...,k} are pairwise
different. This cycle will be denoted Cj'.
One of our embeddings will be an embedding into the Cartesian product of generalized Sierpinski triangle graphs, a class of graphs introduced in [14] as 2-parametric Sierpinski gasket graphs. For n > 1 and k > 3, the generalized Sierpinski triangle graph Sn is the graph obtained from Sn by contracting all non-clique edges of Sn. Note that
Sfc = (k > 3). For S"2 see Fig. 2, where {i,j} denotes the vertex obtained by contracting the edge (ij)(ji).
CM
3 Embeddings into products of generalized Sierpinski triangle graphs
CM
In this section we first summarize the theory developed in [18] about induced embeddings of graphs into Hamming graphs.
CO
Let G be a connected graph and let F = {Fi, F2,..., Fp} be a partition of E(G). CO Such a partition yields the corresponding labeling i : E(G) ^ {1, 2,... ,p} by setting i(e) = i for e € Fi. For our purpose, the following conditions of a labeling are crucial:
Condition A. Let G be a labeled graph. Then edges of a triangle have the same label.
Condition B. Let G be a labeled graph and let u and v be arbitrary vertices of G with dG(u,v) > 2. Then there exist different labels i and j which both appear on any induced u, v-path.
CO
Now we can recall:
CD
5
{1, 2}
vo
$H
CD
CD O CD
VD VD
{1, 3}
{2, 3}
0 o
CM
1
CM CO CM CM
£ CO CO
CO CD
$H
CD CO
Figure 2: The generalized Sierpinski triangle graph
Theorem 3.1 [18] Let G be a connected graph. Then Hdim(G) < to if and only if there exists a labeling of G that fulfills Conditions A and B.
The proof of Theorem 3.1 is constructive in the following way. If G is an induced subgraph of a Hamming graph with p factors, then the labeling of G that respects the projection of the edge uses p labels and satisfies Conditions A and B. Conversely, let F = {Fi,..., Fp} be a partition of E(G) such that the corresponding labeling £ fulfills Conditions A and B. For every i = 1,... ,p, define the graph G/Fj whose vertices are the connected components of G \ Fj, two components C and C' being adjacent in G/Fj whenever there exists an edge of Fj connecting a vertex of C with a vertex of C. Let fi : V(G) ^ V(G/Fj) be the natural projection, that is, u € V(G) is mapped to the component of G \ Fj to which it belongs. Then
f = (fi,..., fp) : G ^ G/Fi □ ... □ G/Fp
(1)
is an induced embedding of G. Moreover, by adding edges to each factor G/Fi to make it complete, the embedding f is still induced. It follows that f can be considered as an induced embedding of G into a Hamming graph. In addition, f is an irredundant embedding meaning that each G/Fi has at least two vertices and each vertex of it appears as a coordinate in some image of a vertex of G. (To obtain an induced embedding of G into a Cartesian product (of factors that are not necessarily complete), Condition B must be modified, see [22].)
U
a
CD U
We will make use of the following additional properties of a labeling that fulfills Condition B, see [18, Lemmas 3.1 and 3.2]:
(i)	in an induced cycle of length > 3, every label must appear at least twice, and
(ii)	if every induced path between two vertices contains labels i and j, then every path between these two vertices contains these two labels.
vO
In addition, it is easy to see that if a maximal part of an induced cycle C is labeled alternatively with i and j, then i and j must also exist on the other part of C. In particular, if we have the sequence iji on C, then i appears at least once more on C.
o
CD
We now turn our attention to Sierpinski graphs. Every S? can be embedded in a CD Hamming graph with two factors as follows. Label the clique and the non-clique edges of S? with labels p and q, respectively. Call this labeling a p\r-labeling. Clearly, a p\r-labeling fulfills Condition A. Moreover, since no two non-clique edges are incident, Condition B holds as well.
Let k > 3. Then the Sierpinski triangle labeling of S? is inductively defined as follows. Label the edges of Sk = Kk with label 1. Suppose now S?, n > 1, has already been labeled. Then label every subgraph iS? (1 < i < k) of S?+1 identically as S? and label the edges e(™+1) with label n + 1. Clearly, the Sierpinski triangle labeling of S? uses n labels. Note also that the Sierpinski triangle labeling of S| coincides with its 1\2-labeling.
o

Theorem 3.2 Let k > 3 and n > 1. Then the Sierpinski triangle labeling of S? yields an induced embedding
5	S? ^ sj?□ sk-1 □ ... □ si.
Proof. Let k > 3 be a fixed integer. The Sierpinski triangle labeling clearly fulfills Condition A. Let u, v be two non-adjacent vertices of S?. Consider a shortest path P between u and v and let i be the largest label on P. Then i > 1 and every induced CM path between u and v contains labels 1 and i. Hence Condition B is fulfilled and thus the embedding (1) can be used.
Let Fi, 1 < i < n, be the set of edges of S? labeled with n — i + 1 in the Sierpinski triangle labeling of S?. We are going to prove that for any n > 1 and for any 1 < i < n,
Sfc/F = Si.
—
Let n = 1. Then S^ = Kk and all of its edges are labeled with 1. Hence S^ = Kk = S1/F1. Suppose Theorem 3.2 holds for some n > 1 and consider S^1. Since
Fi = (ej1^ \ i = j} we infer that S^/F = Kk = Let next i > 2. Then every edge of Fi lies in some subgraph jS?. Let jF be the restriction of Fi to jS? and note that jFi coincides with the labeling as Fi_1 in S?. Hence, by the induction hypothesis,
it follows that jS?/jFi = Sk-1. But then S^+VF = Sik by the way the generalized Sierpinski triangle graphs are constructed.	□
7
U
a
CD U
CD
4 A lower bound on Hdim(Sn)
In this section we prove: Theorem 4.1 For any n > 2,
7	3 9
Hdim(S£) > - • 3ra"3 + 3 • 2ra"4 + ^n - - .
4	2	4
CD
To prove the theorem we construct a merging labeling of S3, n > 2, as follows. For n = 2, label every edge of ¿S3 with i and for any j = k, label the edge ej2 with i, where {i, j, k} = {1,2,3}. Proceed by induction on n as follows. Label every iS3-1 with the same pattern as S3-1, but such that iS3-1 and jS3-1 use pairwise different
labels for any i = j. In addition, label the edges e^, e^, and e^ with the same
labels as 3e12-1), 1e2™-1), and 2e1™-1), respectively. Note that this labeling does not fulfill Condition B since some labels appears only once at C^.
We thus need to merge every label that appears only once on 1P2(3 1), only once on 2P1(r1), and only once on 3P1(3>-1) with the exception of the edges 1e2™-1), 2e1g-1), and 3e12-1), respectively. The merging is done as follows. Consider the following pairs of oriented subpaths of eg: 12P2(r2), 32P2(r2); 13P2(3n-2), 23P1(3n-2); and 31P&-2), 21P;n-2). Here oriented means that each of these paths has it start and its end, for instance, 12P2( 33""2) starts in (122... 2) and ends in (1233... 3). Now traverse 12P2(3-2) and 32P2(n"-2) in parallel. As soon as a label is found on 12P2(3>-2) that appears only once on 1P2(3i-1), merge it with the corresponding label of 32P2(n"-2). (Note that also CM appears only once on 3P2(3-1) by the construction.) More precisely, we replace every label in S3 with Do the same procedure for the other two pairs of paths. An example of a merging labeling of S| is shown in Fig. 3.
CM
Proposition 4.2 A merging labeling of S3, n > 2, fulfills Conditions A and B.
Proof. Edges that form a triangle are labeled with the same label, hence Condition A is fulfilled. Note also that Condition B is fulfilled on S2. Let now n > 2 and let u, v CO be vertices of S3 with d(u, v) > 2. Let p be the smallest in the sense that both u and v are in i1i2 ... ipS3-p. Then p < n — 1 since d(u, v) > 2. Let u € i1i2 ... ipj1S3>-p-1, v € i1i2 .. .iPj2S3-p-1, and let j j'2, j3} = {1, 2, 3}.
Let P be a shortest u, v-path. Suppose first that P contains the edges i1i2 ... ipejl-
and i1 i2 ... ipej3.-p). Then the labels of these two edges are on any induced u, v-path by the way the merging labeling is constructed. In the other case, P contains a unique edge of the form e = i1i2 ... ipe(:r!1-pP, namely the edge i1i2 ... ipej™:-p). By the same argument its label appears on every induced u, v-path. Since d(u, v) > 2, the edge e has at least one incident edge on P, say f. We may assume without loss of generality that f €
Jh
8
U
a
CD U
1—1		/TV
	3/	
1—1		
0	A	
CM		A
	3f\	
vD		
u
CD
a
CD O CD
Q
vD vO
0 ^
&
O
CM
1
CM CO CM CM
£ CO CO
m
CD
$H
CD
m
SA 71^	y8V y^ ¿S4V ¿10Y ¿S6V --"14 2b	2b LU 27	27
Figure 3: A merging labeling of
i1 ■ ■■ipj2Sn p ^ Then the label of f appears also on the triangle of ■ ■■ipjs S' p 1 that is incident with the edge i1 i2 ... ipej'"^- Again by the construction, the label of f appears on any induced u, v-path.	□
Lemma 4.3 Let n — 2, be labeled with a merging labeling. Then every label of a non-clique edge of , i,j € {1,2,3}, besides e(n, appears exactly twice on pi'3.
(n)
Proof. There is nothing to be proved for n = 2. We can restrict to P2g by symmetry. Note that the labels of the edges 2e2'-1) and 3e2'-1) are merged in and have thus
U
a
CD U
CM
r
vO
CD O
the same label. Hence every label of a non-clique edge of Pj"^, i, j € {1,2,3}, besides
ej, appears at least twice on P-j3 by induction.
It remains to prove that no non-clique edge appears more than twice. This clearly holds for n = 3,4, cf. Fig. 3. Let now n > 5. Note first that the assertion holds for the label of 2e23 ^ and 3e23 1. Indeed, their labels were unique on
2P2(3n-1) and
3P2(n-1), respectively and were henceforth merged in the last step of the construction. The label of the edges 22e2'3_2) and 23e2'3_2) (which is the same) appears only once on 2P1(r1) and
is also merged in S™. But this label appears on 23Pi3-2) and is merged with a label from 13P2(3 1). In other words, this label does not appear in 3S3-1 and consequently not on 3P2(3 1). By symmetry, the assertion also holds for the label of the edges 32e2'3_2) and 33e2'3_2) .
Next we show that the label t of non-clique edges 222e2'3_3) and 223e2'3_3) appears twice on
2P1(r1) and is not merged in S3. Clearly t appears once on 223P1(33-3) (on the edge incident with (22311... 1)) and was in 2SJ-1 merged with the label of the edge on 213P2(3"3) incident with (21322... 2). This label is in 21S3-2 present also on the edges 211e(j'3_3) and 213e(j'3_3), which are both on 2P1(3i_1).
Similarly, the label tt of the edges 232e2'3_3) and 233e2'3_3) appears twice on 2P1(3>-1) and is not merged in S3. Clearly tt appear once on 2P13 1) since it is in the triangle of the extreme vertex (23311 . . . 1) in
233S3"3. But tt is also in the triangle of the extreme vertex (23211... 1) in 232S3-3. Hence it was merged in 2S3-1 with the label of the triangle of the extreme vertex (21333... 3) in 212S3-3. But this was again merged in 21S3-2 with the label of the triangle of the extreme vertex (21133... 3), which lie on
2P1(n-1)
vO
O
1
13
(n) in Q C3-1
Next we calculate the number of labels of a merging labeling of S3. Let bn be the
The conclusion also holds for the labels of P23 in 3S3- that are symmetric to the edges in previous two paragraphs.
Finally, for all the other non-clique edges of P2(J) the statement follows by induction.
□
number of labels different from 1 that appear on P2g exactly once. In other words, b3 is the number of labels of 1S™ that will be merged with some other label in S3+1. (Clearly label 1 will not be merged.) Hence
bn = 2bn-1 2cn ,
where c3 represents the number of labels that appear twice on P2(3) for the first time. To determine cn, Lemma 4.3 implies that we only need to find clique edges whose labels appear twice on P2(3) for the first time and, moreover, one edge must be in 2S3-1 and the second one in
way merging is defined this can happen if the first
Jh
10
u
a
CD U
edge is in 223Sn-3 and its label appears on both 22P2(3 2) and 22Pl(3i 2) exactly once. The label of such an edge is then merged with the label of some edge in 213Sn-3 that again appears on 21P2(3 2) and 21Pln 2) exactly once. The edge on 21Pl(3i 2) is then on eg and its label is merged with the label of an edge in 312Sn-3 that appears on 31Pln 2) and 31P2(n 2) exactly once by symmetry. Finally this was merged with a label in 332Sn-3 that again appears only once on 33Pl2n 2) and 33P2(n 2). Loking to Fig. 3 we infer that that c4 = 1 (label 9) and c5 = 1 (label 17).
Hence we need to treat clique edges on 223P2(i"-3) . For this sake we define even and odd clique edges of P^ as follows. Let T:,T2,...,T2n-1 be the consecutive triangles
with edges in P2(3n). (On Fig. 3, triangle Tl is labeled with 13, and Tl6 with 22.) Then
/ \
we say that a clique edge e € P23 is even/odd if e € T and i is even/odd. Note that the label of an odd clique edge from 223P2(n-3) appears twice on 22Pl(3i-2). Hence it appears twice on 2Cln-l) and is not merged at this step. So we only need to consider even clique edges from 223P2(n-3). We will show by induction that cn = n — 4 for n > 5. Note that for n = 5 there is only one such label, namely label 17 on Fig. 3. For S^, n > 5, every even clique edge of 2233P2(i"-4) has this property as well as the even clique edge of T3.2n-5. Hence cn = n — 4 for n > 5. Returning back to bn we now have:
vO vO
bn = 2bn-l — 2(n — 4), b5 = 10,
which solves to
bn = 2n-3 + 2n — 4, n > 5 .
CM
Note that this formula holds also for n = 4.
Let finally an, n > 4, be the number of labels in a merging labeling of Sn. Then
CO
33 an = 3a,„_i - -bn-1 = 3a,„_i - -(2ra_4 + 2n - 6), a4 = 12
since we merge six parts into three by pairs. The theorem now easily follows. (We need to check n = 2,3 separately.)
CO
l-H
5 An upper bound on Hdim(Sn)
In this section we prove an upper bound on the Hamming dimension of Sn for k > 3. We first establish some exact values.
Proposition 5.1 (i) Hdim(Sf) = 3, Hdim(Sf) = 6.
(ii) For any k > 4, Hdim(S|) = 2.
CD
11
U
a
CD U
CO CD
Proof. (i) By Theorem 4.1, Hdim(Sf) > 3. That Hdim(Sf) < 3 follows by the fact that on the cycle C(23 of S2 each label appears at least twice. Note that the merging labeling is the unique 3-labeling of S2 that satisfies Conditions A and B. CM	Using Theorem 4.1 again we have Hdim(S3) > 6. Since C(23 has length 12 (and
every label of an induced cycle must appear at least twice on it), there can be at most 6 different labels on C(23. If for {i,j,£} = {1,2,3} every £Pi(2) contains three labels in £S2, then each £S2 contains the same three labels as £Pi(2) (because the merging labeling is the unique appropriate 3-labeling of S2). Such a labeling thus uses at most 6 different labels. Similarly, if some £Pi(2) contains only two different labels we infer that only these two labels can be used on £S2.
(ii) Let k > 4. We claim that the 1|2-labeling of S2 yields a unique induced embedding of S2 into a Hamming graph and hence Hdim(S2) = 2.
Since S2 is not a complete graph we need at least two labels. By Condition A, all edges of iS^, i = 1,2,..., k, must receive the same label. By Condition B, every edge
ej, j = i, must have different label from the labels of iS^ and jS^. If all iS^ have
(2)
the same label, then the non-clique edges of any cycle Cpq'r must have the same label, for otherwise one label appears only once on Cp^. Since p, q, and r are arbitrary we obtain the 1|2-labeling.
Suppose next that two of iS^, i = 1,2,...,k, are labeled with 1 and among the others at least one with 2. We may choose the notation so that 1S^ and 2S^ have label
1 and 3Si label 2. Then by Condition B, edges e^, e^, and e^ cannot have label 1,
(2) (2) (2) moreover e 3 and e23 cannot have label 2 by the same condition. But then e 2 must
(2)
have label 2, for otherwise we have the same contradiction as above in C123. Consider now vertices (13) and (23) to find the final contradiction with Condition B. CM	Assume finally that all the iSk1, i = 1, 2, . . . , k, have different labels, say iSk1 has
(2) (2) (2) label i. To satisfy Condition B, the edge e12 of C123 must have label 3, e13 label 2,
(2) (2) (2) and e23 label 1. By the same argument applied on C124, the edge ei2 must have label
4, a final contradiction.	□
CO
We are now ready for the main result of this section. Theorem 5.2
(i) Hdim(S^) < 5 ■ 3n-3 + 1 (n > 3).
2	2k — 4
(») Hdim(SE) <	+	(„> 2).
Proof. Labels that appear in more than one iS^"-1 will be called common labels.
For a fixed k and n > 3, consider a labeling of that fulfills Conditions A and B and uses Hdim(Sn) labels. This labeling has at most Hdim(S^-1) different labels in
CD
12
U
a
CD U
each subgraph iSn 1 (because iS^ 1 is isomorphic to S^ 1). In addition, by Condition B, there must be at least two labels in each iSn-1 that appear also in Sn\iSn-1. Hence we get
Hdim(Sn) > k(Hdim(Sn-1) - 2) + an ,
vO

vD
o
csr
i
where an denotes the maximum number of common labels. Setting
an = k(an-1 - 2) + a„
we thus have Hdim(Sn) < an.
Consider iSn 1 and C j. For the closest vertices of e j and e(n on Cj we observe
that by Condition B we need (at least) two labels of iS^-1 on the other part of Cjj>. Hence for every i = 1,2,..., k there are at most an-1 — 2 labels that appear only in iSn-1. First we assume that the maximum number of labels is attained when we have an-1 — 2 different labels in every iSn-1. Even more, these two labels cannot be on e j or e^, since otherwise we can include these two edges and consider the other two
vertices of ej and e(n. Thus we have 6 positions on cj for new labels in iS^ 1, jSn-1, and £S£-1, and additional 3 edges ej^, e(n and ejn>—all together 9 positions. By the above argument, each	may contain more
than one edge but all such edges can be viewed just as one. But then in Cj we may have at most 4 = |_|J common labels.
Suppose now that we can use 5 common labels. First we consider a longer path Pijg between (i££... •) and ... •) in Cj for every i, j, and If every Cj contains at most two common labels, Pj clearly contains both labels. But then Pj> = Pj for every r / {i, j,^} and every Cjr contains these two labels. This is a contradiction since we have used 5 common labels. Next suppose that every Cj contains at most 3 common labels. If P^j contains only two of these labels, then both Pj and Pjfi contain all three. Again Pj> = Pj for every r / {i, j,^} and every Cjr contains these three labels—a contradiction. Next suppose that Cj contains four common labels. If Pji contains only three common labels, we have only 4 positions in Cj — Pj and one label, say 4 is present only on Cj — P^. By the above, both e^ and ejn> must have
CO
label 4. The label of e(™>, say 3, must be in •Sn 1 together with a common label 2. Label 2 must also be in one of iS^-1 or jS^-1. We may assume that it is in iSn-1 (together with label 1). Hence Pjj contains four common labels. If label 5 exists in rSn-1, r / {i,j,^}, then C^ contains 5 common labels which is not possible. Hence let ePn>> have label 5. If p € {i,^} (or by symmetry r € {i,^}) then C^ (or ) contains 5 common labels again. If finally p, r / {i, j, •£}, either epn > or e^> have label 5 which is not possible. Thus an < 4, hence
m
an = k(an-1 - 2) +4 ,a3 = 4.
$H
13
U
a
CD U
By Proposition 5.1, the initial conditions for k = 3 and k > 4 are Hdim(Sf) = 6 and Hdim(S|) = 2, respectively. Solving the recurrence yields the result.	□
Corollary 5.3 For any k > 4, Hdim(Sf ) = 4.
Proof. By Theorem 5.2, Hdim(S|) < 4. A 4-labeling of that satisfies Conditions A and B can be constructed as follows. Use the 112-, 2|3-, 3|4-, and 4|1-labelings on 1S|, 2S|, 3S|, and 4S|, respectively. Label the edges e, e^, e^l, and ell with 4, 1, 2, and 3, respectively. Next, we may choose labels 2 or 4 for the edge e^ and labels 1 or 3 for the edge e^'. Finally, for every i € {5, 6,... ,k} use the 1|3-labeling on iS|,
o
£ CO CO
(3)	(3)	(3)	(3)	(3)
label edges ei/ and e\2 with 4, edges e\3 and ei4 with 2, and all the other edges ej ,
j € {5,6,..., k}, i = j, with 2. For this labeling, Condition A clearly holds. Moreover,
(3)
a straightforward checking on cycles Cpqr shows that Condition B is fulfilled for it as well.	□
vO
Note that in Theorem 5.2 the equality holds for and S|, k > 4. The upper bound (ii) is also exact for S44. Indeed, the bound is 12, and on the other hand, two d Afferent appropnate labeling* of ^ are show„ ta Fig. 5.
a
6 Isometric embedding
In this final section we consider isometric embeddings of SJ? into Cartesian product graphs. In this case the classical theory due to Graham and Winkler asserts that there
CM
is a unique such embedding that is irredundant and has the largest number of factors. The embedding is described in many papers and books, see for instance [8], and is called the canonical isometric representation. We recall that it is defined just as the embedding f was introduced in Section 3 where the partition of the edge set of G is done with respect to the transitive closure 0* of the relation 0. Here edges e = xy and f = uv of G are in relation 0 if d(x, u) + d(y, v) = d(x, v) + d(y, u). The canonical isometric representation is trivial if G contains only one 0* class.
It is easy to see that no two edges of a geodesic are in relation 0, a fact that will be used later. We will also need the following well-known lemma, cf. [8]:
Lemma 6.1 Suppose P is a walk connecting the endpoints of an edge e. Then P contains an edge f = e with eOf.
Now we have:
Proposition 6.2 Let k > 4. Then for any n > 1 the canonical isometric representation of Sjn is trivial.
■ 1
14
U
a
CD U
vo
Jh
CD
CD O CD
VD vD
0 Ö
o
CM
1
CM CO CM CM
£ CO CO
CO CD
Jh
CD CO
10(5)	11(3)	5(7)
Figure 4: Two labelings of £|
Proof. For a given k > 4 we proceed by induction on n. Graph S1 is isomorphic to Ki, hence the assertion clearly holds in this case. Let n > 1. Then for i = 1,... ,k, the subgraph iSjj-1 contains a single 6*-class by the induction assumption. For i = 3,4,..., k, let C^ be a shortest cycle containing the edges e^, e1i), and e[>i). Then Lemma 6.1 implies that C(2i contains an edge f with f ©e^. Moreover, f can only lie in iSj-1. Hence the edges of iSj-1, i > 3, all lie in the same ©*-class. By the
symmetry of Sk?, the canonical isometric representation of S? is then trivial.
□
By Proposition 6.2 we may hope for a nontrivial isometric representation of S^ only
U
a
CD U
o fi

when k = 3. This is indeed the case as the main result (Theorem 6.5) of this section asserts. We need some preparation for it.
o	( ,
Proposition 6.3 Let n > 1 and let F be a 0*-class of . Then |pjj n F| > 1 i = j •
vO
Proof. The statement is clearly true for n = 1. Let n > 1 and let F be an arbitrary 6*-class of Sn. If |FniSn-11 > 1, then by the induction hypothesis (applied to ¿Si-1), F intersects shortest paths ¿Pjn-1), ¿Pf™-^, and ¿pj^-1) for {¿,j, = {1,2,3}. Let e be in ¿pjn-1) n F. If the antipodal edge of e on C(n3 is ejn>, we are done since ejn> is
(n> '	(n)	(n-1)	(n-1)
on Pj /. Otherwise, the antipodal edge of e on C123 is either on jP^ or ¿Pj- . CD Induction completes the proof.	□
It is well-known (and easy to prove) that edges from different blocks of a graph are not in relation 6 and hence also not in relation 6*. For our purposes we need the following modification of this fact.
Lemma 6.4 Let H be isometric subgraph of G and let e and f be edges from different blocks of H. Then e is not in relation 6 with f in G.
Proof. Let e = uv and f = xy. By the above fact, e and f are not in relation 0 in H, that is,
du(u, x) + du(v, y) = du(u, y) + du(v, x). Since H is an isometric subgraph of G, it follows that
CM
dG(u, x) + dG(v, y) = dG(u, y) + dG(v, x),
00
Note that we cannot conclude in Lemma 6.4 that e and f are not in relation 0* in G. For instance, consider P3 as a subgraph of K2 ,3. Then it is isometric in K2 ,3 yet its edges are in relation 0*.
To describe 0*-classes of SJ, let {i, j, k} = {1,2,3} and set
hence e and f are not in relation 0 in G.	□
Fn = {(in>(in-1 j>, (in)(in-1k)} u {ejk | ^ = 1,2,..., n} .
Note that F| = n + 2.
Now we cab state the main result of this section:
Theorem 6.5 Let n > 2. Then the 0*-classes of SJ are Fl, , F,3, and Fn E(Sn) \ (F,1 u Fra2 U Fra3).
Jh
a
CD U
o
u
a
CD U
vo
$H
CD
CD O CD
Figure 5: The factor graph S4/F4
o	_
Proof. It is straightforward to check the result for n = 2, where F3 = 0 so that in this case we have three 0*-classes.
Let i € {1, 2, 3} and consider F3. By induction assumption (and the fact that iSJ-1 is an isometric subgraph of S3), we infer that (i3)(i3-1 j), (i3)(i3-1k) € F^, as well as
HZ. ZT^ -fV\Y» 0 - 1 0	ly-t _ 1 1\ /T/~\TV~WVI rnr -fln/^ /^r! rrr, /o(3)
ejk € F^ for t = 1,2,..., n — 1. Moreover, the edge ejfc belongs to F,i because it is the antipodal edge of e(k-1) on C(23. (Recall that C(23 is the shortest cycle containing the edges e^, e2™), and e3l).) Hence the edges of F^ belong to a common 0*-class. It remains to show that (i) no two edges from different sets F^, F^, F3, and F3 are in relation 0 and that (ii) in F3 any two edges are in relation 0*.
For assertion (i), by symmetry it suffices to prove that no edge of F^ is in relation 0 with any other edge. Moreover, denoting with G2 and G3 the connected components of S3 \ F^, where (23) € G2, it suffices (using symmetry again) to prove that no edge of F^ is in relation 0 with an edge of G2.
Note first that G2 is isometric in S3. Moreover, the graph induced with V(G2) and vertices (13) and (13-13) is also isometric in S3. Then Lemma 6.4 implies that none of the edges (13)(13-12), (13)(13-13), and (13-12)(13-13) is in relation 0 with no edge in G2. Let t € {0,... ,n — 2} and consider the subgraph of S3 induced by G2 and (1323). We infer again that this subgraph is isometric, hence applying Lemma 6.4 we conclude that (13-12)(13-13) is in relation 0 with no edge of G2. This proves (i).
It remains to prove that any two edges of F3 are in relation 0*. If n = 3, it is
vo
Jh
CD
straightforward to check that (112)(121)B(322)(321)B(122)(123). By symmetry and
(n)
transitivity the result follows. Let n > 4. Then because Cl23 is isometric,
(12n-i )(12n 3)8(321n-2 )(321n 2)
as well as
(12n-2 3)(12n-3 32)8(321n-3 2)(321n-4 21)
n-3c
i n-4i
Now apply induction, symmetry, and transitive closure to conclude that Fn is indeed a 8*-class.	□
CD O CD
References
vO vO
0 Ö
o
CM
1
CM CO CM CM
£ CO CO
CO CD
$H
CD CO
[1]	L. Beaudou, S. Gravier, S. Klavzar, M. Kovse, M. Mollard, Covering codes in Sierpiäski graphs, Discrete Math. Theoret. Comput. Sci. 12 (2010) 63-74.
[2]	D. Eppstein, The lattice dimension of a graph, European J. Combin. 26 (2005) 585-592.
[3]	S. L. Fitzpatrick, R. J. Nowakowski, The strong isometric dimension of finite reflexive graphs, Discuss. Math. Graph Theory 20 (2000) 23-38.
[4]	D. Froncek, J. Jerebic, S. KlavZar, P. Kovär, Strong isometric dimension, biclique coverings, and Sperner's Theorem, Comb. Prob. Comp. 16 (2007) 271-275.
[5]	H.-Y. Fu, D. Xie, Equitable L(2,1)-labelings of Sierpiäski graphs, Australas. J. Combin 46 (2010) 147-156.
[6]	R. L. Graham, P. M. Winkler, On isometric embeddings of graphs, Trans. Amer. Math. Soc. 288 (1985) 527-536.
[7]	S. Gravier, S. KlavZar, M. Mollard, Codes and L(2,1)-labelings in Sierpiäski graphs, Taiwanese J. Math. 9 (2005) 671-681.
[8]	R. Hammack, W. Imrich, S. KlavZar, Handbook of Product Graphs, Second Edition, CRC Press, Boca Raton, FL, 2011.
[9]	A. M. Hinz, The Tower of Hanoi, Enseign. Math. (2) 35 (1989) 289-321.
[10]	A. Hinz, S. KlavZar, U. Milutinovic, D. Parisse and C. Petr, Metric properties of the Tower of Hanoi graphs and Stern's diatomic sequence, European J. Combin. 26 (2005) 693-708.
[11]	A. M. Hinz, D. Parisse, Coloring Hanoi and Sierpiäski graphs, Discrete Math., in press: doi:10.1016/j.disc.2011.08.019.
U
a
CD U
o
CM VD
$H
CD
CD O CD
VO vD
0 ^
&
O
CM
1
CM CO CM CM
£ CO CO
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20] [21] [22]
[23]
[24]
A. M. Hinz, D. Parisse, The average eccentricity of Sierpinski graphs, Graphs Combin., in press: doi: 10.1007/s00373-011-1076-4.
W. Imrich, M. Kovse, Lattice embeddings of trees, European J. Combin. 30 (2009) 1142-1148.
M. Jakovac, A 2-parametric generalization of Sierpinski gasket graphs, Ars Com-bin., to appear.
S. KlavZar, U. Milutinovic, Graphs and a variant of the Tower of Hanoi problem, Czechoslovak Math. J. 47(122) (1997) 95-104.
S. KlavZar, U. Milutinovic, C. Petr, 1-perfect codes in Sierpinski graphs, Bull. Austral. Math. Soc. 66 (2002) 369-384.
S. KlavZar, B. Mohar, Crossing numbers of Sierpinski-like graphs, J. Graph Theory 50 (2005) 186-198.
S. KlavZar, I. Peterin, Characterizing subgraphs of Hamming graphs, J. Graph Theory 49 (2005) 302-312.
C.-H.	Lin, J.-J. Liu, Y.-L. Wang, W. C.-K. Yen, The hub number of Sierpinski-like graphs, Theory Comput. Syst. 49 (2011) 588-600.
S. Lipscomb, Fractals and Universal Spaces in Dimension Theory, Springer, Berlin, 2009.
D.	Parisse, On some metric properties of the Sierpinski graphs Ars Combin. 90 (2009) 145-160.
I. Peterin, Characterizing flag graphs and induced subgraphs of Cartesian product graphs, Order 21 (2004) 283-292.
T. Pisanski, T. W. Tucker, Growth in repeated truncations of maps, Atti Sem. Mat. Fis. Univ. Modena 49 (2001) 167-176.
D. Romik, Shortest paths in the Tower of Hanoi graph and finite automata, SIAM J. Discrete Math. 20 (2006) 610-622.
m
CD
$H
CD
m
u
a
CD U