S369550579.online.de

A simple O(mn) algorithm for recognizing Institut f¨ur Mathematik und Angewandte Geometrie We show that any isometric irredundant embedding of a graph into a product of complete graphs is the canonical isometric embedding.
This result is used to design a simple O(mn) algorithm for recognizingHamming graphs.
All graphs considered in this paper are finite undirected graphs without loops and multiple edges. Throughout the paper, for a given graph G, let n and m stand for the number of its vertices and edges, respectively.
Graphs that can be embedded isometrically in a Cartesian product of complete graphs are called Hamming graphs. Interest in Hamming graphs has been decisively stimulated by the work of Graham and Pollak [10, 11] ∗This work was supported in part by the Ministry of Science and Technology of Slovenia in communication theory and Firsov [8] in linguistics. In biology, Hamming graphs appear as "quasi-species" [6].
Several algorithms for recognizing Hamming graphs have been proposed.
The first algorithm is due to Winkler [16]. Its running time is bounded by O(n5). Aurenhammer, Formann, Idury, Sch¨affer and Wagner [2] improved Winkler's algorithm to run in O(D(m, n) + n2) time, where D(m, n) is the time needed to compute the distance matrix of the graph. Wilkeit [14] presented another algorithm running in O(n3) time.
In 1985 Graham and Winkler [12] published a fundamental paper on isometric embeddings into Cartesian product graphs. Using their results to- gether with a result of Aurenhammer and Hagauer [4] one can give an O(mn) algorithm to recognize Hamming graphs. Aurenhammer and Hagauer [3] also proposed another algorithm of the same complexity to recognize binary In this paper we present an O(mn) algorithm to recognize Hamming graphs. Our algorithm is also based on the theory of isometric embeddings into Cartesian product graphs. However, our approach needs a minimum of theory and the algorithm itself is simple and straightforward. We have taken care that everything up to and including Section 4 is self-contained.
In particular, this includes all results about binary Hamming graphs.
In the next section we state the necessary definitions and recall a connec- tion between Hamming graphs and the Cartesian product of graphs. In Sec- tion 3 we introduce the relation Θ and reprove a characterization of binary Hamming graphs. Section 4 follows with an algorithm for the recognition of binary Hamming graphs. In the last section we prove that any isometric irredundant embedding of a graph into a product of complete graphs is the canonical isometric embedding. With the aid of this result we extend the algorithm for binary Hamming graphs to all Hamming graphs.
Let Σ be a finite alphabet and let w1 and w2 be words of equal lengthover Σ. Then the Hamming distance between w1 and w2, H(w1, w2), is thenumber of positions k in w1 and w2 such that the k-th symbol in w1 differsfrom the k-th symbol in w2. A graph G is called a Hamming graph, if eachvertex v ∈ V (G) can be labelled by a word of fixed length, a(v), such that H(a(u), a(v)) = dG(u, v) for all u, v ∈ V (G). Here dG(u, v) denotes the usualshortest path distance in G between u and v. In particular, if Σ = {0, 1}, we call G a binary Hamming graph.
The Cartesian product G ✷ H of graphs G and H is the graph with vertex set V (G) × V (H) and (a, x)(b, y) ∈ E(G ✷ H) whenever ab ∈ E(G) and x = y, or a = b and xy ∈ E(H). The Cartesian product is commutative, associative and K1 is a unit. Also, G✷H is connected if and only if both Gand H are connected. For G1✷G2✷. ✷Gk we shall also write i=1 Gi let pi : V (G) → V (Gi), i ∈ {1, 2,. , k}, be the natural projection of G onto the i-th factor Gi, i.e. for v = (v1, v2,. , vk) ∈V (G) we set pi(v) = vi ∈ V (Gi). For X ⊆ V (G) let pi(X) = {pi(x) | x ∈ X}.
In particular, for e = uv ∈ E(G) let pi(e) = {pi(u), pi(v)}. We also introducea product coloring c : E(G) → {1, 2,. , k} (with respect to the product representation) as follows. For uv ∈ E(G) we set c(uv) = i if and only if u and v differ in coordinate i. Clearly c is a mapping from E(G) into {1, 2,. , k}. It is not an edge coloring in the usual sense, because incident A subgraph H of a graph G is an isometric subgraph, if dH(u, v) = dG(u, v) for all u, v ∈ V (H). In addition, if α : V (H) → V (G) maps edgesinto edges and α(H) is an isometric subgraph of G, we call α an isometric embedding of H into G.
The following observation is a starting point in studying isometric sub- graphs of Cartesian products of graphs.
i=1 Gi, k ≥ 1, let u = (u1, u2,. , uk) and v = (v1, v2,. , vk) be arbitrary vertices of G. Then dG(u, v) = With Lemma 2.1 it is an easy exercise to characterize Hamming graphs: Theorem 2.2 A graph G is a Hamming graph if and only if G is an iso- metric subgraph of a Cartesian product of complete graphs. Theorem 2.2 in particular implies that binary Hamming graphs are iso- metric subgraphs of hypercubes (the k-dimensional hypercube Qk, k ≥ 1, isthe Cartesian product of k copies of K2).
In this section we present a characterization of binary Hamming graphs which is essential for a fast recognition algorithm.
Let G be a connected graph. Define a relation Θ on E(G) as follows. If e = uu ∈ E(G) and e = vv ∈ E(G), then eΘe if and only if d(u, v) + d(u , v ) = d(u, v ) + d(u , v). This relation, which was first introduced in an alternative form in [5], plays a central role in our investigation. The relation Θ is well-defined, reflexive and symmetric, yet it need not be transitive. We denote its transitive closure by Lemma 3.1 Let P be a shortest path in a graph G. Then no two different edges of P are in relation Θ. Proof. Let u0u1 . um be a shortest path, and let e = uiui+1, e = ujuj+1,i < j. Then d(ui, uj) + d(ui+1, uj+1) = (d(ui+1, uj) + 1) + (d(ui, vj+1 − 1), hence e is not in the relation Θ with e .
It follows from Lemma 3.1 that for a tree on n vertices Θ∗ consists of n − 1 equivalence classes, each containing a single edge. Lemma 3.1 also implies that two adjacent edges are in relation Θ if and only if they lie in a Lemma 3.2 Suppose P is a path connecting the endpoints of an edge e. Then P contains an edge f with eΘf. Proof. Let u0u1 . umu0 be a closed path with e = umu0 and ei = ui−1uifor i = 1, 2,. , m. Set µ(e, ei) = d(um, ui−1) + d(u0, ui) − d(um, ui) − d(u0, ui−1) Clearly s = 2, which means that at least one of the summands µ(e, ei) = 0,i.e. eΘei.
For an edge uv of a graph G let Vuv = { w | w ∈ V (G), dG(w, u) < dG(w, v) }. Lemma 3.3 Let e = uv be an edge of a connected bipartite graph G and let Ee = { f | f ∈ E(G), eΘf }. Then G\Ee has exactly two components. Furthermore, they are induced bythe vertex sets Vuv and Vvu. Proof. G\Ee is disconnected by Lemma 3.2.
Let w ∈ Vuv and let P be a shortest u − w path. Then vP is a shortest v − w path. Hence, using Lemma 3.2 again, no edge of P is in relation Θ with e. It follows that P connects u and w in G\Ee.
Since G is bipartite, d(w, u) = d(w, v). Therefore Vuv and Vvu form a partition of V (G). In addition, no edge ww ∈ E(G), where w, w ∈ Vuv, isin relation Θ with e, and the proof is complete.
For Cartesian product graphs Lemma 2.1 immediately implies: i=1 Gi and let e, e ∈ E(G). (i) If c(e) = c(e ) = i and pi(e) = pi(e ) then eΘe.
(ii) If c(e) = c(e ) then eΘe does not hold. Consider the product G ✷ H of two graphs. Then Lemma 3.4 (i) claims that if ab ∈ E(G), then (a, x)(b, x) is in relation Θ with (a, y)(b, y), for any x, y ∈ V (H). Lemma 3.4 (ii) on the other hand says that if ab ∈ E(G) and xy ∈ E(H), then (a, z)(b, z) is not in relation Θ with (c, x)(c, y), for any c ∈ V (G) and z ∈ V (H), i.e. edges with different colors with respect to the product coloring are not in relation Θ. In other words, every color class (with respect to the product coloring) is the union of one or more equivalence classes with respect to Θ∗.
Theorem 3.5 [16, Winkler] A graph G is a binary Hamming graph if and only if G is bipartite and Θ∗ = Θ. Proof. Assume G is an isometric subgraph of a hypercube. Then G is Define a relation R on E(G) as follows. For e, e ∈ E(G) let eRe if and only if c(e) = c(e ). Let c(e) = c(e ) = i. Then pi(e) = pi(e ) = {0, 1} andhence, by Lemma 3.4 (i), eΘe . Furthermore, by Lemma 3.4, e and e are not related by Θ if c(e) = c(e ). It follows R = Θ. As R is transitive, we Conversely, let G be bipartite and let Θ∗ = Θ. Let e1 = x1y1, e2 = x2y2, ., ek = xkyk, k ≥ 1 be representatives of each equivalence class of Θ∗.
Define an embedding α : V (G) → Qk = {0, 1}k in the following way. Letv ∈ V (G). For i = 1, 2,. , k let the i-th coordinate of α(v) be 0 if v ∈ Vxiyiand 1 if v ∈ Vy . We claim that α is an isometric embedding.
Let uv ∈ E(G) and assume uv belongs to the equivalence class of ei.
By Lemma 3.3, α(u) and α(v) differ in the i-th coordinate. Furthermore, if j = i then d(u, xj) + d(v, yj) = d(u, yj) + d(v, xj). Thus α(u) and α(v) havesame j-th coordinate. It follows that α maps edges to edges.
As G is bipartite and Θ = Θ∗, no two adjacent edges are in the same equivalence class. Furthermore, if P is a shortest path between u and v then, by Lemma 3.1, α(u) and α(v) differ in just as many coordinates as the number of edges of P , i.e., the distance dG(u, v).
In a direct implementation of Theorem 3.5 we must check for all pairs of edges whether they are in relation Θ. For a given graph G this leads to an algorithm with time complexity O(m2). In order to improve this complexity, we introduce relation Θ1, which is due to Feder [7].
Let T be a spanning tree of a graph G. Then edges e, e ∈ E(G) are in the relation Θ1 if and only if they are in the relation Θ and if atleast one of the edges e and e belongs to T . Let E1, E2,. , Ek be theequivalence classes of the relation Θ∗1. For i = 1, 2,. , k let Gi denotethe graph (V (G), E(G)\Ei) and let Ci,1, Ci,2,. , Ci,m denote the con- nected components of Gi. Form the graphs G∗i, i = 1, 2,. , k, by lettingV (G∗i) = {Ci,1, Ci,2,. , Ci,m } and taking C i,j Ci,j to be an edge of G∗i if some edge in Ei joins a vertex in Ci,j to a vertex in Ci,j .
We now define the natural contraction αi : V (G) → V (G∗i) by setting αi(v) = Ci,j if v ∈ Ci,j. Finally, we obtain a mapping α : V (G) → α(v) = (α1(v), α2(v),. , αk(v)). It is important for our algorithm that k ≤ n−1. Indeed, let e = uv ∈ Ei.
By Lemma 3.2 any path in G from u to v must traverse at least one edge from Ei. This is in particular true for the path between u and v in T , hencethere is at least one edge of T belonging to Ei.
This also means that Θ = Θ∗1 in a binary Hamming graph. For, suppose eΘf . Then there is an e ∈ T with e Θe. Since Θ = Θ∗ we also have e Θf and eΘ∗1f. Hence Θ ⊆ Θ∗1. Since Θ1 ⊆ Θ we also have Θ∗1 ⊆ Θ∗ = Θ, whichproves the assertion.
Input: a connected graph G.
Output: TRUE, and a labeling, if G is a binary Hamming graph. FALSE, 1. If G is not bipartite then return FALSE and stop.
2. Compute Θ∗1.
3. Compute Gi, i = 1, 2,. , k and α(v), v ∈ V (G).
4. For i = 1, 2,. , k, compute mi, i.e., the number of components in Gi. If for some i, mi > 2, then return FALSE and stop.
5. Return TRUE and the labeling of G obtained in step 3.
Theorem 4.1 Algorithm BHG correctly recognizes binary Hamming graphs and can be implemented to run in O(mn) time using O(m) space. Proof. Suppose that G is a binary Hamming graph. Then Θ = Θ∗1 andevery Gi has exactly two components by Lemma 3.3. It thus remains toshow that α is an isomorphism, if every Gi has exactly two components.
Let P be a shortest path between u and v in G. By Lemma 3.1 no two edges of P are in the relation Θ and thus all edges of P belong to different Θ∗1 classes. This means that the labels of u and v differ in just as manycoordinates as the number of edges of P , i.e. the distance dG(u, v). Thisproves the correctness of the algorithm.
Concerning the running time we first note that it is trivial to check bipartiteness in O(m) time and space.
Let T be a spanning tree of G and let uv be an edge of T . Then we can calculate the distances from u and v to all other vertices in O(m) time and O(m) space. Hence we get all the edges in G related to e under Θ1in the same time, and in time O(mn) over all edges in T . To get the equivalence classes of Θ∗1 we merge equivalence classes of two edges wheneverwe determine that they are in the relation Θ1. During the execution of theprocedure there will be at most m − 1 such union operations and m(n − 1) find operations. It is well-known that these can be done in O(nm) time using O(m) space (see, for example, [1]).
When Ei is known, it is easy to construct the graph Gi in O(m) time. As k ≤ n − 1, all the Gi can be obtained in O(mn) time. Since every edge in Gicorresponds to an edge of G, we get all the Gi using O(m) space. In addition,we don't need to store the complete information on α(v), it is enough to store the value αi(v) if it is different from αi(u) for some uv ∈ E(G).
Graham [9] proved that there exists a fixed small c such that m ≤ c n log n for any subgraph of a hypercube. Thus: Corollary 4.2 Algorithm BHG can be implemented to run in O(n2 log n) time using O(n log n) space. We are going to modify Algorithm BHG to recognize general Hamming Let α be the mapping (∗) defined in Section 4. Call an isometric em- i irredundant if |Hi| ≥ 2, i = 1, 2,. , m, and for all h ∈ V (Hi), h occurs as a coordinate value of the image of someg ∈ V (G). This is the principal result in the theory of isometric embeddings Theorem 5.1 [12, Graham and Winkler] The mapping α is an isometric i , the so-called canonical embedding. Further- more, the embedding α is irredundant and has the largest possible number of factors among all irredundant isometric embeddings of G. Graham and Winkler [12] proved Theorem 5.1 for the relation Θ, while Feder [7] showed Θ∗1 = Θ∗.
For the isometric embeddings into products of complete graphs we have: Theorem 5.2 [16, Winkler] Any two isometric embeddings of a graph into products of complete graphs are equivalent. Equivalence in Theorem 5.2 essentially means that equivalent isometric embeddings can be obtained from one another by discarding unused factors, permuting factors, and permuting vertices within a factor.
The following theorem is crucial for our algorithm.
i=1 Hi be an isometric irredundant embedding of a graph G into a product of complete graphs Hi. Then this embedding isthe canonical isometric embedding. Proof. By Theorem 5.2 we have to show that any two edges e, e in β(G) are in the relation Θ∗ if they have the same color with respect to the product Consider now i-layers U and V with respect to Hi. We claim that pi(β(G) ∩ U) ⊆ pi(β(G) ∩ V ) or vice versa. If this is not the case, thereare vertices u, u ∈ U and v, v ∈ V such that u ∈ β(G) ∩ U, u / v ∈ β(G) ∩ V, v / where pi(u) = pi(v ), pi(u ) = pi(v) (see Fig. 1).
Suppose the distance between U and V in i=1 Hi is k. Then k + 1 = dH(u, v) = dβ(G)(u, v), which is only possible if u ∈ β(G) or v ∈ β(G).
This proves the claim.
Thus, let the i-colored edges e, e in β(G) be in the i-layers U and V , respectively. If pi(β(G) ∩ U) ⊆ pi(β(G) ∩ V ), then by Lemma 3.4 (i) thereis an edge e in β(G) ∩ V with eΘe . Since β(G) ∩ V is complete we have e Θe , and hence eΘ∗e .
Input: a connected graph G.
Output: TRUE, and a labeling, if G is a Hamming graph. FALSE, otherwise.
1. Compute Θ∗1.
2. Compute Gi, i = 1, 2,. , k and α(v), v ∈ V (G).
3. If for some i = 1, 2,. , k, G∗i is not a complete graph, then return 4. Return TRUE and the labeling of G obtained in step 2.
Theorem 5.4 Algorithm HG correctly recognizes Hamming graphs and can be implemented to run in O(mn) time using O(m) space. Proof. Correctness of the algorithm follows from Theorem 5.3.
The complexity can be argued as in the proof of Theorem 4.1 with the exception of Step 3. Every edge of a factor graph G∗i correspond to anedge of G and furthermore, this correspondence is injective. It follows Hence to implement Step 3 in the desired time and space it is sufficient to count the number of edges in the G∗i's.
[1] A. Aho, J. Hopcroft and J. Ullman, The Design and Analysis of Com- puter Algorithms (Addison-Wesley, Reading, 1974).
[2] F. Aurenhammer, M. Formann, R. Idury, A. Sch¨affer and F. Wagner, Faster isometric embeddings in products of complete graphs, DiscreteAppl. Math., to appear.
[3] F. Aurenhammer and J. Hagauer, Recognizing binary Hamming graphs in O(n2 log n) time, in: Proc. 16th Int. Workshop on Graph TheoreticalConcepts in Computer Science, Lecture Notes in Comput. Sci., Vol. 484(Springer, New York, 1991) 90-98.
[4] F. Aurenhammer and J. Hagauer, Computing equivalence classes among the edges of a graph with applications, Discrete Math. 109 (1992)3-12.
[5] D. Djokovi'c, Distance preserving subgraphs of hypercubes, J. Combin.
[6] M. Eigen and R. Winkler-Oswattisch, Transfer-DNA: the early adaptor, Naturwissenschaften 68 (1981) 217-228.
[7] T. Feder, Product graph representations, J. Graph Theory 16 (1992) [8] V. Firsov, Isometric embedding of a graph in a Boolean cube (Russian), [9] R. Graham, On primitive graphs and optimal vertex assignments, Ann.
New York Acad. Sci. 175 (1970) 170-186.
[10] R. Graham and H. Pollak, On the addressing problem for loop switch- ing, Bell System Tech. J. 50 (1971) 2495-2519.
[11] R. Graham and H. Pollak, On embedding graphs in squashed cubes, in: Graph Theory and Applications, Lecture Notes in Math., Vol. 303(Springer, New York, 1972) 99-110.
[12] R. Graham and P. Winkler, On isometric embeddings of graphs, Trans.
Amer. Math. Soc. 288 (1985) 527-536.
[13] W. Imrich, Embedding graphs into Cartesian products, Ann. New York [14] E. Wilkeit, Isometric embeddings in Hamming graphs, J. Combin. The- [15] P. Winkler, Proof of the squashed cube conjecture, Combinatorica 3 [16] P. Winkler, Isometric embeddings in products of complete graphs, Dis- crete Appl. Math. 7 (1984) 221-225.
[17] P. Winkler, The metric structure of a graph, in: C. Whitehead, ed., Theory and Applications, London Math. Soc. Lecture Note Ser., Vol.
123 (Cambridge University Press, Cambridge, 1987) 197-221.

Source: http://s369550579.online.de/at/uploads/tx_pdforder/P67.pdf