Printer Friendly

Chromatic Numbers of Suborbital Graphs for the Modular Group and the Extended Modular Group.

1. Introduction

Graph coloring is a special case of graph labeling which assigns labels to all vertices or edges of a given graph. In this special case, the labels are called colors. Vertex coloring is the study of how many colors can be assigned to the vertices of a graph verifying that no adjacent vertices are equally colored. Similarly, edge coloring assigns colors to edges of a graph that the same color cannot be painted to edges which have a common vertex.

The graph which can be assigned k colors on its vertices is said to be k-colorable. If k is the smallest number of colors, the graph is said to be k-chromatic and k is called the chromatic number of the graph. In the case of edges, we add the word "edge" to the terminologies, for example, k-edge-colorable, k-edge-chromatic, and edge chromatic number.

This paper studies coloring of suborbital graphs for the modular group and the extended modular group. The results of edge coloring are trivial, so we focus on vertex coloring. This study is separated into two parts in Sections 3 and 4. In Section 3, we provide the coloring results of the directed graph [G.sub.u, n], the suborbital graph for the modular group r. The graph was first constructed in [1] using the general concept introduced by Sims; see more in [2]. The authors showed that G[u.sub., n] was the disjoint union of isomorphic copies of their special subgraph [F.sub.u, n], the generalized Farey graph, coming from the use of the subgroup [[GAMMA].sub.0] (n) of [GAMMA]. Then many properties of [G.sub.u, n] were investigated through the studies on [F.sub.u, n]. Certainly, vertex coloring of [G.sub.u, n] is also examined through the study on [F.sub.u, n].

In 2013, the concept of suborbital graphs continued to the extended modular group [??], as in [3]. The notations are defined likewise. That is, [[??].sub.u, n] denotes the suborbital graph for the extended modular group [??], and [[??].sub.u, n] is a special subgraph of [[??].sub.u, n] coming from the subgroup [[??].sub.u, n] of [??]. Certainly, [[??].sub.u, n] is the disjoint union of isomorphic copies of [[??].sub.u, n]. The vertex coloring results of this case are described in Section 4. The forest conditions for the graph [[??].sub.u, n], which are necessary in vertex coloring, are also studied in this section.

Note that the graph in the context of coloring is loopless. Thus, coloring of the suborbital graphs with loops will not be mentioned.

2. Preliminaries

In this section, we provide some necessary backgrounds used in coloring. Some backgrounds of suborbital graphs may not be mentioned in this research. We start this section with the definition of the modular group. The modular group r is the projective special linear group PSL(2, Z), the group of 2 x 2 matrices of unit determinant with integer coefficients such that every matrix A is identified with its negative -A. Therefore, [GAMMA] is the quotient of the special linear group SL (2, Z) by its center {[+ or -] I}, where I is the identity matrix of order 2. In other words, the elements of PSL(2, Z) are represented by the pairs of matrices [mathematical expression not reproducible]. We usually leave out the signs of the representations for convenience.

From another point of view, the group [GAMMA] maybe presented as a group of transformations. In this manner, it is the group of linear fractional transformations on [H.sup.2] = {z [member of] C : Im (z) > 0} where the composition of functions is the group operation. Certainly, the group in this manner and PSL(2, Z) are isomorphic. In other words, PSL(2, Z) is considered as a group acting on [H.sup.2] by linear fractional transformation, that is,

[mathematical expression not reproducible], (1)

where [mathematical expression not reproducible]. This action can be also extended to the set [??] = Q [union] {[infinity]} as follows:

[mathematical expression not reproducible], (2)

where x/y is an irreducible fraction representing an element of [??]. In this case, [infinity] is represented by -1/0 and 1/0. Certainly, the fractions representing the elements of [??] are not unique since x/y = -x/ - y. However, it does not affect the action of [GAMMA] on [??]. Notice that the action of [GAMMA] on [??] is transitive; that is, [??] has only one orbit under the action of [GAMMA].

The extended modular group [??] is a group generated by [GAMMA] and the hyperbolic reflection z [??] -[bar.z]. In the forms of matrix representations, [mathematical expression not reproducible], that is,

[mathematical expression not reproducible]. (3)

On the set [??], the complex conjugate is ineffective. Then the action of [??] on [??] is the same as that of the group r.

In [1], a suborbital graph for [GAMMA] on [??] was established. The vertex set is defined to be the set [??]. The set of directed edges depends on a pair v, w [member of] [??]. It is defined to be the orbit [GAMMA] (v, w) = {[gamma] (v, w) = ([gamma] (v), [gamma](w)) : [gamma] [member of] [GAMMA]} where the action of [GAMMA] on the Cartesian [??] x [??] is the component-wise action extended from that on [??]. In this research, we let [v.sub.1] - [v.sub.2] denote a directed edge from [v.sub.1] to [v.sub.2]; that is, there exists the edge [v.sub.1] [right arrow] [v.sub.2] of the graph if ([v.sub.1], [v.sub.2]) [member of] [GAMMA] (v, w). Since [GAMMA] acts on [??] transitively, there is an element [gamma] [member of] [GAMMA] such that [gamma] (y) = [infinity]. Certainly, [gamma](w) [member of] [??], so it can be represented as a reduced fraction u/n with nonnegative denominator. This implies that ([infinity], u/n) = [gamma] (v, w) [member of] [GAMMA] (v, w). Hence [GAMMA] ([infinity], u/n) = [GAMMA] (v, w). Then the suborbital graph is simply denoted by [G.sub.u,n]. The case n = 0 is the case of trivial suborbital graphs. There is one loop at every vertex. The coloring of this case will not be mentioned. In the case n [greater than or equal to] 1, edges of the graph are defined to be the upper half-circles and the vertical half-lines in [H.sup.2] joining elements of [??]; see Figure 1 for examples. In this case, the graph [F.sub.u,n] is determined. It is a restriction of [G.sub.u,n] on the orbit ([[GAMMA].sub.0] (n))([infinity]), where [[GAMMA].sub.0] (n) is a congruence subgroup of [GAMMA] defined by

[mathematical expression not reproducible]. (4)

Note that ([[GAMMA].sub.0] (n))([infinity]) = {x/y [member of] [??] : y [equivalent to] 0 mod n}. In fact, [F.sub.u,n] is a suborbital graph for [[GAMMA].sub.0] (n) on ([[GAMMA].sub.0] (n))([infinity]). The following remark is the result obtained directly after constructing the T-invariant equivalence relation related to [[GAMMA].sub.0] (n); see more details in [1].

Remark 1. [G.sub.u,n] is the disjoint union of m = [absolute value of ([GAMMA]: [[GAMMA].sub.0] (n))] isomorphic copies of [F.sub.u,n], where [absolute value of ([GAMMA] : [[GAMMA].sub.0] (n))] is the index of the subgroup [[GAMMA].sub.0] (n) in the group r.

In the case n= 1, we have [G.sub.1,1] = [F.sub.1,1]. This graph is called the Farey graph and denoted by F. We see that r contains [mathematical expression not reproducible], a translation along the real axis. Then [F.sub.u,1] = [G.sub.u,1] = [G.sub.1,1] for every u [member of] Z.

Likewise, in [3], the author used the notation [[??].sub.u,n] to denote the suborbital graph for [??] on [??], and [[??].sub.u,n] is the subgraph of [[??].sub.u,n] on the orbit ([[??].sub.0] (n)) ([infinity]) where [[??].sub.0] (n) is a subgroup of [??] determined by

[mathematical expression not reproducible]. (5)

Certainly, [mathematical expression not reproducible]. Then [mathematical expression not reproducible]. Remark 1 is also true for this version.

Next, we introduce other necessary definitions used in this research. A path in a directed graph is a finite or infinite sequence of different vertices such that every two successive vertices in the sequence are adjacent in the graph. In the finite case, a path is said to be finite. The initial vertex and the final vertex of a finite path are allowed to be equal. For the infinite case, we consider only a path containing the initial vertex. This path is said to be semi-infinite. We use the notations [v.sub.1] [right arrow] [v.sub.2] [right arrow] ... [right arrow] [v.sub.m] and [v.sub.1] [right arrow] [v.sub.2] [right arrow] [v.sub.3] [right arrow] ... to denote finite and semi-infinite paths with the initial vertex [v.sub.1], respectively Note that some arrows in the notations may be reversed.

If the initial vertex and the final vertex of a finite path are equal, we say that the path is closed. A closed path consisting of m [greater than or equal to] 3 vertices is called a circuit. If m = 3, a circuit is called a triangle. We distinguish triangles into two families with respect to the directions of edges. A triangle of the form [v.sub.1] [right arrow] [v.sub.2] [right arrow] [v.sub.3] [right arrow] [v.sub.1] is said to be directed. If a triangle contains two edges of opposite directions, for instance, [v.sub.1] [right arrow] [v.sub.2] [left arrow] [v.sub.3] [right arrow] [v.sub.1], we call it anti-directed. The graph is called a forest if it contains no loops and circuits.

The following proposition shows that there are a countably infinite number of colors to be assigned on the edges of the graphs [mathematical expression not reproducible]. This is due to the fact that there are infinitely many edges incident to the vertex rn by translations in the underline groups. We elaborate this in the detail of the proof. In this case, we say that the graphs are [N.sub.0]-edge-chromatic.

Proposition 2. [mathematical expression not reproducible] are [N.sub.0]-edge-chromatic.

Proof. We know that [GAMMA] and [??] contain all translations [[gamma].sub.k] : z [??] z + k, where k [member of] Z. Then there are infinitely many edges of the graphs [G.sub.u,n] and [[??].sub.u,n] incident to [infinity], that is, [[gamma].sub.k] ([infinity] [right arrow] u/n) = [infinity] [right arrow] (u + kn)/n, where k [member of] Z. We can see easily that (u + kn)/n is also a vertex of [F.sub.u,n] and [[??].sub.u,n] for every k [member of] Z. Thus, all edges [infinity] [right arrow] (u + kn)/n also belong to [F.sub.u,n] and [[??].sub.u,n] . Then we need to paint these all edges by different countable colors. The proof is finally completed because of countability of [??] x [??].

3. Chromatic Numbers of Suborbital Graphs for the Modular Group

In this section, we provide the vertex coloring results of the graphs [F.sub.u,n] and [G.sub.u,n]. We start this section with some useful properties of [F.sub.u,n] obtained in [1]. We state these properties of the graph [F.sub.u,n] in the two lemmas below. The first one provides the results of graph isomorphism. The second describes the relation between edge conditions of the Farey graph F and the Farey sequences. Notice that the Farey sequence of order m [greater than or equal to] 1, denoted by [F.sub.m], is a sequence of reduced fractions x/y [member of] Q sorted in increasing order where [absolute value of (y)] [less than or equal to] m.

Lemma 3. (1) [F.sub.u,n] is isomorphic to [F.sub.-u,n] by the mapping v [??] -v. (2) If m | n, [F.sub.u,n] is isomorphic to a subgraph of [F.sub.u,m] by the mapping v [??] nv/m.

Lemma 4. Let r/s, x/y [member of] Q. Then the three conditions below are equivalent:

(1) The fractions are adjacent vertices in F.

(2) ry - sx = [+ or -] 1.

(3) The fractions are consecutive terms in the Farey sequence [F.sub.m] for some m.

From [1, Theorem 5.1], we know that [F.sub.u,n] contains directed triangles if and only if [u.sup.2] [+ or -] u + 1 [equivalent to] 0 mod n and contains anti-directed triangles only for n =1. Therefore, [F.sub.u,n] contains triangles if and only if [u.sup.2] [+ or -] u + 1 [equivalent to] 0 mod n. Surprisingly, by considering triangles of the graph, we can check whether the graph is a forest or not. In [4], the author proved that [G.sub.u,n] is a forest if and only if it contains no triangles. The author proved it through the subgraph [F.sub.u,n] but concluded for [G.sub.u,n] by using Remark 1. In this paper, we prefer to write it in the version of [F.sub.u,n] which is more useful in our work.

Lemma 5. [F.sub.u,n] is a forest if and only if it contains no triangles; that is, [u.sup.2] [+ or -] u + 1 [not equal to] 0 mod n.

Considering the second result of Lemma 3, we see that every graph [F.sub.u,n] can be embedded as a subgraph of F. Thus, we will study the Farey graph F first and then apply the result to the general case. Now, consider the Farey graph. We know that [F.sub.1,1] and [F.sub.-1,1] are identical. Then the first result of Lemma 3 implies that F is symmetric with respect to the imaginary axis; see Figure 2. Moreover, the graph is periodic with period one along the real axis. This is a consequence of the fact that r contains the translation z [??] z + 1. Thus, we first paint vertices of the graph in the interval [0, 1] and then use the reflection and translations to assign colors to the whole graph.

To paint the vertices of F in the interval [0, 1], we need to introduce the well-known notion, the Farey tree whose vertices form the set of all rationals in [0, 1]. All vertices of the tree can be constructed by using the mediants of fractions. Let r/s, x/y be a pair of fractions, called parents. Their mediant is the fraction given by (r + x)/(s + y), called a child. The following remark includes some facts of the fractions and their mediants used to construct the vertex set of the Farey tree. Its edges will not be mentioned in this paper; see more in [5-7] about the Farey tree.

Remark 6. (1) If r/s [less than or equal to] x/y and s, y > 0, then r/s [less than or equal to] (r + x)/(s + y) [less than or equal to] x/y. (2) If rx - sy = [+ or -] 1, then the fractions r/s, x/y and their mediant (r + x)/(s + y) are reduced.

We are now ready to talk more about the vertex set of the Farey tree. The notations are followed from [7]. Let [FT.sub.1] = [Q.sub.1] = {0/1, 1/1}. For every n [greater than or equal to] 2, [FT.sub.n] and [Q.sub.n] are constructed inductively; that is, [Q.sub.n] is the set of all mediants of every two consecutive fractions in [FT.sub.n-1], and let [FT.sub.n] = [FT.sub.n-1] [union] [Q.sub.n] written as the set of fractions sorted in increasing order. [Q.sub.n] is called the set of Farey fractions of level n. By this method, we finally obtain the vertex set [[union].sub.n[greater than or equal to]0] [FT.sub.n] = Q [intersection] [0, 1] of the Farey tree; see [8, Lemma 2.4]. The following result is a consequence of the preceding remark closely related to Lemma 4.

Remark 7. For each n [member of] N, every pair of successive fractions r/s and x/y in F[T.sub.n] satisfies the identity ry - sx = [+ or -] 1, so they are all reduced.

We see that a child is adjacent to its parents in the Farey graph F. When a child appears, it always lies between their parents. Then a child in [Q.sub.n] and nonparents in [FT.sub.n] are certainly not consecutive terms in the Farey sequence [F.sub.m] for every m [member of] N. We apply this fact to Lemma 4, so they are not adjacent vertices in the graph F. We are now ready to prove the theorem.

Theorem 8. The Farey graph F is 3-chromatic.

Proof. From the discussion above, we first consider the graph on the strip 0 [less than or equal to] Re(z) [less than or equal to] 1. We start with [Q.sub.1] and then color every vertex level by level. Obviously, the vertices [infinity], 0, and 1 are adjacent to one another. Thus, we paint them by different colors [c.sub.1], [c.sub.2], and [c.sub.3], respectively One can check that there is not any vertex of F in (0, 1) adjacent to [infinity]. We then go to the next level [Q.sub.2] = {1/2} and paint the vertex 1/2 by the color [c.sub.1]. We now obtain that three consecutive vertices in [FT.sub.2] = {0, 1/2, 1} are painted by three different colors, [c.sub.2], [c.sub.1], [c.sub.3], respectively. For the next level [Q.sub.3], we can color each vertex by the one remaining color different from those of its parents in [FT.sub.2]. Continue this process inductively, so all vertices of F in the interval [0, 1] will be painted by only the three colors [c.sub.1], [c.sub.2], and [c.sub.3]. After that we extend the color labels to other vertices of the graph in the interval [-1, 0) by the reflection across the imaginary axis and then extend to the whole graph by using the translations z [right arrow] z + 2k where k [member of] Z.

The next three corollaries are results for the graphs [F.sub.u,n] and [G.sub.u,n]. The first one is obtained by combining Lemma 3 with the previous theorem. The lemma implies that [F.sub.u,n] is isomorphic to a subgraph of F which is 3-chromatic. Therefore, we have the following.

Corollary 9. [F.sub.u,n] is 3-colorable.

The first result in the next corollary occurs when the graph [F.sub.u,n] is a forest. The other case is obtained from that the graph contains triangles together with the preceding corollary.

Corollary 10. Let y be the chromatic number of [F.sub.u,n]; then,

(1) [chi] = 2 if [u.sup.2] [+ or -] u + 1 [not equivalent to] 0 mod n,

(2) [chi] = 3 if [u.sup.2] [+ or -] u + 1 [equivalent to] 0 mod n.

Since [G.sub.u,n] is the union of isomorphic copies of [F.sub.u,n], we obtain the results on the chromatic numbers for [G.sub.u,n] as follows.

Corollary 11. Let [chi] be the chromatic number of [G.sub.u,n]; then,

(1) [chi] = 2 if [u.sup.2] [+ or -] u + 1 [not equivalent to] 0 mod n,

(2) [chi] = 3 if [u.sup.2] [+ or -] u + 1 [equivalent to] 0 mod n.

4. Chromatic Numbers of Suborbital Graphs for the Extended Modular Group

This section provides the vertex coloring results for graphs [[??].sub.u,n] and [[??].sub.u,n]. Two lemmas below, edge conditions for [F.sub.u,n] and [[??].sub.u,n], are the useful results obtained in [1] and [3], respectively. They provide the relation between [F.sub.u,n] and [[??].sub.u,n] that we can use to extend the results from the previous section.

Lemma 12. There is an edge r/s [right arrow] x/y in [F.sub.u,n] if and only if

(1) x [equivalent to] ur mod n and ry - sx = n,

(2) x [equivalent to] -ur mod n and ry - sx = -n.

Lemma 13. There is an edge r/s [right arrow] x/y in [[??].sub.u,n] if and only if one of the following conditions is true:

(1) x [equivalent to] ur mod n and ry - sx = n.

(2) x [equivalent to] -ur mod n and ry - sx = -n.

(3) x [equivalent to] ur mod n and ry - sx = -n.

(4) x [equivalent to] -ur mod n and ry - sx = n.

We see that the first two conditions of Lemma 13 are edge conditions for [F.sub.u,n] and the others are for [F.sub.-u,n]. Thus, the graph [[??].sub.u,n] seems to be the union of the graphs [F.sub.u,n] and

[F.sub.-u,n]. In this case, the edge set of [[??].sub.u,n] is the union, in the context of sets, of the edge sets of those two graphs. That is, r/s [right arrow] x/y is an edge of [[??].sub.u,n] if and only if r/s [right arrow] x/y is an edge of [F.sub.u,n] or [F.sub.-u,n]. We know from [4, Lemma 1] that, for every n [greater than or equal to] 1, [G.sub.u,n] = [G.sub.[bar.u],n] if and only if u [equivalent to] [bar.u] mod n. This fact can be applied for [F.sub.u,n]. Therefore, we obtain the following proposition immediately.

Proposition 14. If u [equivalent to] [bar.u] mod n, then [[??].sub.u,n] = [[??].sub.[bar.u],n].

Further, the isomorphism results of [F.sub.u,n], see Lemma 3, can be extended directly to the case of [[??].sub.u,n].

Proposition 15. (1) [[??].sub.u,n] is isomorphic to [[??].sub.-u,n] by the mapping v [??] -v. In fact, [[??].sub.u,n] = [[??].sub.-u,n]. (2) If m | n, [[??].sub.u,n] is isomorphic to a subgraph of [[??].sub.u,n] by the mapping v [??] nv/m.

At this point, it is not difficult to see that [[??].sub.u,1] = [[??].sub.1,1]. Since [F.sub.1,1] = [F.sub.-1,1], [[??].sub.u,1] is actually the Farey graph F. As we introduce in Section 2, all vertices of a suborbital graph in this study are on the real axis of the complex plane, and edges are represented by upper half-circles or the vertical half-line in [H.sup.2] joining two reduced fractions in [??]. We say that two edges of the graph cross in [H.sup.2] if they meet in [H.sup.2] in this representation. By [1, Corollary 4.2], there are not edges of the Farey graph F crossing in [H.sup.2]. Then, after applying the second result of the preceding proposition, we obtain the following corollary immediately.

Corollary 16. No edges of [[??].sub.u,n] cross in [H.sup.2].

In the previous section, we showed that F is 3-chromatic. Then the next corollary is also obtained from the second result of the preceding proposition.

Corollary 17. [[??].sub.u,n] is 3-colorable.

Next, we investigate the chromatic number of [[??].sub.u,n]. From Theorems 5 and 6 of [3], we can conclude that [[??].sub.u,n] contains triangles if and only if [u.sup.2] [+ or -] u + 1 [equivalent to] 0 mod n. In general, a graph with triangles cannot be painted by 2 colors. If [[??].sub.u,n] contains triangles, the previous corollary implies that 3 is the least number of colors which can be assigned to vertices of [[??].sub.u,n]. Therefore, it is 3-chromatic.

Question. What about [[??].sub.u,n] containing no triangles?

We answer this question in Corollary 21. To prove this corollary, we need the following lemmas and theorem, the forest conditions for [[??].sub.u,n].

Lemma 18. If u [not equivalent to] [+ or -] 1 mod n, then there are not adjacent vertices v and w of [[??].sub.u,n] such that v < 1/2 < w.

Proof. By the discussion before Proposition 14, we can work on the graph [F.sub.u,n] instead. Assume that v and w are adjacent vertices of [F.sub.u,n] such that v < 1/2 < w. Then, by using Lemma 3, nv and nw are adjacent in F. If n is even, Lemma 12 implies that [infinity] [right arrow] n/2 is an edge of F crossing the edge incident to nv and nw. This is a contradiction because no edges of F cross in [H.sup.2]. We then suppose that n is odd. By Lemma 4, nv and nw are consecutive terms in some Farey sequence [F.sub.m]. Since nv < n/2 < nw, we have m =1. This implies that nv = (n- 1)/2 and nw = (n+ 1)/2. Then v = ((n-1)/2)/n and w = ((n+1)/2)/n. If v [right arrow] w is an edge of [F.sub.u,n], we have by Lemma 12 that (n+ 1)/2 [equivalent to] -u(n- 1)/2 mod n. Thus, u [equivalent to] 1 mod n. The other case implies that u [equivalent to] -1 mod n. This is a contradiction.

The following lemma is used as a part to prove the forest conditions for [G.sub.u,n] in [1, Theorem 10]. The function in this lemma will arrive on the proof of our next theorem. For the sake of completeness, we include it here together with our own clarification.

Lemma 19. Let u, n, k [member of] R and n [not equal to] 0. Then the function <p : R \ {(u + k)/n} [right arrow] R defined by

z [??] uz - ([u.sup.2] + ku + 1) / n / nz - (u + k) (6)

is increasing on the interval (-[infinity], (u+k)/n) and also increasing on ((u+k)/n, +[infinity]). Further, [phi] ((u+x)/n) < (u+1)/n whenever 1 < k - x.

Proof. Considering the derivative of [phi], d[phi]/dz = 1/[(nz - u - k).sup.2] > 0 for every z [member of] R \ {(u + k)/n}. Then [phi] is increasing on the mentioned intervals. Next, suppose that 1 < k - x. Since [phi] ((u + x)/n) = (u + 1/(k - x))/n, we have [phi] ((u + x)/n) < (u + 1)/n.

Before the next theorem, we recall the definitions of paired and self-paired suborbital graphs as follows. Let G be a group acting transitively on a nonempty set X. Suppose that G (v, w) and G(w, v) are suborbital graphs for the group G equipped with the orbits G(v, w) and G(w, v) in X x X, respectively. We can see that G(w, v) is just the graph G(v, w) with arrows reversed. We say that the graphs are paired. If G(v, w) = G(w, v), we have G(v, w) = G(w, v). Then the graph consists of pairs of oppositely directed edges. In this case, the graph G(v, w) is called a self-paired suborbital graph. Refer to [3, Corollary 3]; the suborbital graph [[??].sub.u,n] of [??] is self-paired if and only if [u.sup.2] [equivalent to] [+ or -] 1 mod n. This fact can be applied to [[??].sub.u,n]. Now, we are ready to prove the forest conditions for [[??].sub.u,n].

Theorem 20. [[??].sub.u,n] is a forest if and only if it contains no triangles, that is, [u.sup.2] [+ or -] u + 1 [not equivalent to] 0 mod n.

Proof. For every n [less than or equal to] 2, we can see that [F.sub.u,n] = [F.sub.-u,n], so [[??].sub.u,n] = [F.sub.u,n]. Thus, this case is clear by Lemma 5. We then assume that n >2. Of course, the forward is trivial, so only the converse needs proof. Suppose that [u.sup.2] [+ or -] u + 1 [not equivalent to] 0 mod n. We will show that [[??].sub.u,n] does not contain any circuit. On the contrary, we assume that [[??].sub.u,n] contains a circuit C. Since [[??].sub.0] (n) acts transitively on edges of Fun, see [3, Theorem 4], we may suppose that C contains the edge [infinity] [right arrow] u/n. Further, we can apply Proposition 14 to suppose that 0 < u/n < 1. By using Proposition 15 with the fact that no edges of F cross in [H.sup.2], we can show that every vertex of [[??].sub.u,n] in the interval [0, 1] is not adjacent to vertices outside the interval except [infinity]. Then the circuit C lies in the strip 0 [less than or equal to] Re(z) [less than or equal to] 1.

Case 1. [[??].sub.u,n] is self-paired, that is, [u.sup.2] [equivalent to] [+ or -] 1 mod n.

Firstly, we consider the simple case, [u.sup.2] [equivalent to] 1 mod n. With this condition, [1, Corollary 3.3] implies that [F.sub.u,n] and [F.sub.-u,n] are paired. They are the same graph but arrows reversed. Thus, [[??].sub.u,n] is a forest if and only if [F.sub.u,n] is a forest. Therefore, Lemma 5 implies that [[??].sub.u,n] contains no circuits.

In the case [u.sup.2] [equivalent to] -1 mod n, we can check easily by using Lemma 13 that u/n and (n - u)/n are the only two vertices of [[??].sub.u,n] in the interval [0, 1] adjacent to [infinity]. Then the circuit C must contain the vertices u/n and (n - u)/n. This means that if we leave out the vertex [infinity] from C, we obtain a path C - {[infinity]} joining u/n and (n - u)/n where every vertex in the path is a vertex in the interval [0, 1]. We see that u/n and (n - u)/n are on the different side of the line Re(z) = 1/2. Since u [not equivalent to] [+ or -] 1 mod n, Lemma 18 implies that there are not adjacent vertices of the graph [[??].sub.u,n] belonging in the different sides of the line Re(z) = 1/2.1/2 is not a vertex of [[??].sub.u,n] because n > 2. Then the path C - {[infinity]} cannot occur. This is a contradiction. Hence [[??].sub.u,n] has no circuits.

Case 2. [[??].sub.u,n] is not self-paired, that is, [u.sup.2] [not equivalent to] [+ or -] 1 mod n.

In this case, we can see easily that u [not equivalent to] [+ or -] 1 mod n, so Lemma 18 can be applied. Further, there are only four vertices of [[??].sub.u,n] inducing four edges in the strip 0 [less than or equal to] Re(z) [less than or equal to] 1 incident to [infinity]. We can see that [infinity] [right arrow] u/n and u'/n [right arrow] [infinity], where 1 [equivalent to] -uu' mod n, are two of these four edges belonging to [F.sub.u,n]. Under the hyperbolic reflection v [??] -[bar.v] and the translation v [??] v + 1, we obtain the other two edges [infinity] [right arrow] (n-u)/n and (n-u')/n [right arrow] [infinity] belonging to the graph [F.sub.-u,n].

We separate this case into two subcases. That is, u/n and u'/n are on the same side of the line Re(z) = 1/2, and the other case is that they are on the different sides. From Propositions 14 and 15, we know that [mathematical expression not reproducible]. Then we may assume that (u/n) < (u'/n); if not, we certainly obtain that (n-u)/n < (n-u')/n, so we can consider [[??].sub.n-u,n] instead.

Before proving Case 2, we need to construct a semi-infinite path in [[??].sub.u,n]. Since gcd(w, n) = 1, we have ux + ny = 1 for some x, y [member of] Z. Then ux [equivalent to] 1 mod n, so [u.sup.2] - (ux)([u.sup.2] + 1) + 1 [equivalent to] 0 mod n. We can choose a positive integer k < n such that k [equivalent to] -x([u.sup.2] + 1) mod n. Hence [u.sup.2] + ku + 1 [equivalent to] 0 mod n. Since [[??].sub.u,n] is not self-paired and does not contain triangles, we have 1 < k < n. Now, let

[mathematical expression not reproducible]. (7)

We see that [phi] [member of] [[??].sub.0] (n) such that [phi] ([infinity]) = u/n and [phi] ((u + k)/n) = [infinity]. Then the edge [[phi].sup.-1] ([infinity] [right arrow] u/n) = (u + k) / n [right arrow] [infinity] belongs to [[??].sub.u,n]. One can show that u' = u + k.

We now let [v.sub.1] = u/n and define [v.sub.j] = [phi] ([v.sub.j-1]) for every j [greater than or equal to] 2. By Lemma 19, [phi] is a strictly increasing function on the interval (-[infinity], (u + k)/n) such that <p((u + x)/n) < (u+1)/n for every x < 1 < k. Then we obtain a strictly increasing sequence {[v.sub.j]} of vertices of [[??].sub.u,n] in the interval [u/n, (u + 1)/n). Since [infinity] [right arrow] u/n is an edge in [[??].sub.u,n], we obtain the semi-infinite path [v.sub.1] [right arrow] [v.sub.2] [right arrow] [v.sub.3] [right arrow] ... contained in [[??].sub.u,n]. From now, if the direction of an edge is not clear, we will use the notation [??] to refer to either of the arrows [right arrow] or [left arrow]. We are ready to provide the proof of Case 2.

In the case that u/n and u'/n are on the same side of the lineRe(z) = 1/2, we obtain that (n-u)/n and (n-u')/n are on the other side. Thus, we obtain by Lemma 18 that the circuit C contains the vertex u'/n and does not contain (n - u)/n and (n - u')/n. Recall that [v.sub.1] = u/n < u'/n = (u + k)/n.

Since C is a circuit containing [v.sub.1], there are finitely many vertices from the sequence {[v.sub.j]} belonging to the circuit C. Hence there is the greatest integer i such that [v.sub.i] is a vertex in C. Then there is an edge in C incident to v; and another vertex v of [[??].sub.u,n] such that v > [v.sub.i]. By Corollary 16, no edges of [[??].sub.u,n] cross in [H.sup.2], so [v.sub.j] < v [less than or equal to] (u + k)/n for every j [member of] N. If v = (u + k)/n, we have [phi](v) = [infinity]. Then the edge [v.sub.i] [??] v crosses the edge [phi] ([v.sub.i]) [??] [phi] (v) in [H.sup.2]. If v < (u + k)/n, we apply Lemma 19. Since the function [phi] is strictly increasing on the interval (-[infinity], (u + k)/n), we still obtain that the edge [v.sub.i] [??] v crosses the edge [phi] ([v.sub.i]) [??] [phi](v) in [H.sup.2]. This is a contradiction. Therefore, there is no such circuit C.

Next, we prove the remaining case; that is, u/n and u'/n are on the different sides of the line Re(z) = 1/2. In this case, we have u/n, (n - u')/n < 1/2 < '/n, (n - u)/n. Since u(n - u') [equivalent to] -uu [equivalent to] 1 mod n, [3, Corollary 2] implies that [[??].sub.u,n] and [[??].sub.n-u',n] are paired suborbital graphs. Thus, [[??].sub.u,n] and [[??].sub.n-u',n] are also paired. Hence we may suppose that u/n < (n - u')/n; if not, we can prove on the graph [F.sub.n-u',n] together with the compatible mapping <p instead. We now have u/n < (n- u')/n < 1/2 < u'/n < (n- u)/n.

We know that the circuit C contains the edge [infinity] [right arrow] u/n. Then Lemma 18 implies that it also contains the vertex (n-u')/n. More precisely, it contains the edge (n-u')/n [right arrow] [infinity]. Since the graph [[??].sub.u,n] does not contain triangles, the vertices u/n and (n - u')/n are not adjacent. Then there is an edge u/n [??] of C such that u/n < v <{n - u')/n. Next, we consider the path (n - u')/n [right arrow] [infinity] u/n [??] v in the circuit C. Its image under [[phi].sup.-1] is the path [[phi].sup.-1] ((n-u')/n) [right arrow] u'/n [right arrow] [infinity] [??] [[phi].sup.-1] (v) in the circuit [[phi].sup.-1] (C). We know that 1/2 < u'/n and 1/2 is not a vertex of [[??].sub.u,n]. Then we obtain by Lemma 18 that the circuit [[phi].sup.-1] (C) must belong to the right side of the line Re(z) = 1/2. Since u'/n and [[phi].sup.-1] (v) are adjacent to [infinity], Corollary 16 implies that [[phi].sup.-1] ((n-u')/n) lies between u'/n and [[phi].sup.-1] (v). We see that u'/n is the least vertex on the right side of the line Re(z) = 1/2 adjacent to [infinity]. Hence u'/n < [[phi].sup.-1] ((n-u')/n) < [[phi].sup.-1] (v). By Lemma 19, [phi] is increasing on the interval (u'/n, +[infinity]). This induces a contradiction to the inequality v <(n- u')/n, that is, (n - u')/n = [phi][[phi].sup.-1] ((n - u')/n) < [phi][[phi].sup.-1] (v) = v. Therefore, the circuit C does not exist.

From the proof in Cases 1 and 2, we have shown that if [[??].sub.u,n] does not contain triangles, it does not contain circuits. Consequently, [[??].sub.u,n] is a forest if and only if it contains no triangles.

By the similar reasons used in the case of modular, we obtain the following corollaries immediately. If [u.sup.2] [+ or -] u + 1 [not equivalent to] 0 mod n, the previous theorem implies that the graphs become forests. Thus, they are 2-chromatic. If [u.sup.2] [+ or -] u + 1 [equivalent to] 0 mod n, the graphs contain triangles. Then their chromatic numbers are greater than 2. Finally, Corollary 17 guarantees that they are 3-chromatic.

Corollary 21. Let [chi] be the chromatic number of [[??].sub.u,n]; then,

(1) [chi] = 2 if [u.sup.2] [+ or -] u + 1 [not equivalent to] 0 mod n,

(2) [chi] = 3 if [u.sup.2] [+ or -] u + 1 [equivalent to] 0 mod n.

Corollary 22. Let [chi] be the chromatic number of [[??].sub.u,n]; then,

(1) [chi] = 2 if [u.sup.2] [+ or -] u + 1 [not equivalent to] 0 mod n,

(2) [chi] = 3 if [u.sup.2] [+ or -] u + 1 [equivalent to] 0 mod n.

https://doi.org/ 10.1155/2017/7458318

Competing Interests

The authors declare that there are no competing interests regarding the publication of this paper.

Acknowledgments

This research was supported by Chiang Mai University and Thailand Research Fund.

References

[1] G. A. Jones, D. Singerman, and K. Wicks, "The modular group and generalized Farey graphs," in Groups-St. Andrews 1989, C. M. Campbell and E. F. Robertson, Eds., vol. 2, pp. 316-338, Cambridge University Press, Cambridge, UK, 1991.

[2] C. C. Sims, "Graphs and finite permutation groups," Mathematische Zeitschrift, vol. 95, pp. 76-86, 1967

[3] S. Kader and B. O. Guler, "On suborbital graphs for the extended modular group r," Graphs and Combinatorics, vol. 29, no. 6, pp. 1813-1825, 2013.

[4] M. Akbas, "On suborbital graphs for the modular group," The Bulletin of the London Mathematical Society, vol. 33, no. 6, pp. 647-652, 2001.

[5] L. Kocic and L. Stefanovska, "A property of Farey tree," in Numerical Analysis and Its Applications, Z. Li, L. Vulkov, and J. Was'niewski, Eds., vol. 3401 of Lecture Notes in Computer Science, pp. 345-351, Springer, 2005.

[6] N. Moshchevitin and A. Zhigljavsky, "Entropies of the partitions of the unit interval generated by the Farey tree," Acta Arithmetica, vol. 115, no. 1, pp. 47-58, 2004.

[7] G. Howell, A normalised distance function considered over the partition of the unit interval generated by the points of the Farey tree [Ph.D. thesis], Cardiff Univers

Wanchai Tapanyo and Pradthana Jaipong

Department of Mathematics, Chiang Mai University, Chiang Mai 50200, Thailand

Correspondence should be addressed to Pradthana Jaipong; pradthana.j@cmu.ac.th

Received 20 October 2016; Revised 19 January 2017; Accepted 20 February 2017; Published 5 March 2017

Academic Editor: Francisco B. Gallego

Caption: FIGURE 1: Example of edges of [G.sub.u,n].

Caption: FIGURE 2: Farey graph F.
COPYRIGHT 2017 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2017 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Tapanyo, Wanchai; Jaipong, Pradthana
Publication:Journal of Mathematics
Article Type:Report
Date:Jan 1, 2017
Words:6803
Previous Article:A Mixed Discontinuous Galerkin Approximation of Time Dependent Convection Diffusion Optimal Control Problem.
Next Article:Approximate Solution of Perturbed Volterra-Fredholm Integrodifferential Equations by Chebyshev-Galerkin Method.
Topics:

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