Printer Friendly

Linear recognition of generalized Fibonacci cubes [Q.sub.h](111).

The generalized Fibonacci cube [Q.sub.h](f) is the graph obtained from the h-cube [Q.sub.h] by removing all vertices that contain a given binary string f as a substring. In particular, the vertex set of the 3rd order generalized Fibonacci cube [Q.sub.h](111) is the set of all binary strings [b.sub.1][b.sub.2] ... [b.sub.h] containing no three consecutive 1's. We present a new characterization of the 3rd order generalized Fibonacci cubes based on their recursive structure. The characterization is the basis for an algorithm which recognizes these graphs in linear time.

Keywords: generalized Fibonacci cube, 3rd order generalized Fibonacci cube, characterization, recognition algorithm

1 Introduction

The study of interconnection topologies is not just an important subject in the area of parallel or distributed systems, it also initiates the research work on several new interesting classes of graphs Liu and Hsu (1992). Besides hypercubes, Fibonacci cubes are the most known class of graphs which are applied as a model for interconnection network. They were studied from several points of view and they are known to possess many appealing properties Gregor (2006); Hsu (1993).

The Fibonacci cube [[gamma].sub.h], h [greater than or equal to] 1, is defined as follows. The vertex set of [[gamma].sub.h] is the set of all binary strings [b.sub.1][b.sub.2] ... [b.sub.h] containing no two consecutive 1's. Two vertices are adjacent in [[gamma].sub.h] if they differ in precisely one bit. Several structural properties and applications including different metric aspects such as recursive construction, hamiltonicity, degree sequence and other enumeration have been investigated Castro and Mollard (2012); Dedo et al. (2002); Klavzar (2005); Klavzar and Mollard (2012, 2014). For an extensive survey of Fibonacci cubes see Klavzar (2013).

Suppose f is an arbitrary binary string and h [greater than or equal to] 1. The generalized Fibonacci cube, [Q.sub.h](f), was introduced as the graph obtained from [Q.sub.h] by removing all vertices that contain f as a substring Ilic et al. (2012). In this notation the Fibonacci cube [Q.sub.h] is [Q.sub.h](11). The question for which strings f, [Q.sub.h](f) is

an isometric subgraph of Qh is raised and answered in Ilic et al. (2012) for some small lengths of f. Also, for a given large length of f, the proportion of f such that Qh(f) is an isometric subgraph of Qh is investigated Klavzar and Shpectorov (2012).

The subclass of generalized Fibonacci cubes, the graphs Qh([1.sup.k]), have been introduced already in Hsu and Chung (1993) and further studied in Liu et al. (1994); Wasserman and Ghozati (2003); Zagaglia Salvi (1996). They are called the k-th order generalized Fibonacci cubes (of dimension h) in this paper (note that they were defined as "generalized Fibonacci cubes" in Hsu and Chung (1993)).

Hsu and Chung raised the following question Hsu and Chung (1993):

Question 1.1 Given a graph, how to quickly decide whether it is the k-th order generalized Fibonacci cube of dimension h?

The question has been answered only for Fibonacci cubes in Vesel (2015) where a linear recognition algorithm for Qh (11) is presented. This result provides a linear recognition algorithm for a closely related class of Lucas cubes Taranenko (2013).

The main contribution of this paper is a linear-time algorithm which recognizes the 3rd order generalized Fibonacci cubes. The paper is organized as follows. In the next section we give basic definitions and concepts needed in this paper. In Section 3, a new characterization of the 3rd order generalized Fibonacci cubes is given. This characterization is the basis for the algorithm presented in the last section, which recognizes these graphs in linear time.

2 Preliminaries

The hypercube of order h, denoted by Qh, is the graph G = (V, E) where the vertex set V(G) is the set of all binary strings u = [u.sub.1][u.sub.2] ... uh, ui G {0,1}, and two vertices x, y G V(G) are adjacent in Qh if and only if x and y differ in precisely one place.

Fibonacci numbers form a sequence of non-negative integers [F.sub.n], where [F.sub.0] = 0, [F.sub.1] = 1 and for n > 0 satisfy the recurrence [F.sub.n]+2 = [F.sub.n+1] + [F.sub.n].

The k-th order generalized Fibonacci numbers form a sequence of positive integers [F.sub.n], where [F.sub.0] = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and for n > 0 satisfy the recurrence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We will use [n] for the set {1,2,... , n} in this paper.

The k-th order Fibonacci string of length h is a binary string u = [u.sub.1][u.sub.2].. .uh, ui G {0,1}, with ui+k-1 = 0 for i G [h - k + 1]. In other words, the k-th order Fibonacci string is a binary string without k consecutive ones.

The 3rd order generalized Fibonacci cube Qh (111) is the subgraph of Qh induced by the 3rd order Fibonacci strings of length h. For convenience we also set [Q.sub.0](111) = K1. The 3rd order generalized Fibonacci cubes Qh(111) are shown in Fig. 1 for h = 1,2,3,4. Note that Qh(111) is isomorphic to Qh for h < 2, while Q3(111) is isomorphic to the vertex-deleted subgraph of Q3 denoted by Q3.

It is easy to see that the following lemma holds (see also Hsu and Chung (1993)).

Lemma 2.1 If h > 0, then |V(Qh(111))| = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Let n denote the number of vertices of Qh (111) .

Lemma 2.2 Hsu and Chung (1993) If h [greater than or equal to] 0, then |E(Qh(111))| = [theta](nlogn).

A subgraph H of a graph G is isometric if dH(u, v) = dG(u, v) for any pair of vertices u and v from H. Isometric subgraphs of hypercubes are called partial cubes. The isometric dimension of a graph G, idim(G), is the smallest integer h such that G isometrically embeds into the h-dimensional cube. All generalized Fibonacci cubes are not partial cubes, however, [Q.sub.h](1) isometrically embeds into [Q.sub.h] as shown in Ilic et al. (2012).

[FIGURE 1 OMITTED]

Let [alpha] : V(G) [right arrow] V([Q.sub.h]) be an isometric embedding. We will denote the i-th coordinate of [alpha] with [[alpha].sup.i], i.e. [alpha] = ([[alpha].sub.1], [[alpha].sub.2],... , [[alpha].sub.h]).

Let G be a connected graph and e = xy, f = uv be two edges of G. We say that e is in relation [theta] to f if d(x, u) + d(y, v) = d(x, v) + d(y, u). [theta] is reflexive and symmetric, but need not be transitive. We denote its transitive closure by [theta]*. It was proved in Winkler (1984) that G is a partial cube if and only if G is bipartite and [theta]* = [theta]. The [theta]-classes of a partial cube G constitute a partition of E(G) and will be denoted with 1,... , h in the sequel.

Let G be a partial cube with idim(G) = h and assume that we are given an isometric embedding of G into [Q.sub.h]. Each pair (i, [chi]) G [h] [chi] {0,1} defines the semicube W([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) = {u G V(G)|[[alpha].sup.i](u) = [chi]}. For any i G [h], we call [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] a complementary pair of semicubes.

Any isometric embedding of G with idim(G) into [Q.sub.h] describes the same family of semicubes and pairs of complementary semicubes, which are indexed in a different way. For a partial cube G and a complementary pair of semicubes W(i,0), W(i,1), the set of edges with one end vertex in W(i,0) and the other in W(i,1) forms a [theta]-class i of G.

For an edge ab of G we write:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We will need the following well known lemma, cf. (Hammack et al., 2011, Proposition 11.7).

Lemma 2.3 Let e = ab be an edge of a connected bipartite graph G and [F.sub.ab] = {f | f G E(G), e[theta]f}. Then G - [F.sub.ab] has exactly two connected components, namely G[[W.sub.ab]] and G[[W.sub.ab]].

For an edge ab of a partial cube with an isometric embedding [alpha] into [Q.sub.h], let the vertices a and b differ in the coordinate i, i.e. [[alpha].sup.i] (a) = 0 and [[alpha].sup.i] (b) = 1. Then [W.sub.ab] = W(i 0), [W.sub.ab] = W(i,1) and [F.sub.ab] = {xy | xy edge in E(G) such that [[alpha].sup.i](x) = 0, [[alpha].sup.i](y) = 1 and [[alpha].sup.J](x) = [[alpha].sup.J](y), for all j = i}.

Note that the vertices of [Q.sub.h](111) define an isometric embedding [alpha] into [Q.sub.h] in a natural way, i.e. if u G V([Q.sub.h](111)), then [[alpha].sup.i](u) = ui.

If v is a vertex of a graph G, then NG (v) denotes the set of vertices of G adjacent to v.

For X C V(G) let G[X] denote the subgraph of G induced by the set X.

Let 0h stand for the vertex with zero at all coordinates and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for the vertex with one exactly at the i - th coordinate for i [member of] [h]. We write xy for the concatenation of binary strings x and y. We will also denote by ei =[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the i-th unit string in {0, 1}h.

For binary strings u and v of equal length let u + v denote their sum computed bitwise modulo 2. In particular, u + ei is the string obtained from u by complementing its i-th bit.

3 Characterization

Let ab be an edge of a partial cube G for which [U.sub.ab] = [W.sub.ab]. Then G[[W.sub.ab]] is called a peripheral subgraph of G.

A [theta]-class E of a partial cube G is called peripheral if at least one of G[[W.sub.ab]] and G[Wba] is peripheral for all ab G E. It is known that every [theta]-class of a Fibonacci cube is peripheral Taranenko and Vesel (2007). Here we show that the same holds for the 3rd order generalized Fibonacci cubes.

Lemma 3.1 Every [theta]-class of [Q.sub.h](111) is peripheral.

Proof: Since [Q.sub.h](111) isometrically embeds into [Q.sub.h], it admits [theta]-classes denoted 1,... , h. Note that an edge e = uv belongs to a [theta]-class i if and only if u and v differ exactly in the i-th coordinate. Suppose w.l.o.g. that u [member of] W(i,1) and v G W(i,0). Let x be a vertex of W(i,1) and let x' be obtained from x by changing the i - th position of x to 0. Since it is straightforward to see that x' is a vertex of Wvu, it follows that xx' G Fuv and Wuv = W(i,1) = Uuv. This assertion completes the proof. []

Let fh, h > 1, denote the number of the 3rd order Fibonacci strings of length h, i.e. fh = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] = |V([Q.sub.h](111))|. For convenience, we also set f0 := 1.

The following result shows the recursive structure of [Q.sub.h](111) (see also Fig. 2).

Proposition 3.2 If W(i,[chi]), [chi] G {0,1}, is a semicube of[Q.sub.h](111), then the following hold.

(i) [Q.sub.h](111)[W(1 0)] is isomorphic to [Q.sub.h]-1(111).

(ii) | W(1,1) | = fh-2 + fh-3.

(iii) |W(1,0) [pi] W(2,1) = fh-3 + fh-4.

(iv) [Q.sub.h](111)[W(1,1) | W(2,1)] is isomorphic to [Q.sub.h]-3(111).

(v) [Q.sub.h](111)[W(11) [pi] W(2,0)] is isomorphic to [Q.sub.h]-2(111).

(vi) |W(i,0)| = fi-1fh-i, i [member of] [h].

(vii) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: It is obvious that u G V([Q.sub.h]-1(111)) if and only if 0u G W(1,0). Moreover, uv G E([Q.sub.h]-1(111)) if and only if 0u and 0v are adjacent in [Q.sub.h](111). Since |V([Q.sub.h]-1(111))| = fh-1 and |V([Q.sub.h](111))| = fh = fh-1 + fh-2 + fh-3, (i) and (ii) easily follow. Analogously, (iii) follows from (i) and (ii).

For (iv) note that if u is a vertex of W(1,1) [pi] W(2,1), then [u.sub.1] = u2 = 1 and u3 = 0. Therefore, v G V([Q.sub.h]-3(111)) if and only if 110v G W(1,1) [pi] W(2,1) and the assertion easily follows. The proof of (v) is analogous.

For the proof of (vi), let [F.sub.h] be the set of all the 3rd order Fibonacci strings of length h and Tih C [F.sub.h], i G [h] be the subset which includes all strings of [F.sub.h] with 0 at the position i. In order to prove the assertion, note that |[F.sub.h]| = [f.sub.h] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Finally, for the proof of (vii) note that [U.sub.ab] denotes the set of vertices of [W.sub.ab] that are adjacent to the vertices of [W.sub.ab]. We have [W.sub.ab] = W(1,0) and [W.sub.ab] = W(1,1). Moreover, [W.sub.ab] = W(1,1) [pi] (W(2,0) [union] (W(2,1) [pi] W(3,0))). Since every [theta]-class of [Q.sub.h](111) is peripheral by Lemma 3.1, we have [W.sub.ab] = Uba. It follows that [U.sub.ab] = W(10) [pi] ((W(2 0) [union] (W(2,1) [pi] W(3,0))). Since W(10) = W(1,0) [pi] ((W(2,0) U (W(2,1) [pi] (W(3,0) [union] W(3,1)))), we have [W.sub.ab] | [U.sub.ab] = W(10) | (W(10) [pi] ((W(2,0) [union] (W(2,1) [pi] W(3,0)))) = W(1,0) [pi] W(2,1) [pi] W(3,1) and the assertion follows. []

[FIGURE 2 OMITTED]

Lemma 3.3 Let h [greater than or equal to] 9 and x = 10h-1 G V([Q.sub.h](111)). Ifxy is an edge of[Q.sub.h](111)[W(1,1)] and the set W(1,1) [pi] [W.sub.yx] admits exactly [f.sub.h-3] vertices, then W(1,1) [pi] [W.sub.yx] = W(1,1) [pi] W(2,1).

Proof: By Proposition 3.2(ii) we have |W(1,1) | = fh-2 + [f.sub.h-3]. Moreover, by Lemma 2.3, a vertex u of W(1,1) [W.sub.yx] is adjacent to a vertex v of W(1,1) [pi] [W.sub.yx] if and only if u and v differ in precisely the i-th coordinate, i [greater than or equal to] 2. Since x = 10h-1, the i-th coordinate of u and v is 1 and 0, respectively. From the proof of Lemma 3.1 then it follows that | [W.sub.yx] | < |[W.sub.yx]| and therefore we get |W(1,1) [pi] [W.sub.yx]| < |W(1,1)n[W.sub.yx]|.

If i = 2, then W(1,1) [pi] [W.sub.yx] = W(1,1) [pi] W(2,1). From Proposition 3.2(iv) (see also Fig. 2, where b and e can be replaced with x and y, respectively) we can see that [Q.sub.h](111)[W(1,1) [pi] [W.sub.yx]] is isomorphic to [Q.sub.h]-3(111). [F.sub.h]us, |W(1,1) [pi] [W.sub.yx]| = fh-2 and |W(1,1) [pi] [W.sub.yx]| = [f.sub.h-3].

We will show that |W(1,1) [gamma] W(i,0) | = fh-2 for every i > 2.

Let i = 3. If u G W(1,1) [pi] W(3,0), then either u2 = 0 or u2 = 1. It follows from Proposition 3.2(vi) that |W(1,1) [pi] W(3,0) | = 2 [f.sub.h-3] > fh-2 and the case is settled.

Let i = 4. If u [member of] W(1,1) [intersection] W(4,0), then either u2 = 0, or u2 = 1 and u3 = 0. From Proposition 3.2(vi) it follows that |W(1,1) [intersection] W(4,0)| = 3[f.sub.h-4] = 2[f.sub.h-4] + [f.sub.h-5] + [f.sub.h-6] + fh-7 = [f.sub.h-3] + [f.sub.h-4] + fh-7 = [f.sub.h-2] - [f.sub.h-5] + fh-7 < [f.sub.h-2].

Let i = h. If u [member of] W(1,1) [intersection] W(h,0), then either u2 = 1 and u3 = 0 or u2 = 0. From Proposition 3.2(vi) it follows that |W(1,1) [intersection] W(ft.,0)| = [f.sub.h-3] + [f.sub.h-4] < [f.sub.h-2].

Let i = h - 1. If u [member of] W(1,1) [intersection] W(h-1,0), then either u2 = 1 and u3 = 0 or u2 = 0. Moreover, uh = 0 or uh = 1. From Proposition 3.2(vi) it follows that |W(1,1) [intersection] W(h-1,0)| = 2([f.sub.h-4] + [f.sub.h-5]) = [f.sub.h-4] + [f.sub.h-5] + [f.sub.h-3] - [f.sub.h-6] = [f.sub.h-2] - [f.sub.h-6] < [f.sub.h-2].

Let i = h - 2. Similarly as above we get | W(11) [intersection] W(h-2,0) | = 4([f.sub.h-5] + [f.sub.h-6]) = 2([f.sub.h-3] - fh-7) < 2[f.sub.h-3] [f.sub.h-6] [f.sub.h-3] + [f.sub.h-3] fh - 6 [f.sub.h-3] [f.sub.h-3] + [f.sub.h-5] [f.sub.h-2].

For 5 [less than or equal to] i [less than or equal to] h - 3 note that for u [member of] W(1,1) [intersection] W(i,0) we have either u2 = 0 or u2 = 1 and u3 = 0. From Proposition 3.2(vi) then it follows that |W(1,1) [intersection] W(i,0)| = [f.sub.i-3]fh-i + [f.sub.i-4]fh-i. We will show that ([f.sub.i-3] + [f.sub.i-4])fh-i < [f.sub.h-2], 5 [less than or equal to] i [less than or equal to] h - 3, by induction on h. For h [member of] {9,10,11} the values of |W(1,1) [intersection] W(i,0) | = ([f.sub.i-3] + [f.sub.i-4])fh-i are depicted in Table 1 and we can see that ([f.sub.i-3] + [f.sub.i-4])fh-i < [f.sub.h-2] for every i of the interest. Suppose that the assertion holds for all dimensions smaller than h, for some h > 11. Let us consider the dimension h for 5 [less than or equal to] i [less than or equal to] h - 3. We have ([f.sub.i-3] + [f.sub.i-4])fh-i = ([f.sub.i-3]+[f.sub.i-4])fh-i-1 + ([f.sub.i-3]+[f.sub.i-4])[f.sub.h-2]-i + ([f.sub.i-3]+[f.sub.i-4])[f.sub.h-3]-i. Note that by the induction hypothesis:

([f.sub.i-3] + [f.sub.i-4])fh-i-1 < [f.sub.h-3], 5 [less than or equal to] i [less than or equal to] h - 1, ([f.sub.i-3] + [f.sub.i-4])fh-i-2 < [f.sub.h-4], 5 [less than or equal to] i [less than or equal to] h - 2, and ([f.sub.i-3] + [f.sub.i-4])fh-i-3 < [f.sub.h-5], 5 [less than or equal to] i [less than or equal to] h - 3.

It follows that ([f.sub.i-3] + [f.sub.i-4])fh-i < [f.sub.h-3] + [f.sub.h-4] + [f.sub.h-5] = [f.sub.h-2], 5 [less than or equal to] i [less than or equal to] h - 3.

Since we showed above that ([f.sub.i-3] + [f.sub.i-4])fh-i < [f.sub.h-2] fori [member of] {h - 2, h-1, h}, the proof is complete.

Lemma 3.4 Let xy be an edge of [Q.sub.h](111)[W(11)]such that x = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] If H := Qh(111)[W(11) [intersection] Wyx], then the following hold.

(i) If h [member of] {7,8}, then | V(H) | = [f.sub.h-3] if and only if V(H) = W(11) [intersection] W(2,1) or V(H) = W(11) [intersection] W(h-2,1). Moreover, if V(H) = W(1,1) [intersection] W(h-2,1), then H is not isomorphic to Qh-3(111).

(ii) If h [member of] {5,6}, then |V(H)| = [f.sub.h-3] if and only if V(H) = W(1,1) [intersection] W(2,1).

(iii)If h [member of] {3,4}, then |V(H)| = [f.sub.h-3] if and only if V(H) = W(1,1) [intersection] W (2,1) orV(H) = W(1,1) [intersection] W(3,1). Moreover, if V(H) = W(11) [intersection] W(3,1), then H is isomorphic to Q.-3(111).

Proof: Note that in the graph Qh(111) we have |W(1,1)| = |W(1,1) [intersection] W(i,0)| + |W(1,1) [intersection] W(i,1)| = [f.sub.h-2] + [f.sub.h-3], i [member of] {2,... , h}, by Proposition 3.2(ii). We can obtain analogously as in the proof of Lemma 3.3 the number of vertices of W(1,1) [intersection] W(i,0) and W(1,1) [intersection] W(i,1) as follows. If i = 2, then |W(1,1) [intersection] W(i,0)| = [f.sub.h-2] and |W(1,1) [pi] W(i,1)| = [f.sub.h-3]; ifi = 3, then |W(1,1) [intersection] W(i,0)| = 2[f.sub.h-3]; for i G {4,... , h} we get |W(1,1) [pi] W(i,0)| = [f.sub.h-3]fh-i + [f.sub.h-4]fh-i. The values of |W(1,1) [pi] W(i,0)| for every i G {2,... , h} and for all h = {5,6, 7, 8} are depicted in Table 2.

(i) Since f5 = 24 and f6 = 44, the first part of the assertion follows from Table 2. In order to see that Q7(111)[W(1,1) [pi] W(5,1)] is not isomorphic to Q4(111), observe first that V(Q7(111)[W(1,1) [pi] W(5,1)]) = {1000100, 1000101, 1000110, 1001100, 1010100, 1100100, 1001101, 1010101, 1100101, 1010110, 1100110, 1101100, 1101101}.

Note that by Proposition 3.2 the graph isomorphic to Q4 (111) has to admit an edge ab such that | [W.sub.ab] | = f4-1 = f3 = 7 and |Wba| = f2 + [f.sub.1] = 6.

We can see that |W(1,1) [pi] W(5,1) [pi] W(2,1)| = 5, |W(1,1) [pi] W(5,1) [pi] W(3,1)| = 3, |W(1,1) [pi] W(5,1) [pi] W(4,1)| = 4, |W(1,1)nW(5,1)nW(6,1)| = 3, |W(1,1)nW(5,1)nW(7,1)| = 5. It follows that Q7(111)[W(1,1)n W(5,1)] cannot be isomorphic to Q4(111) and the case is settled.

The proof that Q8(111)[W(1,1) [pi] W(6,1)] is not isomorphic to Q5(111) is analogous. We can see that V(Q8(111)[W(1 1) [pi] W(6,1)]) = {10000100, 10000101, 10000110, 10010100, 10010101, 10010110, 10001100, 10001101, 10100100, 10100101, 10100110, 10110100, 10110101, 10110110, 10101100, 10101101, 11000100, 11000101, 11000110, 11010100, 11010101, 11010110, 11001100, 11001101}.

By Proposition 3.2, the graph isomorphic to Q5(111) has to admit an edge ab such that | [W.sub.ab] | = f5-1 = f4 = 13 and |Wba| = f3 + f2 = 11.

We can see that |W(1,1) [pi] W(6,1) [pi] W(2,1) = 8, |W(1,1) [pi] W(6,1) [pi] W(3,1)| = 8, |W(1,1) [pi] W(6,1) [pi] W(4,1)| = 9, |W(1,1) [eta]W(6,1)[eta]W(51) | = 6, | |/(1,1)[pi]W(6,1)[eta]W(71)| = 6, |W(1,1)[pi]W(6,1)[eta]W(81)| = 9. It follows that Q8(111)[W(1,1) [eta] W(6,1)] cannot be isomorphic to Q5(111) and the case is settled.

(ii) Since we can see from Table 2 that |W(1,1) [pi] W(i,0) | = [f.sub.h-2] only if i = 2, the assertion follows.

(iii) The assertion follows from Fig. 1. []

Remark 3.5 The results of Proposition 3.2, Lemmas 3.3 and 3.4 can be analogously statedforb = 0h-11, W(h,[chi]), W(h-1,[chi]), and x = 0h-11. In particular, an analog to Lemma 3.3 is as follows:

Let h > 9 and x = 0h-11 G V(Qh(111)). If xy is an edge of Qh(111)[W(h1)] and the set W(h1) [pi] Wyx admits exactly [f.sub.h-3] vertices, then W(h,1) [pi] Wyx = W(h,1) [pi] W(h-1,1).

Lemma 3.6 Let h>3 and let v be a vertex of Qh(111). Then deg(v) < h if

(i) vi = vi+1 = 1, i < h - 1, or

(ii) vi = vi+2 = 1, i < h - 2.

Proof: (i) Since v cannot have three consecutive ones and h > 3, we have vi-1 = 0 or vi+2 = 0. Suppose w.l.o.g. that vi-1 = 0. Let u G N(v). Note that v and u differ in precisely one coordinate. Since [v.sub.i] = [v.sub.i]+1 = 1 and [v.sub.i]-1 = 0, u and v cannot differ in the (i - 1)-st coordinate and the case is settled. The proof for (ii) is analogous. []

Proposition 3.7 (i) If h > 3, then 0h is the only vertex with h neighbors of degree h in [Q.sub.h](111).

(ii) Let h > 4 and v = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII][h]. Then v has h - 2 neighbors of degree h in [Q.sub.h](111) if and only if i = 1 or i = h.

Proof:

(i) It is clear that 0h has h neighbors of degree h in [Q.sub.h](111). Assume to the contrary that [Q.sub.h](111) admits a vertex v with h neighbors of degree h such that [v.sub.i] = 1. Note that v cannot have [v.sub.i] = [v.sub.i]+1 = 1, i < h - 1, or [v.sub.i] = [v.sub.i]+2 = 1,i < h - 2,by Lemma 3.6. It follows that there exist a vertex u adjacent to v such that either [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. But then we have either ui = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. From Lemma 3.6 it follows that u admits less then h neighbors and we obtain a contradiction.

(ii) Note that [10.sup.h-1] and 0h-11 have h - 2 neighbors of degree h in [Q.sub.h](111). Assume to the contrary that [Q.sub.h](111) admits a vertex v = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with exactly h - 2 neighbors of degree h such that 2 [less than or equal to] i [less than or equal to] h - 1. We can see from Lemma 3.6 that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are neighbors of v with a degree less then h. Moreover, since h > 4, at least one of v + ei+2 and v + ei-2 exists in [Q.sub.h](111). Since both have less then h neighbors in [Q.sub.h](111) by Lemma 3.6, we again obtain a contradiction. []

If G is an isometric subgraph of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote a graph obtained from G by exchanging the i-th and the j-th coordinate in every vertex of V(G). Note that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is an isometric subgraph of [Q.sub.h] isomorphic to G. From Fig. 1 we can see

Proposition 3.8 The vertices of Q3(111)[W(11) ]2,3 and Q4(111)[W(1,1)]2,3 are the 3rd order Fibonacci strings.

The next theorem gives a new characterization of [Q.sub.h] (111).

Theorem 3.9 Let ab be an edge of a connected, bipartite graph G such that a has h neighbors of degree h and b has h - 2 neighbors of degree h.

If h [greater than or equal to] 10 or h [member of] {4,5,6,7}, then G is isomorphic to [Q.sub.h](111) if and only if the following conditions hold:

(i) G[[W.sub.ab]] is isomorphic to [Q.sub.h]-1(111).

(ii) Fab is a matching defining an isomorphism between G[[U.sub.ab]] and G[[W.sub.ba]].

(iii) [W.sub.ab] | [U.sub.ab] = [W.sub.ab] [pi] [W.sub.ca] [pi] Wdcfor c G [U.sub.ab] which has h - 3 neighbors of degree h - 1 in G[[W.sub.ab]] and is adjacent to a vertex d G [W.sub.ab] | [U.sub.ab].

(iv) |[W.sub.ab] | [U.sub.ab]| = [f.sub.h-4].

Proof: Let G be isomorphic to [Q.sub.h](111). From Proposition 3.7 it follows that a = 0h and b = [10.sup.h-1] or b = 0h-11. Suppose first that b = [10.sup.h-1].

(i) This is Proposition 3.2(i).

(ii) Since a = 0h and b = [10.sup.h-1], we have [W.sub.ab] = W(1,0) and [W.sub.ba] = W(1,1). Thus, an edge of Fab has one end-vertex with zero at the first position and one end-vertex with one at the first position. Since all [theta]-classes of [Q.sub.h](111) are peripheral by Lemma 3.1, it follows that [W.sub.ba] = Uba. Let u,v G [W.sub.ba] and u!, v' G [W.sub.ba] such that uu', vv' G Fab. Since u and u! (resp. v and v') differ precisely in the first coordinate, uv G [member of] (G[[W.sub.ba]]) if and only if u'v' G E(G[[U.sub.ab]]). It follows that G[[U.sub.ab]] and G[[W.sub.ba]] are isomorphic.

(iii) From (i) and Proposition 3.7 it follows that c = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Proposition 3.2(vii) yields [W.sub.ba] | [U.sub.ab] = W(1,0) [pi] W(2,1) [pi] W(3,1), hence c = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(iv) Every u G [W.sub.ba] | [U.sub.ab] has the first four coordinates fixed such that u4 = 0. Hence, one can construct all the 3rd order Fibonacci strings of length h - 4 at the coordinates 5, 6,... h and we have |[W.sub.ba] | [U.sub.ab]| = [f.sub.h-4].

Since the proof for b = 0h-11 is analogous (see also Remark 3.5), the first part of the proof is complete.

For the converse note that G[[W.sub.ba]] is isomorphic to [Q.sub.h]-1(111), thus we will first construct an isometric embedding of G[[W.sub.ba]] into [Q.sub.h]-1(111), i.e. we will assign the 3rd order Fibonacci strings of length h - 1 to the vertices of G[[W.sub.ba]]. Denote this embedding by [beta]. Since |NG(a)| = h and G is bipartite, we have |NG[[W.sub.ba]](a)| = h - 1 by Lemma 2.3. Since the degree of every u G NG[[W.sub.ba]](a) is h in G, from Lemma 2.3 it follows that the degree of u is at least h - 1 in G[[W.sub.ba]]. Moreover, since G[[W.sub.ba]] is isomorphic to [Q.sub.h]-1(111), the degree of a vertex of G[[W.sub.ba]] cannot exceed h - 1. Hence, a has h - 1 neighbors of degree h - 1 in G[[W.sub.ba]]. From Proposition 3.7 then it follows that we have to set [beta](a) := (0,0,... , 0). Analogously, since c has h - 3 neighbors of degree h - 1 in G[[W.sub.ba]], we may set [beta](c) := (1,0,0,... , 0) (we could also set [beta](c) := (0,0,... , 0,1) by Proposition 3.7. We may assume that [beta](c) := (1,0,0,... , 0). It follows that for every u G [W.sub.ba] [gamma]I Wac we have [[beta].sub.1](u) = 0 and for every v G [W.sub.ba] [gamma]I Wca we have [[beta].sub.1](v) = 1.

Suppose first that h > 10. Note that G[[W.sub.ba]] is isomorphic to [Q.sub.h]-1(111), d belongs to [W.sub.ba] [gamma]I Wca, [W.sub.ba] [pi] Wca [pi] [W.sub.c] = [W.sub.ba] | [U.sub.ab], and | [W.sub.ba] | [U.sub.ab] | = [f.sub.h-4]. Hence, by Lemma 3.3, we have to define [beta] such that for every vertex u G [W.sub.ba] | [U.sub.ab] we have [[beta].sub.1] (u) = [[beta].sub.2] (u) = 1 and [[beta].sub.3] (u) = 0. For h G {4, 5, 6, 7} note that since [beta] is anembeding into [Q.sub.h]-1(111), the value of h is subtracted by 1 when it is applied in Lemma 3.4 and Proposition 3.8. If h G {6,7}, then by Lemma 3.4(ii), we have to define [beta] such that for every vertex u G [W.sub.ba] | [U.sub.ab] we have [[beta].sub.1] (u) = [[beta].sub.2] (u) = 1 and [[beta].sub.3] (u) = 0. If h G {4,5}, then by Lemma 3.4(iii), for every vertex u G [W.sub.ba]|[U.sub.ab] we have either [[beta].sub.1]( u) = [[beta].sub.2](u) = 1 and[[beta].sub.3](u) = 0or[[beta].sub.1](u) = [[beta].sub.3](u) = 1 and [[beta].sub.2](u) = 0. From Proposition 3.8 it follows that above both cases are equivalent, therefore we may choose the former and conclude that for h > 10 or h G {4,5, 6, 7} for every vertex u G [W.sub.ba] [pi] Wca [gamma] [W.sub.c] we have [[beta].sub.1](u) = [[beta].sub.2](u) = 1 and [[beta].sub.3](u) = 0, while for every vertex v G [W.sub.ba] [pi] Wca [gamma]I Wcd we have [[beta].sub.1] (v) = 1 and [[beta].sub.2] (v) = 0. Lemma 3.3 and Proposition 3.2(iv) imply that the vertices of [W.sub.ba] | [U.sub.ab] induce [Q.sub.h]-4(111). We may then construct [beta] for u G [W.sub.ba] [pi] Wca [gamma]I [W.sub.c] such that ([beta]4 (u), [beta]5 (u),... , [beta]h-1 (u)) represents the embedding of [Q.sub.h](111)[[W.sub.ba] | [U.sub.ab]] into [Q.sub.h]-4(111) and the vertices of [W.sub.ba] [pi] Wca [gamma]I Wcd accordingly. Finally, we construct [beta] for every vertex of [W.sub.ba] [pi] Wac with respect to the embedding of vertices of [W.sub.ba] [pi] Wca and the construction of [beta] is complete.

We can now apply [beta] in order to construct an embedding [alpha] of vertices of G into [Q.sub.h](111) as follows. For every vertex x G [W.sub.ba] we set [alpha]1(x) := 0 and [[alpha].sup.i](x) := [beta]i-1(x), 2 < i < h. Note that for every vertex y G [W.sub.ba] there exist a vertex x G [W.sub.ba] such that xy G Fab. Thus, we set [alpha]1(y) := 1 and [[alpha].sup.i](y) := [beta]i-1(x), 2 < i < h.

Obviously, for every vertex v of G we constructed the embedding [alpha] such that [alpha]1(v)[alpha]2(v)... [alpha]h(v) is a 3rd order Fibonacci string. In order to conclude the proof, we have to show that for every G we have uv G E(G) if and only if [alpha](u)[alpha](v) G E([Q.sub.h](111)). Since G[[W.sub.ba]] is isomorphic [Q.sub.h]-1(111), the claim is obvious for every u, v G [W.sub.ba]. For u, v G [W.sub.ba] note that since the matching Fab defines an isomorphism between G[[W.sub.ba]] and G[[U.sub.ab]], for every u, v G [W.sub.ba] we have u', v' G [U.sub.ab] such that uu', vv' G Fab and uv [member of] E(G[[W.sub.a]]) if and only if u'v' G E(G[[U.sub.ab]]) if and only if [alpha](u')[alpha](v') G E(Qh(111)). Finally, for u G [W.sub.ab] and v G [W.sub.a] note that uv G E(G) if and only of uv G [F.sub.ac]. Since [alpha](u) and [alpha](v) differ in precisely one coordinate, the proof is complete. []

Since Theorem 3.9 does not include the graphs Qh(111) for h G {8,9}, we need the following

Proposition 3.10 Let ab be an edge of a connected, bipartite graph G such that a has h neighbors of degree h, b has h - 2 neighbors of degree h.

If h G {8,9}, then G is isomorphic to Qh(111) if and only if the following conditions hold:

(i) G[[W.sub.ab]] is isomorphic to Qh-1(111).

(ii) [F.sub.ac] is a matching defining an isomorphism between G[[U.sub.ab]] and G[[W.sub.a]].

(iii) [W.sub.ab] | [U.sub.ab] = [W.sub.ab] [pi] [W.sub.ca] [pi] [W.sub.dc]for c G [U.sub.ab] which has h - 3 neighbors of degree h - 1 in G[[W.sub.ab]] and is adjacent to a vertex d G [W.sub.ab] | [U.sub.ab].

(iv) |[W.sub.ab] | [U.sub.ab]| = [f.sub.h-4].

(v) G[[W.sub.ab] | [U.sub.ab]] is isomorphic to Qh-4(111).

Proof: For the if part of the proof just note that by Lemma 3.4(i), for he {8,9} the conditions (i)-(iv) do not guarantee that G[[W.sub.ab] | [U.sub.ab]] is isomorphic to Qh-4(111). The rest of the proof is analogous to the proof of Theorem 3.9. []

4 Algorithm

Theorem 3.9 leads to the following recognition algorithm.

Procedure GENERALIZED3 FIBONACCI( G, h);

1. If h < 3 and G is isomorphic to one of {Q1, Q2, Q3} then ACCEPT.

2. Find ab G E(G) such that a has h neighbors of degree h and b has h - 2 neighbors of degree h.

3. If no such edge exists then REJECT.

4. Find the sets [W.sub.ab], [W.sub.a], [U.sub.ab], Uba and [F.sub.ac].

5. Construct the graph G[[W.sub.ab]].

6. Find ac G [member of] (G[[W.sub.ab]]) such that c has h - 3 neighbors of degree h - 1 in G[[W.sub.ab]] and c is adjacent to a vertex d G [W.sub.ab] | [U.sub.ab].

7. If no such edge exists then REJECT else find sets [W.sub.ac], [W.sub.ca], [W.sub.dc].

8. Verify that

8.1. GENERALIZED3 FIBONACCI(G[[W.sub.ab]], h - 1) returns ACCEPT.

8.2. [F.sub.ac] is a matching which defines an isomorphism between G[[U.sub.ab]] and G[[W.sub.a]].

8.3. [W.sub.ab] | [U.sub.ab] = [W.sub.ab] [eta] [W.sub.ca] [eta] [W.sub.dc].

8.4. |[W.sub.ab] | [U.sub.ab]| = [f.sub.h-4].

8.5. h [??] {8,9} or G[[W.sub.ab] | [U.sub.ab]] is isomorphic to Qh-4(111).

9. If all of the foregoing conditions are fulfilled then ACCEPT else REJECT.

Before GENERALIZED3 FIBONACCI is started, some preprocessing has to be done. A given graph G is examined only if |V(G)| = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some h [greater than or equal to] 1, otherwise the graph is rejected. Moreover, we have to establish whether G is bipartite. Note that this can be done in O(m) time.

The given bipartite graph G is then declared the 3rd order generalized Fibonacci cube if and only if GENERALIZED3 FIBONACCI(G,h) terminates without ever encountering a REJECT statement. In other words, GENERALIZED3 FIBONACCI for a graph G terminates with success if and only if either h [greater than or equal to] 4 and the conditions of Theorem 3.9 and Proposition 3.10 are fulfilled for G or h [less than or equal to] 3 and G is isomorphic to one of {Q1, Q2, Q3}. This gives us the following

Theorem 4.1 GENERALIZED3 FIBONACCI correctly recognizes Qh (111).

In order to find the time complexity of the algorithm, we first show two lemmas.

Lemma 4.2 If h[greater than or equal to]3, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: We first compute [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that we write every 2ifi as ifi +i(fi+3 - fi+2 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We obtain above telescoping series in which all terms [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are cancelled. Thus we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The assertion now clearly follows. []

Theorem 4.3 GENERALIZED3 FIBONACCI runs in linear time.

Proof: Let m denote the number of edges of G.

Concerning the time complexity, we will show that the time complexity of every step of the algorithm with the exception of Step 8.1 is bounded by O(m). Since for h < 3 the graphs [Q.sub.h] = [Q.sub.h](111) are very simple, this is obviously true for Step 1. For Steps 2 and 3 it is convenient to arrange the vector deg, such that [deg.sub.v] equals the number of vertices adjacent to v for every v [member of] V(G). We then first determine vertex a with h neighbors of degree h, by inspecting the adjacency list for every vertex of a graph. The total number of all examined entries in the adjacency list is clearly bounded by O(m). If a is found, then we check its neighbors in order to find the vertex b. Analogously, this can be done again in linear time and the proof for Steps 2 and 3 is settled. Concerning Steps 4, 5, and 7 it has been shown in Jha and Slutzki (1992) that they can be performed in time linear in the number of edges of the input graph. Since the proof for Step 6 is analogous to the proof for Steps 2 and 3, we may proceed with Step 8. It has also been shown in Jha and Slutzki (1992) that Step 8.2 can be performed in time linear in the number of edges of the input graph. If we mark every vertex of [U.sub.ab] [union] Uba, [W.sub.ab], [W.sub.ca], and Wdc, then Steps 8.3 and 8.4 can be implemented to run within the same time bound. Thus, neglecting the recursive call, the total time needed to check G is bounded by O(m), i.e. the cost per edge processed by a single call of the algorithm is O(1).

By Lemma 2.2 we have m = [theta](n log n). If follows that we can find a constant C such the the total time needed to check G, neglecting the recursive call, is bounded by C hfh.

Let mh denote the total number of edges checked by the algorithm.

From the above discussion we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

while Lemma 4.2 yields [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We showed that the total number of edges processed by GENERALIZED3 FIBONACCI(G, h) cannot exceed [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Moreover, since we showed that the cost per edge processed by a single call of the the algorithm is O (1), the proof is complete. []

References

A. Castro and M. Mollard. The eccentricity sequences of Fibonacci and Lucas cubes. Discrete Mathematics, 312(5):1025-1037, 2012.

E. Dedo, D. Torri, and N. Z. Salvi. The observability of the Fibonacci and the Lucas cubes. Discrete Mathematics, 255(1):55-63, 2002.

P. Gregor. Recursive fault-tolerance of Fibonacci cube in hypercubes. Discrete mathematics, 306(13): 1327-1341, 2006.

R. Hammack, W. Imrich, and S. Klavzar. Handbook of product graphs. CRC Press, 2011.

W. Hsu and M. Chung. Generalized Fibonacci cubes. In Parallel Processing, 1993. ICPP 1993. International Conference on, volume 1, pages 299-302. IEEE, 1993.

W.-J. Hsu. Fibonacci cubes-a new interconnection topology. IEEE Transactions on Parallel and Distributed Systems, 4(1):3-12, 1993.

A. Ilic, S. Klavzar, and Y. Rho. Generalized Fibonacci cubes. Discrete Mathematics, 312(1):2-11, 2012.

P. K. Jha and G. Slutzki. Convex-expansions algorithms for recognition and isometric embedding of median graphs. Ars Combinatoria, 34:75-92, 1992.

S. Klavzar. On median nature and enumerative properties of Fibonacci-like cubes. Discrete Mathematics, 299(1):145-153, 2005.

S. Klavzar. Structure of Fibonacci cubes: a survey. Journal of Combinatorial Optimization, 25(4):505-522, 2013.

S. Klavzar and M. Mollard. Wiener index and Hosoya polynomial of Fibonacci and Lucas cubes. MATCH Communications in Mathematical and in Computer Chemistry, 68(4):311-324, 2012.

S. Klavzar and M. Mollard. Asymptotic properties of Fibonacci cubes and Lucas cubes. Annals of Combinatorics, 18(3):447-457, 2014.

S. Klavzar and S. Shpectorov. Asymptotic number of isometric generalized Fibonacci cubes. European Journal of Combinatorics, 33(2):220-226, 2012.

J. Liu and W.-J. Hsu. Distributed algorithms for shortest-path, deadlock-free routing and broadcasting in a class of interconnection topologies. In Parallel Processing Symposium, 1992. Proceedings., Sixth International, pages 589-596. IEEE, 1992.

J. Liu, W.-J. Hsu, and M. J. Chung. Generalized Fibonacci cubes are mostly Hamiltonian. Journal of Graph Theory, 18(8):817-829, 1994.

A. Taranenko. A new characterization and a recognition algorithm of Lucas cubes. Discrete Mathematics and Theoretical Computer Science, 15(3):31, 2013.

A. Taranenko and A. Vesel. Fast recognition of Fibonacci cubes. Algorithmica, 49(2):81-93, 2007.

A. Vesel. Linear recognition and embedding of Fibonacci cubes. Algorithmica, 71(4):1021-1034, 2015.

H. C. Wasserman and S. Ghozati. Generalized linear recursive networks: topological and routing properties. Computers & Electrical Engineering, 29(1):121-134, 2003.

P. M. Winkler. Isometric embedding in products of complete graphs. Discrete Applied Mathematics, 7 (2):221-225, 1984.

N. Zagaglia Salvi. On the existence of cycles of every even length on generalized Fibonacci cubes. Le Matematiche, 51:241-251, 1996.

Yoomi Rho (1) Aleksander Vesel (2*)

(1) Department of Mathematics, Incheon National University, Incheon, Korea

(2) Faculty of Natural Sciences and Mathematics, University of Maribor, Maribor, Slovenia

received 12 Jan. 2015, revised 24thAug. 2016, accepted 25 Aug. 2016.

(*) Supported in part by the bilateral Korean-Slovenian project BI-KR/13-14-005.

([dagger]) Supported by Basic Science Research Program through the National Research Foundation of Korea funded by the Ministry of Education, Science and Technology grant 2011-0025319.

([double dagger]) Supported by the Ministry of Science of Slovenia under the grant 0101-P-297.
h\i   2    5    6    7    8

 9   81   78   77
10  149  144  143  140
11  274  264  264  260  259

Tab. 1: Values of | [W.sub.(1,1)] [intersection] [W.sub.(i,0)]| for i
[member of] {2, 5,... , h - 3}, h = {9,10,11}.

h|i   2   3   4   5   6   7   8

 5    7   8   6   6
 6   13  14  12  12  11
 7   24  26  21  24  22  20
 8   44  48  39  42  44  40  37

Tab. 2: Values of [W.sub.(1,1)] [intersection] [W.sub.(i,0)]| for
every i [member of] {2,... , h} and for all h = {5, 6, 7, 8}.
COPYRIGHT 2016 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Rho, Yoomi; Vesel, Aleksander
Publication:DMTCS Proceedings
Article Type:Report
Date:Jan 1, 2016
Words:7974
Previous Article:Connected tropical subgraphs in vertex-colored graphs.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters