Abstract

A graph is called cycle books if consists of m cycles with a common path . Figueroa-Centeno, Ichishima, and Muntaner-Batle conjecture that the graph is super edge-magic total if and only if is even or . In this article, we prove this conjecture for  ≥ 36 and  = 0 mod (2).

1. Introduction

For undefined terms and notations in this study, we follow Chartrand, Lesniak, and Peng [1]. Let be a graph with and be a set of vertices and edges, respectively. A graph is called a if has and number of vertices and edges, respectively. Kotzig and Rosa [2] defined that an edge-magic total labeling of is a bijective function f: {1, 2, ..., p + q}, such that f(w) + f(wz) + f(z) = k for any edge . Moreover, a super edge-magic total labeling is an edge-magic total labeling , such that  = {1, 2, ..., p}.

The notion of edge-magic total labeling of a graph is generalized to edge-antimagic total labeling of graphs. Let and be integers. Let . If forms an arithmetic sequence starting from with common difference , then is called . Moreover, if  = {1, 2, ..., p}, then is called . Notice that when β = 0, the of is the usual edge-magic total labeling of with f() + f(wz) + f(z) =  for any edge .

One of the most popular problems in the theory of graph labeling is super edge-magic total labeling of tree. Enomoto et al. [3] proposed the following conjecture.

Tree conjecture [3]: every tree is .

The tree conjecture is still an open problem; however, some authors proved that tree conjecture is true for some classes of tree. For example, Bhatti, Javaid and Hussain [4] and Raheem et al. [5] proved that tree conjecture is true for subdivision of caterpillar. Javaid, Bhatti, and Aslam [6] proved that tree conjecture is true for subdivision of stars. Other authors who studied tree conjecture can be found in Gallian [7].

Another popular problem in the theory of graph labeling is super edge-magic total labeling of a cycle book. A cycle book graph is constructed from some cycles either with the same or different order. Let be any positive integer and let be the cycles of order . A graph is called -cycle books if consists of cycles with a common path . For , we define to be a cycle . From now on, the graphs, -cycle books is denoted by .

Marr and Wallis ([8], Research problem 2.7, p.39) proposed the following problem.

Problem 1. Are all graphs edge-magic total (super edge-magic total)?
Graph is constructed from some cycles of the same order. Swita et al. [9] contructed a graph from some cycles with different orders. A graph is constructed from some cycles C_a and C_b with a common path , a path of order with , and as the positive integers.

Problem 2. Are all graphs edge-magic total (super edge-magic total)?
Both Problems 1 and 2 are interesting problems for at least the following two reasons. First reason is the solutions of Problems 1 and 2 that can be used to construct the secret sharing scheme in information technology. Reddy and Basha [10] and Imron et al. [11] used edge-magic total labeling of catepilar graphs to construct the secret sharing scheme. Baskoro, Simanjuntak, and Adithia [12] used edge-magic total labeling of star graphs to construct the secret sharing scheme.
The second reason is both Problems 1 and 2 provide a challenging problem for the researchers, since they are open problems. Swita et al. [9] proved Problem 2 for or for any integer . MacDougall and Wallis [13] proved Problem 2 for that a graph is a super edge-magic total labeling. Let . Notice that is a chord of cycle . Thus, is a chord of graph . Using Kotzig array, Singgih [14, 15] proposed a new method to construct an edge-magic total labeling (super edge-magic) of graph cycle with chords, each of length , from an edge-magic total labeling (super edge-magic) of graph , where and are the positive integers.
Berkman, Parnas and Roditty [16], Enomoto et al. [3], Kotzig and Rosa [2], and Godbold and Slater [17] are among others authors that discuss Problem 1 for . For , Problem 1 is an open problem; however, some authors provided a partial solution. Figueroa-Centeno, Ichishima, and Muntaner-Batle [18] proved that is an edge-magic total. Furthermore, they proved that B[(4, m), 2] is not super edge-magic total for and  = 4, but B[(4, m), 2] is super edge-magic total for  = 2, 5, 6, 8, 10, 11. Moreover, they made the following conjecture.
Cycle book conjecture [18]: the graph B[(4, m), 2] is super edge-magic total if and only if m is even or .
Gallian [7] reported that Yuansheng et al. [19] proved this conjecture for is even in Ars Combinatoria, 93 (2009) 431–438. A study [20] contains the abstract of Yuansheng et al. [19] and claims that Yuansheng et al. proved the cycle book conjecture is true for is even. The study [19] is the same as that of Gallian [7]. We trace this reference, and we find that this reference is neither in the table of contents of Ars Combinatoria, 93 (2009), nor in the table of contents Ars Combinatoria from 1995 up to 1999. Hence, we assume that the article of Yuansheng et al. is unpublished. Therefore, it is reasonable to publish this article. Thus, this study proves the cycle book conjecture for  ≥ 36 and  = 0 mod (2). The solution of cycle book conjecture is available from the author for 12 ≤  ≤ 34 and  = 0 mod (2).

2. Preliminary Notes

In this section, we provide some previous results on super edge-magic total labeling of a graph. Figuero-Centeno, Ichisma, and Mutaner-Batle [18] proved some necessary conditions for super edge-magic total labeling of a graph. We need them to prove the main results of this study. First, we define some notations in the following definition.

Definition 1. Let be a graph , , and . We define the vertex set and the edge set .
The element of and the edge are called the common vertices and common edge of the copies of , respectively.
The graph B[(4,m), 2] in Definition 1 is shown in Figure 1 and the graph is shown in Figure 2.

Figure 1 

Graph .

Figure 2 

Graph .

Theorem 1 (see [18]). Let be a graph, such that and . Then, is super edge-magic total if and only if there exists a bijective function , such that the set or any edge consists of consecutive integers. In such a case, extends to a super edge-magic total labeling of with magic constant where and .

Theorem 2 (see [18]). Let be a graph, such that and and be a super edge-magic total labeling of . Let and . Then, . In particular, deg .

Theorem 3 (see [18]). Let be a graph , such that and . If is super edge-magic total labeling, then .

The following theorem is derived from the proof of Theorem 3 in [3]. For self-contained of this article, we rewrite the proof again.

Theorem 4 (see [18]). Let be a graph in Definition 1 and let be the common edges of all cycles in . If is super edge-magic total labeling, then .

Proof. Let be a graph in Definition 1. Let , and . We first notice that and Moreover, .
Let A = XY and B = Z W. By Theorem 2, we have or . The last equality reduces to , since , and . Thus, . We substitute to the last equation, and we have the following equation.By the equation (1) and in Theorem 3, we conclude that . Hence, the theorem.

3. Proof of Cycle Book Conjecture for Is Even

In this section, we prove that the cycle book conjecture is true if is even and

Theorem 5. Let be the graph in Definition 1 with, is an even integer, , and let be an edge-magic total labeling of Let or any edge and Then, is a super edge-magic total if and only if(i)(ii)(iii) is a set of consecutive integers(iv)

Proof. Let be the graph with , and let be a super edge-magic total. Note that and Let be an edge-magic total labeling of . If f is a super edge-magic total labeling of , then the conditions (i) and (ii) follow from Theorems 4 and 3, respectively, and the conditions (iii) and (iv) follow from Theorem 1.
Let satisfies the conditions (i), (ii), (iii), and (iv). By (i) and (ii), we conclude thatThe pair () is one of the solutions of equation (2) with  =  and By this solution, we define the bijection , such that and as follows. Case 1:  We define Case 1.1:  We define Next, we will show that is a set of consecutive integers with . Recall that and . Let and . Let . By equations (3) and (5), we conclude that . Hence, . Let and . Let and . By equations (5) and (7), we conclude that . Hence, . Let = , and . Let and . By equations (3) and (5), we conclude that . Hence, . Let  = ,  = , and . By equations (5) and (6), we conclude that . By equations (5) and (8), we conclude that . Hence, . Let , and . By equations (5) and (12), we conclude that . Hence, . Let  = ,  = , and . By equations (5) and (10), we conclude that . Hence, . Let and . By equations (3) and (4), we conclude that . Hence, . Let ,  = , and . By equations (5) and (15), we conclude that . Hence, . Let  = ,  = , and . By equations (5) and (16), we conclude that . Hence, . Let  = ,  = , and . By equations (5) and (18), we conclude that . Hence, . Let  = ,  = , and . By equations (5) and (17), we conclude that . Hence, . Let  = ,  = , and . By equations (5) and (11), we conclude that . Hence, . Let  = ,  = , and . By equations (5) and (14), we conclude that . Hence, . Let  = ,  = , and . By equations (5) and (13), we conclude that . Hence, . Let  = ,  = , and . By equations (4) and (7), we conclude that . Hence, . Let  =  = , and . By equations (4) and (10), we conclude that . Hence, . Let  = ,  = , and . By equations (4) and (11), we conclude that . Hence, . Let  = ,  = , and . By equations (4) and (12), we conclude that . Hence, . Let ,  = , and . By equations (5) and (9), we conclude that . Hence, . Let  = ,  = , and . By equations (4) and (8), we conclude that . By equations (4) and (6), we conclude that . Hence, . Let  = ,  = , and . By equations (4) and (13), we conclude that ., . Hence, . Let  = ,  = , and . By equations (4) and (15), we conclude that . Hence, . Let  = ,  = , and . By equations (4) and (14), we conclude that . Hence, . Let  =  = , and . By equations (4) and (16), we conclude that . Hence, . Let  =  = , and . By equations (4) and (17), we conclude that . Hence, . Let  =  = , and . By equations (4) and (9), we conclude that . Hence, . Let  =  = , and . By equations (4) and (18), we conclude that . Hence, . Next, we will show that consists of consecutive integers. Simple counting shows that , and ,  =  We arrange the term of in Table 1. We observe from Table 1 that  =  consists of consecutive integers. In addition, we will show that consists of consecutive integers. Simple counting shows that  =  ,  =  =  , and . By these information, we arrange the terms of in Table 2. We observe from Table 2 that  =  consists of consecutive integers. Let S =  . We will show that consists of consecutive integers with . Let                     Notice that . Moreover, consists of consecutive integers. Simple counting shows that consists of consecutive integers with Thus, by Theorem 1, we conclude that is super edge-magic total. Moreover, by , we have for all . Hence, the theorem in this case. Case 1.2:  We define It can be proved in the same lines as previous proof of Case 1.1 that is a set of q consecutive integers with . Thus, by Theorem 1, we conclude that is super edge-magic total. Hence, the theorem in this case. Case 1.3:  We define It can be proved in the same lines as the previous proof of Case 1.1 that is a set of q consecutive integers with . Thus, by Theorem 1, we conclude that is super edge-magic total. Hence, the theorem in this case. Case 2:  Case 2.1:  We define It can be proved in the same lines as the previous proof of Case 1.1 that is a set of consecutive integers with . Thus, by Theorem 1, we conclude that is super edge-magic total. Hence, the theorem in this case. Case 2.2:  We define It can be proved in the same lines as the previous proof of Case 1.1 that is a set of consecutive integers with . Thus, by Theorem 1, we conclude that is super edge-magic total. Hence, the theorem in this case.  Case 2.3:  We define It can be proved in the same lines as previous proof of Case 1.1 that is a set of consecutive integers with . Thus, by Theorem 1, we conclude that is super edge-magic total. Hence, the theorem.