Hamming dimension of a graph - the case of Sierpiński graphs - PDF

Description
Hamming dimension of a graph - the case of Sierpińsi graphs Sandi Klavžar Faculty of Mathematics and Physics, University of Ljubljana Jadransa 19, 1000 Ljubljana, Slovenia and Faculty of Natural Sciences

Please download to get full document.

View again

of 19
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

Engineering

Publish on:

Views: 18 | Pages: 19

Extension: PDF | Download: 0

Share
Transcript
Hamming dimension of a graph - the case of Sierpińsi graphs Sandi Klavžar Faculty of Mathematics and Physics, University of Ljubljana Jadransa 19, 1000 Ljubljana, Slovenia and Faculty of Natural Sciences and Mathematics, University of Maribor Koroša 160, 2000 Maribor, Slovenia Izto Peterin Faculty of Electrical Engineering and Computer Science University of Maribor, Smetanova ulica 17, 2000 Maribor Sara Sabrina Zemljič Institute of Mathematics, Physics and Mechanics Jadransa 19, 1000 Ljubljana, Slovenia Abstract 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 Sierpińsi graphs S n, 3. The Hamming dimension of S n 3 grows as 3n 3. Several explicit embeddings are constructed along the way, in particular into products of generalized Sierpińsi triangle graphs. The canonical isometric representation of Sierpińsi graphs is also explicitly described. Keywords: Hamming graphs; Hamming dimension; Sierpińsi graphs; Cartesian product of graphs; induced embeddings; isometric embeddings AMS Subj. Class. (2010): 05C60, 05C76, 05C78 This wor has been financed by ARRS Slovenia under the grant P and within the EURO- CORES Programme EUROGIGA/GReGAS of the European Science Foundation. The author is also with the Institute of Mathematics, Physics and Mechanics, Ljubljana. 1 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) if and only if G admits a certain edge labeling, see Theorem 3.1 below. Note that K 4 e is the smallest graph with Hdim(K 4 e) =. The general problem of determining the Hamming dimension of a graph seems very demanding, here we will study this concept on Sierpińsi graphs. Sierpińsi graphs S n were introduced and studied for the first time in [15]. The study was motivated in part by the fact that for = 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 boo [20]. Sierpińsi graphs were later independently introduced in [23]. The graphs S n 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 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 Sierpińsi 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 Sierpińsi 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 Sierpińsi graphs was determined in [19]. As already said, Sierpińsi graphs are closely related to the Tower of Hanoi. In [24], Romi used the Sierpińsi labeling of S3 n 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 Sierpińsi graphs S3 n (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 Sierpińsi graphs and generalized Sierpińsi triangle graphs are introduced 2 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 Sierpińsi graphs into Cartesian products of generalized Sierpińsi triangle graphs. In Section 4 it is proved that for any n 2, Hdim(S n 3 ) 7 4 3n n n 9 4. In the subsequent section an upper bound for Hdim(S n ), 3. Together with the lower bound it implies that Hdim(S3 n) 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 S n. The Cartesian product G H of graphs G and H is the graph with the vertex set V (G) 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 hh 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 p i=1 G i if each G i has at least two vertices and any vertex of G i 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 i=1 K p i }. The distance d(u,v) = d G (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. 2 Sierpińsi graphs The Sierpińsi graph S n,,n 1, is defined on the vertex set {1,...,}n, two different vertices u = (u 1,...,u n ) and v = (v 1,...,v n ) being adjacent if and only if there exists an h {1,...,n} such that (i) u t = v t, for t = 1,...,h 1; (ii) u h v h ; and (iii) u t = v h and v t = u h for t = h + 1,...,n. In the rest we will use abbreviation u 1 u 2...u n for (u 1,u 2,...,u n ). On figures, this will be further simplified to u 1 u 2...u n. The Sierpińsi graph S3 4 together with the corresponding vertex labeling is shown on Fig. 1. A vertex of the form ii... i of S n is called an extreme vertex. Note that Sn contains extreme vertices and that V (S n) = n. Let n 2, then for i = 1,...,, let is n 1 be 3 Figure 1: The Sierpińsi graph S 4 3 the subgraph of S n induced by the vertices of the form iv 2... v n. More generally, for given i 1,...,i r {1,...,}, we denote with i 1...i r S n r the subgraph of S n induced by the vertices of the form i 1...i r v r+1...v n. Note that is n 1 is isomorphic to S n 1, and, more generally, i 1...i r S n r is isomorphic to S n r. An edge of S n of the form u 1u 2...u n 1 i u 1 u 2...u n 1 j, i j, will be called a clique edge. A clique edge is contained in a unique subgraph K of S n. The other edges will be called non-clique edges. Let i j. Then the edge j...j jii... i is the unique edge between is n 1 and js n 1. It will be denoted with e (n) = e (n) ji. Consider the subgraph i 1... i r S n r i 1...i r lj...j will be denoted i 1...i r e (n r) jl. of S n. Then the edge between i 1...i r jl... l and 4 Setting the following holds: ρ i,j = { 1 i j, 0 i = j, Lemma 2.1 [15] Let u 1 u 2...u n and ii... i be vertices of S n. Then d S n ( u 1 u 2... u n, ii... i ) = ρ u1,iρ u2,i...ρ un,i, where the right-hand side is a binary number with digits ρ uj,i. Moreover, a shortest path between u 1 u 2...u n and ii... i is unique. The unique path in S n (n) between ii... i and jj...j will be denoted P. Similarly, in the subgraph i 1...i r S n r, there is a unique path between i 1...i r jj...j and i 1...i r ll...l, it will be denoted i 1... i r P (n r) jl. By the uniqueness of the shortest paths between extreme vertices, it follows that there is also a unique shortest cycle of S n containing the edges e(n), e(n) jl, and e(n) li, where i,j,l {1,2,...,} are pairwise different. This cycle will be denoted C (n) l. One of our embeddings will be an embedding into the Cartesian product of generalized Sierpińsi triangle graphs, a class of graphs introduced in [14] as 2-parametric Sierpińsi gaset graphs. For n 1 and 3, the generalized Sierpińsi triangle graph Ŝ n is the graph obtained from Sn by contracting all non-clique edges of Sn. Note that Ŝ 1 = K ( 3). For Ŝ2 4 see Fig. 2, where {i,j} denotes the vertex obtained by contracting the edge ji. 3 Embeddings into products of generalized Sierpińsi triangle graphs In this section we first summarize the theory developed in [18] about induced embeddings of graphs into Hamming graphs. Let G be a connected graph and let F = {F 1,F 2,...,F p } be a partition of E(G). Such a partition yields the corresponding labeling l : E(G) {1,2,...,p} by setting l(e) = i for e F i. 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 d G (u,v) 2. Then there exist different labels i and j which both appear on any induced u, v-path. Now we can recall: 5 {1, 2} {1, 3} 11 {1, 4} {2, 4} {3, 4} 33 {2, 3} Figure 2: The generalized Sierpińsi triangle graph Ŝ2 4 Theorem 3.1 [18] Let G be a connected graph. Then Hdim(G) 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 = {F 1,...,F p } be a partition of E(G) such that the corresponding labeling l fulfills Conditions A and B. For every i = 1,...,p, define the graph G/F i whose vertices are the connected components of G \F i, two components C and C being adjacent in G/F i whenever there exists an edge of F i connecting a vertex of C with a vertex of C. Let f i : V (G) V (G/F i ) be the natural projection, that is, u V (G) is mapped to the component of G \ F i to which it belongs. Then f = (f 1,...,f p ) : G G/F 1 G/F p (1) is an induced embedding of G. Moreover, by adding edges to each factor G/F i to mae 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/F i 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].) 6 We will mae 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. 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 i on C, then i appears at least once more on C. We now turn our attention to Sierpińsi graphs. Every S n can be embedded in a Hamming graph with two factors as follows. Label the clique and the non-clique edges of S n 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 3. Then the Sierpińsi triangle labeling of S n is inductively defined as follows. Label the edges of S 1 = K with label 1. Suppose now S n, n 1, has already been labeled. Then label every subgraph is n (1 i ) of Sn+1 identically as S n and label the edges e (n+1) with label n + 1. Clearly, the Sierpińsi triangle labeling of S n uses n labels. Note also that the Sierpińsi triangle labeling of S 2 coincides with its 1 2-labeling. Theorem 3.2 Let 3 and n 1. Then the Sierpińsi triangle labeling of S n yields an induced embedding S n Ŝn Ŝn 1 Ŝ1. Proof. Let 3 be a fixed integer. The Sierpińsi triangle labeling clearly fulfills Condition A. Let u,v be two non-adjacent vertices of S n. Consider a shortest path P between u and v and let i be the largest label on P. Then i 1 and every induced path between u and v contains labels 1 and i. Hence Condition B is fulfilled and thus the embedding (1) can be used. Let F i, 1 i n, be the set of edges of S n labeled with n i + 1 in the Sierpińsi triangle labeling of S n. We are going to prove that for any n 1 and for any 1 i n, S n /F i = Ŝi. Let n = 1. Then S 1 = K and all of its edges are labeled with 1. Hence Ŝ1 = K = S 1/F 1. Suppose Theorem 3.2 holds for some n 1 and consider S n+1. Since F 1 = {e (n+1) i j} we infer that S n+1 /F 1 = K = Ŝ1. Let next i 2. Then every edge of F i lies in some subgraph js n. Let jf i be the restriction of F i to js n and note that jf i coincides with the labeling as F i 1 in S n. Hence, by the induction hypothesis, it follows that js n/jf i = Ŝi 1. But then S n+1 /F i = Ŝi by the way the generalized Sierpińsi triangle graphs are constructed. 7 4 A lower bound on Hdim(S n 3 ) In this section we prove: Theorem 4.1 For any n 2, Hdim(S n 3 ) 7 4 3n n n 9 4. To prove the theorem we construct a merging labeling of S3 n, n 2, as follows. For n = 2, label every edge of is3 1 with i and for any j, label the edge e(2) j with i, where {i,j,} = {1,2,3}. Proceed by induction on n as follows. Label every is3 n 1 with the same pattern as S3 n 1, but such that is3 n 1 and js3 n 1 use pairwise different labels for any i j. In addition, label the edges e (n) 12, e(n) 23, and e(n) 13 with the same labels as 3e (n 1) 12, 1e (n 1) 23, and 2e (n 1) 13, respectively. Note that this labeling does not fulfill Condition B since some labels appears only once at C (n) 123. We thus need to merge every label that appears only once on 1P (n 1) 23, only once on 2P (n 1) 13, and only once on 3P (n 1) 12 with the exception of the edges 1e (n 1) 23, 2e (n 1) 13, and 3e (n 1) 12, respectively. The merging is done as follows. Consider the following pairs of oriented subpaths of C (n) (n 2) 123 : 12P 23,32P (n 2) 21 ; 13P (n 2) 23,23P (n 2) 13 ; and 31P (n 2) 12,21P (n 2) 13. Here oriented means that each of these paths has it start and its end, for instance, 12P (n 2) 23 starts in and ends in Now traverse 12P (n 2) 23 and 32P (n 2) 21 in parallel. As soon as a label l 1 is found on 12P (n 2) 23 that appears only once on 1P (n 1) 23, merge it with the corresponding label l 3 of 32P (n 2) 21. (Note that l 3 also appears only once on 3P (n 1) 21 by the construction.) More precisely, we replace every label l 3 in S3 n with l 1. Do the same procedure for the other two pairs of paths. An example of a merging labeling of S3 5 is shown in Fig. 3. Proposition 4.2 A merging labeling of S3 n, 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 S3 2. Let now n 2 and let u,v be vertices of S3 n with d(u,v) 2. Let p be the smallest in the sense that both u and v are in i 1 i 2...i p S n p 3. Then p n 1 since d(u,v) 2. Let u i 1 i 2...i p j 1 S n p 1 3, v i 1 i 2...i p j 2 S n p 1 3, and let {j 1,j 2,j 3 } = {1,2,3}. Let P be a shortest u,v-path. Suppose first that P contains the edges i 1 i 2...i p e (n p) j 1 j 3 and i 1 i 2...i p e (n p) j 2 j 3. 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 = i 1 i 2...i p e (n p) rq, namely the edge i 1 i 2... i p e (n p) j 1 j 2. 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 8 Figure 3: A merging labeling of S 5 3 i 1 i 2...i p j 2 S n p 1 3. Then the label of f appears also on the triangle of i 1 i 2...i p j 3 S n p 1 3 that is incident with the edge i 1 i 2...i p e (n p) j 1 j 3. Again by the construction, the label of f appears on any induced u,v-path. Lemma 4.3 Let S3 n, n 2, be labeled with a merging labeling. Then every label of a non-clique edge of P (n), i,j {1,2,3}, besides e (n) (n), appears exactly twice on P. Proof. There is nothing to be proved for n = 2. We can restrict to P (n) 23 by symmetry. Note that the labels of the edges 2e (n 1) 23 and 3e (n 1) 23 are merged in S3 n and have thus 9 the same label. Hence every label of a non-clique edge of P (n), i,j {1,2,3}, besides e (n) (n), appears at least twice on P 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 2e (n 1) 23 and 3e (n 1) 23. Indeed, their labels were unique on 2P (n 1) 23 and 3P (n 1) 23, respectively and were henceforth merged in the last step of the construction. The label of the edges 22e (n 2) 23 and 23e (n 2) 2P (n 1) 13 and is also merged in S n 3 23 (which is the same) appears only once on (n 2). But this label appears on 23P 13 and is merged with a label from 13P (n 1) 23. In other words, this label does not appear in 3S n 1 3 and consequently not on 3P (n 1) 23. By symmetry, the assertion also holds for the label of the edges 32e (n 2) 23 and 33e (n 2) 23. Next we show that the label l of non-clique edges 222e (n 3) 23 and 223e (n 3) 23 appears twice on 2P (n 1) (n 3). Clearly l appears once on 223P 13 and is not merged in S3 n 13 (on the edge incident with ) and was in 2S3 n 1 merged with the label of the edge on 213P (n 3) 23 incident with This label is in 21S3 n 2 present also on the edges 211e (n 3) 13 and 213e (n 3) 13, which are both on 2P (n 1) 13. Similarly, the label l of the edges 232e (n 3) 23 and 233e (n 3) 23 appears twice on 2P (n 1) 13 and is not merged in S3 n. Clearly l appear once on 2P (n 1) 13 since it is in the triangle of the extreme vertex in 233S3 n 3. But l is also in the triangle of the extreme vertex in 232S3 n 3. Hence it was merged in 2S3 n 1 with the label of the triangle of the extreme vertex in 212S3 n 3. But this was again merged in 21S3 n 2 with the label of the triangle of the extreme vertex , which lie on 2P (n 1) 13. The conclusion also holds for the labels of P (n) 23 in 3S3 n 1 that are symmetric to the edges in previous two paragraphs. Finally, for all the other non-clique edges of P (n) 23 the statement follows by induction. Next we calculate the number of labels of a merging labeling of S3 n. Let b n be the number of labels different from 1 that appear on P (n) 23 exactly once. In other words, b n is the number of labels of 1S3 n that will be merged with some other label in Sn+1 3. (Clearly label 1 will not be merged.) Hence b n = 2b n 1 2c n, where c n represents the number of labels that appear twice on P (n) 23 for the first time.
Related Search
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks