Chromatically unique 6-bridge graph θ(a, a, a, b, b, c)

N.S.A. Karim^a , R. Hasni^b , Gee-Choon Lau^c

Universiti Pendidikan Sultan Idris, 35900 Tanjong Malim, Perak, Malaysia

yaya kulaan@yahoo.com, hroslan@umt.edu.my, geeclau@yahoo.com

For a graph G, let P(G, λ) denote the chromatic polynomial of G. Two graphs G and H are chromatically equivalent if they share the same chromatic polynomial. A graph G is chromatically unique if for any graph chromatically equivalent to G is isomorphic to G. In this paper, the chromatically unique of a new family of 6-bridge graph θ(a, a, a, b, b, c) where 2 ≤ a ≤ b ≤ c is investigated.

Keywords: chromatic polynomial, chromatically unique, 6-bridge graph

Mathematics Subject Classification : 05C15

DOI: 10.5614/ejgta.2016.4.1.6

1. Introduction

All graphs considered here are simple graphs. For such a graph G, let P(G, λ) denote the chromatic polynomial of G. Two graphs G and H are chromatically equivalent (or simply χ−equivalent), denoted by G ∼ H, if P(G, l) = P(H, l). A graph G is chromatically unique (or simply χ−unique) if for any graph H such as H ∼ G, we have H ∼= G, i.e, H is isomorphic to G.

Received: 27 April 2015, Revised 25 February 2016, Accepted: 13 March 2016.

^aDepartment of Mathematics, Faculty of Science and Mathematics,

^bSchool of Informatics and Applied Mathematics, Universiti Malaysia Terengganu,

²¹⁰³⁰ Kuala Terengganu, Malaysia

^cFaculty of Computer and Mathematical Sciences, University Teknologi MARA (Segamat Campus), 85000 Johor, Malaysia

The chromaticity of a graph G refers to questions about the chromatic equivalence class or chromatic uniqueness of G. For terminologies and notations which are not explained here, the reader is referred to [6, 20].

Let k be an integer with k ≥ 2 and let a1, a2, . . . , a^k be positive integers with aⁱ +a^j ≥ 3 for all i, j and 1 ≤ i ≤ j ≤ k. Let θ(a1, a2, . . . , ak) denote the graph obtained by connecting two distinct vertices with k independent (internally disjoint) paths of length a1, a2, . . . , ak, respectively. The graph θ(a1, a2, . . . , ak) is called a multi-bridge (more spesifically k-bridge) graph.

Given positive integers a1, a2, . . . , ak, where k ≥ 2, what is the necessary and sufficient condition on a1, a2, . . . , a^k for θ(a1, a2, . . . , ak) to be chromatically unique? Many papers [4, 5, 14, 15] have been published on this problem, but it is still far from being completely solved.

For two non-empty graphs G and H, an edge-gluing of G and H is a graph obtained from G and H by identifying one edge of G with one edge of H. For example, the graph K⁴ − e (obtained from K⁴ by deleting one edge) is an edge-gluing of K³ and K3. There are many edge-gluings of G and H. Let ge(G, H) denote the family of all edge-gluings of G and H. Zykov [25] showed that any member of ge(G, H) has chromatic polynomial

\[\frac{P(G,\lambda)P(H,\lambda)}{(\lambda(\lambda-1))}\tag{1}\]

Thus any two members in ge(G, H) are χ-equivalent.

For any integer k ≥ 2 and non-empty graphs G0, G1, · · · , Gk, we can recursively define

\[g_e(G_0, G_1, \cdots, G_k) = \bigcup_{0 \le i \le k} g_e(G_i, G')\] (2)

where G⁰ ∈ ge(G0, · · · , Gi−1, Gi+1, · · · , Gk).

Each graph in ge(G0, G1, · · · , Gk) is also called an edge-gluing of G0, G1, · · · , Gk. By (1), any two graphs in ge(G0, G1, · · · , Gk) are χ-equivalent.

Let C^p denote the cycle of order p. It was shown independently in [19] and [21] that if G is χ-equivalent to a graph in ge(Cⁱ⁰ , Cⁱ¹ , · · · , C^ik ), then G ∈ ge(Cⁱ⁰ , Cⁱ¹ , · · · , C^ik ). In other words, this family is a χ-equivalence class.

A 2-bridge graph is simply a cycle graph, which is χ−unique. Chao and Whitehead Jr. [2] showed that every 3-bridge graph θ(1, a2, a3) (or a theta graph) is χ−unique. Loerinc [18] extended the above result to all 3-bridge graphs by showing that all 3-bridge graphs (or generalized θ-graph) are χ-unique. Assume therefore that k ≥ 4. It is clear that if aⁱ = 1 for some i say i = 1, then θ(a1, a2, · · · , ak) is a member of ge(C^a2+1, C^a3+1, · · · , C^ak+1) and thus θ(a1, a2, · · · , ak) is not χ-unique. Assume therefore that aⁱ ≥ 2 for all i. For k = 4, Chen et al. [3] found that θ(a1, a2, a3, a4) may not be χ-unique.

Theorem 1.1. (Chen et al. [3]) (a) Let a1, a2, a3, a⁴ be integers with 2 ≤ a¹ ≤ a² ≤ a³ ≤ ak. Then θ(a1, a2, a3, a4) is χ-unique if and only if (a1, a2, a3, a4) 6= (2, b, b + 1, b + 2) for any integer b ≥ 2.

(b) The χ-equivalence class of θ(2, b, b + 1, b + 2) is

\[\{\theta(2,b,b+1,b+2)\} \cup g_e(\theta(3,b,b+1),C_{b+2}).\]

Thus the problem of the chromaticity of θ(a1, a2, · · · , ak) has been completely settled for k ≤ 4.

The results on the chromaticity of some families of 5-bridge graphs have been obtained by Bao and Chen [1], Li and Wei [17], Li [16], Khalaf [7], Khalaf and Peng [8], Khalaf et al. [13]. Ye [23, 24] proved that θ(2, 2, 2, 2, a, b) where 3 ≤ a + 1 ≤ b and θ(2, 2, . . . , 2, a, b) where 3 ≤ a ≤ b and k ≥ 5 are χ-unique, respectively. Khalaf and Peng [9] also proved that θ(a, a, . . . , a, b) for a ≤ b is χ-unique. The study on the chromaticity of 6-bridge graphs, θ(a1, a2, a3, a4, a5, a6) where a1, a2, a3, a4, a5, a⁶ assume exactly two distinct values and θ(3, 3, 3, 3, b, c) was done by Khalaf and Peng [10, 12]. Later on, Khalaf and Peng in [7, 11] solved the chromaticity of two types of 6 bridge graph θ(a1, a2, a3, a4, a5, a6) where a1, a2, a3, a4, a5, a⁶ assume exactly three distinct values, that is, the graphs θ(a, a, a, b, c, c) and θ(a, a, a, a, b, c), respectively. The aim of this paper is to investigate the chromaticity of another type of such graphs, that is, 6-bridge graphs θ(a, a, a, b, b, c) (see Figure 1).

Figure 1. θ(a, a, a, b, b, c)

2. Preliminary Results and Notations

In this section, we cite some results to be used in this paper. The following result is due to Xu et al. [22].

Lemma 2.1. For \[k \ge 4\], \(\theta(a_1, a_2, ..., a_k)\) is \(\chi\)-unique if \(k - 1 \le a_1 \le a_2 \le ... \le a_k\).

Li and Wei [17] established that the 5-bridge graph θ(2, 2, 2, a, b) is χ-unique if and only if (a, b) 6= (3, 4). Ye [23] extended the above result to any k-bridge graph θ(2, 2, . . . , 2, a, b) with b ≥ a ≥ 3 and k ≥ 5. For each positive integer h, the graph G(h) is obtained from G by replacing each edge of G by a path of length h, respectively and is called the h-uniform subdivision of G. Xu et al. [21] showed that any h-uniform subdivision of θ^k denoted as θk(h), is χ-unique, as stated in the following theorem.

Lemma 2.2. (Xu et al. [21]) For k ≥ 2, the graph θk(h) is χ-unique.

Dong et al. [5] proved the following result.

Lemma 2.3. (Dong et al. [5]) If \(2 \le a_1 \le a_2 \le ... \le a_k < a_1 + a_2\) where \(k \ge 3\), then the graph \(\theta(a_1, a_2, ..., a_k)\) is \(\chi\)-unique.

Let \(k, a_1, a_2, \dots, a_k \in N\), where N is natural number set and \(G = \theta(a_1, a_2, \dots, a_k)\). Then (see [4])

\[P(G,\lambda) = \frac{1}{\lambda^{k-1}(\lambda-1)^{k-1}} \prod_{i=1}^{k} ((\lambda-1)^{a_i+1} + (-1)^{a_i+1}(\lambda-1))\]\[+ \frac{1}{\lambda^{k-1}} \prod_{i=1}^{k} ((\lambda-1)^{a_i} + (-1)^{a_i}(\lambda-1))\]

Let \(\lambda = 1 - x\), then

\[P(G, 1-x) = \frac{(-1)^{a_1+a_2+\cdots+a_k+1}}{(1-x)^{k-1}} \left( x \prod_{i=1}^k (x^{a_i} - 1) - \prod_{i=1}^k (x^{a_i} - x) \right)\]\[= \frac{(-1)^{e(G)+1}}{(1-x)^{e(G)-v(G)+1}} \left( x \prod_{i=1}^k (x^{a_i} - 1) - \prod_{i=1}^k (x^{a_i} - x) \right)\]

where \(e(G) = \sum_{i=1}^k a_i\) and \(v(G) = \sum_{i=1}^k a_i - k + 2\). Also define Q(G, x) for any graph G and real number x as:

\[Q(G,x) = (-1)^{e(G)+1}(1-x)^{e(G)-v(G)+1}P(G,1-x).\]

Then we have

Lemma 2.4. (Dong et al. [5]) For any \(k, a_1, a_2, ..., a_k \in N\),

\[Q(\theta(a_1, a_2, \dots, a_k), x) = x \prod_{i=1}^k (x^{a_i} - 1) - \prod_{i=1}^k (x^{a_i} - x).\]

Lemma 2.5. (Dong et al. [5]) For any graphs G and H,

• 1. If \(H \sim G\), then Q(H, x) = Q(G, x),
• 2. If Q(H,x) = Q(G,x) and v(H) = v(G), then \(H \sim G\).

Lemma 2.6. (Dong et al. [5]) Suppose that \(\theta(a_1, a_2, ..., a_k) \sim \theta(b_1, b_2, ..., b_k)\) where \(k \geq 3\), \(2 \leq a_1 \leq a_2 \leq ... \leq a_k\) and \(2 \leq b_1 \leq b_2 \leq ... \leq b_k\), then \(a_i = b_i\) for all i = 1, 2, ..., k.

Lemma 2.7. (Dong et al. [5]) Let \(H \sim \theta(a_1, a_2, \dots, a_k)\) where \(k \geq 3\) and \(a_i \geq 2\) for all i, then one of the following is true:

(i) \[H \cong \theta(a_1, a_2, \ldots, a_k)\],

(ii) \(H \in g_e(\theta(b_1, b_2, \dots, b_t), C_{b_{t+1}+1}, \dots, C_{b_k+1})\), where \(3 \le t \le k-1\) and \(b_i \ge 2\) for all \(i = 1, 2, \dots, k\).

Lemma 2.8. (Dong et al. [5]) Let \(k, t, b_1, b_2, \ldots, b_k \in N\) where \(3 \le t \le k-1\) and \(b_i \ge 2\) for all \(i = 1, 2, \ldots, k\). If \(H \in g_e(\theta(b_1, b_2, \ldots, b_t), C_{b_{t+1}+1}, \ldots, C_{b_k+1})\), then

\[Q(H,x) = x \prod_{i=1}^{k} (x^{b_i} - 1) - \prod_{i=1}^{t} (x^{b_i} - x) \prod_{i=t+1}^{k} (x^{b_i} - 1).\]

Lemma 2.9. (Koh & Teo [14]) If \(G \sim H\), then

• \((i) \ v(G) = v(H),\)
• (ii) e(G) = e(H),
• (iii) g(G) = g(H),
• (iv) G and H have the same number of shortest cycle.

where v(G), v(H), e(G), e(H), g(G) and g(H) denote the number of vertices, the number of edges and the girth of G and H, respectively.

Lemma 2.10. (Khalaf & Peng [11]) A 6-bridge graph \(\theta(a_1, a_2, ..., a_6)\) is \(\chi\)-unique if the positive integers \(a_1, a_2, ..., a_6\) assume exactly two distinct values.

3. Main Results

In this section, we present our main result on the chromaticity of 6-bridge graph \(\theta(a, a, a, b, b, b, c)\).

Theorem 3.1. The graph 6-bridge \(\theta(a, a, a, b, b, c)\), where \(a \le b \le c\), is \(\chi\)-unique.

Proof. Let G be a 6-bridge graph of the form \(\theta(a,a,a,b,b,c)\) where \(2 \le a \le b \le c\). By Lemma 2.3, G is \(\chi\)-unique if c < 2a. Suppose \(c \ge 2a\) and \(H \sim G\). We shall solve Q(G) = Q(H) to get all solutions. Let the lowest remaining power and the highest remaining power be denoted by l.r.p. and h.r.p., respectively. By Lemma 2.9, g(G) = g(H) = 2a and H has the same number of shortest cycles as G. Thus, we have

\[3a + 2b + c = b_1 + b_2 + b_3 + b_4 + b_5 + b_6 \tag{3}\]

By Lemmas 2.6 and 2.7, we have three cases to consider, (A) \(H \in g_e \left(\theta(b_1,b_2,b_3),C_{b_4+1},C_{b_5+1},C_{b_6+1}\right)\) where \(2 \leq b_1 \leq b_2 \leq b_3\) and \(2 \leq b_4,b_5,b_6\) or (B) \(H \in g_e \left(\theta(b_1,b_2,b_3,b_4),C_{b_5+1},C_{b_6+1}\right)\) where \(2 \leq b_1 \leq b_2 \leq b_3 \leq b_4\) and \(2 \leq b_5,b_6\) or (C) \(H \in g_e \left(\theta(b_1,b_2,b_3,b_4,b_5),C_{b_6+1}\right)\) where \(2 \leq b_1 \leq b_2 \leq b_3 \leq b_4 \leq b_5\) and \(2 \leq b_6\).

<u>Case A</u> \(H \in g_e(\theta(b_1,b_2,b_3),C_{b_4+1},C_{b_5+1},C_{b_6+1})\) where \(2 \le b_1 \le b_2 \le b_3\) and \(2 \le b_4,b_5,b_6\). As \(G \cong \theta(a,a,a,b,b,c)\) and \(H \in g_e(\theta(b_1,b_2,b_3),C_{b_4+1},C_{b_5+1},C_{b_6+1})\), then by Lemma 2.8, we have

\[Q(G) = x(x^{a}-1)^{3}(x^{b}-1)^{2}(x^{c}-1) - (x^{a}-x)^{3}(x^{b}-x)^{2}(x^{c}-x),\] \[Q(H) = x(x^{b_{1}}-1)(x^{b_{2}}-1)(x^{b_{3}}-1)(x^{b_{4}}-1)(x^{b_{5}}-1)(x^{b_{6}}-1) - (x^{b_{1}}-x)(x^{b_{2}}-x)(x^{b_{3}}-x)(x^{b_{4}}-1)(x^{b_{5}}-1)(x^{b_{6}}-1).\]

By equation 3, Q(G) = Q(H) yields

\[Q_{1}(G) = 2x^{3a+b+1} + x^{3a+c+1} + x^{3a+3} + 3x^{2a+2b+1} + 6x^{2a+b+c+1} + 6x^{2a+b+3} + 3x^{2a+c+3} + 3x^{2a+1} + 3x^{a+2b+c+1} + 3x^{a+2b+3} + 6x^{a+b+c+3} + 6x^{a+b+1} + 3x^{a+c+1} + 3x^{a+2b+c+1} + 3x^{a+2b+3} + 2x^{b+1} + 2x^{b+c+1} + 2x^{b+5} + x^{c+5} - (2x^{3a+b+2} + x^{3a+c+2} + x^{3a+1} + 3x^{2a+2b+2} + 6x^{2a+b+c+2} + 6x^{2a+b+1} + 3x^{2a+c+1} + 3x^{2a+4} + 3x^{a+2b+c+2} + 3x^{a+2b+1} + 6x^{a+b+c+1} + 6x^{a+b+4} + 3x^{a+c+4} + 3x^{a+2b+c+2} + 3x^{a+2b+1} + 6x^{a+b+c+1} + 6x^{a+b+4} + 3x^{a+c+4} + 3x^{a+1} + x^{2b+c+1} + x^{2b+c+1} + x^{2b+c+4} + 2x^{b+1} + x^{c+1} + x^6),\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Compare the l.r.p. in Q1(G) and the l.r.p. in Q1(H). Thus, a = 2. Therefore, g(G) = g(H) = 2a = 4 and both G and H has three cycles of length 4, respectively. Without loss of generality, we have four cases to consider, (1) b⁴ = b⁵ = b⁶ = 3 or (2) b⁴ = b⁵ = 3, b⁶ 6= 3 or (3) b⁴ = 3, b⁵ 6= 3, b⁶ 6= 3 or (4) b⁴ 6= 3, b⁵ 6= 3, b⁶ 6= 3.

Case 1 b⁴ = b⁵ = b⁶ = 3. Note that there is −3x ^a+1 in Q1(G). Hence, there are another two terms in Q1(H) that are equal to −x 3 . Thus, we have b¹ = b² = 2 or b¹ = b³ = 2 or b² = b³ = 2.

Case 1.1 b¹ = b² = 2. Therefore, H has four cycles of length 4, a contradiction.

Case 1.2 b¹ = b³ = 2. So b² = 2. Therefore, H has six cycles of length 4, a contradiction.

Case 1.3 b² = b³ = 2. So b¹ = 2. Therefore, H has six cycles of length 4, a contradiction.

Case 2 b⁴ = b⁵ = 3, b⁶ 6= 3. Since the girth of H is 4, then b⁶ ≥ 4. Given that H has three cycles of length 4, then b¹ + b² = 4. So b¹ = b² = 2. It follows from equation 3 that 2b + c = b³ + b⁶ + 4. We obtain the following after simplification.

\[Q_{2}(G) = x^{2b+c+3} + 12x^{b+c+5} + 2x^{b+c+1} + 6x^{2b+5} + x^{2b+1} + 8x^{b+7} + 6x^{b+3} + 4x^{c+7} + 3x^{c+3} + x^{9} + 2x^{7} + 3x^{5} - (x^{2b+c+1} + 6x^{b+c+6} + 2x^{b+c+4} + 6x^{b+c+3} + 3x^{2b+6} + x^{2b+4} + 3x^{2b+3} + 2x^{b+8} + 6x^{b+6} + 4x^{b+5} + 2x^{b+1} + x^{c+8} + 3x^{c+6} + 2x^{c+5} + x^{c+1} + 3x^{8} + x^{6}),\] \[Q_{2}(H) = 3x^{b_{3}+b_{6}+5} + x^{b_{3}+b_{6}+1} + x^{b_{3}+10} + 3x^{b_{3}+8} + 3x^{b_{3}+4} + x^{b_{3}+2} + 3x^{b_{6}+9} + 3x^{b_{6}+7} + 3x^{b_{6}+3} + 2x^{10} + 6x^{6} - (3x^{b_{3}+b_{6}+4} + x^{b_{3}+11} + 3x^{b_{3}+7} + 3x^{b_{3}+5} + x^{b_{3}+1} + 2x^{b_{6}+10} + 6x^{b_{6}+6} + x^{b_{6}+1} + 3x^{9} + 3x^{7}).\]

Consider the l.r.p. in Q2(G) and the l.r.p. in Q2(H). We have b = c = 4. Therefore, G ∼= θ(2, 2, 2, 4, 4, 4). By Lemma 2.10, G is χ-unique.

Case 3 b⁴ = 3, b⁵ 6= 3, b⁶ 6= 3. Since the girth of H is 4, then b⁵ ≥ 4 and b⁶ ≥ 4. Given that H has three cycles of length 4, then b¹ + b² = 4 and b¹ + b³ = 4. So b¹ = b² = b³ = 2. Now, H has four cycles of length 4, a contradiction.

Case 4 b⁴ 6= 3, b⁵ 6= 3, b⁶ 6= 3. Since the girth of H is 4, then b⁴ ≥ 4, b⁵ ≥ 4 and b⁶ ≥ 4. Given that H has three cycles of length 4, then b¹ + b² = 4, b¹ + b³ = 4 and b² + b³ = 4. Thus, b¹ = b² = b³ = 2. It follows from equation 3 that 2b + c = b⁴ + b⁵ + b6. We obtain the following after simplification.

\[Q_{3}(G) = 12x^{b+c+5} + 2x^{b+c+1} + 6x^{2b+5} + x^{2b+1} + 8x^{b+7} + 6x^{b+3} + 4x^{c+7} + 3x^{c+3} + x^{9} + 2x^{7} + 3x^{5} - (x^{2b+c+1} + 3x^{2b+6} + x^{2b+4} + 3x^{2b+3} + 6x^{b+c+6} + 2x^{b+c+4} + 6x^{b+c+3} + 2x^{b+8} + 6x^{b+6} + 4x^{b+5} + 2x^{b+1} + x^{c+8} + 3x^{c+6} + 2x^{c+5} + x^{c+1} + 3x^{8} + x^{6}),\]

\[Q_{3}(H) = x^{b_{4}+b_{5}+6} + 3x^{b_{4}+b_{5}+4} + x^{b_{4}+b_{5}+1} + x^{b_{4}+b_{6}+6} + 3x^{b_{4}+b_{6}+4} + x^{b_{4}+b_{6}+1} + x^{b_{4}+7} + 4x^{b_{4}+3} + x^{b_{5}+b_{6}+6} + 3x^{b_{5}+b_{6}+4} + x^{b_{5}+b_{6}+1} + x^{b_{5}+7} + 4x^{b_{5}+3} + x^{b_{6}+7} + 4x^{b_{6}+3} + x^{6} + 3x^{4} - (x^{b_{4}+b_{5}+b_{6}+1} + x^{b_{4}+b_{5}+7} + 4x^{b_{4}+b_{5}+3} + x^{b_{4}+b_{6}+7} + 4x^{b_{4}+b_{6}+3} + x^{b_{4}+6} + 3x^{b_{4}+4} + x^{b_{4}+1} + x^{b_{5}+b_{6}+7} + 4x^{b_{5}+b_{6}+3} + x^{b_{5}+6} + 3x^{b_{5}+4} + x^{b_{5}+1} + x^{b_{6}+6} + 3x^{b_{6}+4} + x^{b_{6}+1} + x^{7} + x^{3}).\]

Compare the l.r.p. in \(Q_3(G)\) and the l.r.p. in \(Q_3(H)\). We have b=2 or c=2. If b=2, then \(G\cong \theta(2,2,2,2,2,c)\). By Lemma 2.10, G is \(\chi\)-unique. If c=2, then \(G\cong \theta(2,2,2,2,2,2)\). By Lemma 2.2, G is \(\chi\)-unique.

<u>Case B</u> \(H \in g_e(\theta(b_1, b_2, b_3, b_4), C_{b_5+1}, C_{b_6+1})\) where \(2 \le b_1 \le b_2 \le b_3 \le b_4\) and \(2 \le b_5, b_6\). As \(G \cong \theta(a, a, a, b, b, c)\) and \(H \in g_e(\theta(b_1, b_2, b_3, b_4), C_{b_5+1}, C_{b_6+1})\), then

\[Q_{4}(G) = x(x^{a}-1)^{3}(x^{b}-1)^{2}(x^{c}-1) - (x^{a}-x)^{3}(x^{b}-x)^{2}(x^{c}-x),\] \[Q_{4}(H) = x(x^{b_{1}}-1)(x^{b_{2}}-1)(x^{b_{3}}-1)(x^{b_{4}}-1)(x^{b_{5}}-1)(x^{b_{6}}-1) - (x^{b_{1}}-x)(x^{b_{2}}-x)(x^{b_{3}}-x)(x^{b_{4}}-x)(x^{b_{5}}-1)(x^{b_{6}}-1).\]

By equation 3, \(Q_4(G) = Q_4(H)\) yields

\[Q_{5}(G) = 2x^{3a+b+1} + x^{3a+c+1} + x^{3a+3} + 3x^{2a+2b+1} + 6x^{2a+b+c+1} + 6x^{2a+b+3} + 3x^{2a+c+3} + 3x^{2a+1} + 3x^{a+2b+c+1} + 3x^{a+2b+3} + 6x^{a+b+c+3} + 6x^{a+b+1} + 3x^{a+c+1} + 3x^{a+5} + x^{2b+c+3} + x^{2b+1} + 2x^{b+c+1} + 2x^{b+5} + x^{c+5} - (2x^{3a+b+2} + x^{3a+c+2} + x^{3a+1} + 3x^{2a+2b+2} + 6x^{2a+b+c+2} + 6x^{2a+b+1} + 3x^{2a+c+1} + 3x^{2a+c+1} + 3x^{2a+2b+c+2} + 3x^{a+2b+c+2} + 3x^{a+2b+1} + 6x^{a+b+c+1} + 6x^{a+b+4} + 3x^{a+c+4} + 3x^{a+1} + x^{2b+c+1} + x^{2b+c+1} + 2x^{b+c+4} + 2x^{b+1} + x^{c+1} + x^{6}),\]

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Since 2 ≤ a ≤ b ≤ c, by comparing the l.r.p. in Q5(G) and the l.r.p. in Q5(H), we have a = 2 or a = 3.

Case 1 a = 2. Then g(G) = g(H) = 2a = 4. There are three cycles of length 4 in G, and H has the same number as well. Without loss of generality, we have the following cases to consider.

Case 1.1 b⁵ = b⁶ = 3. Since H has three cycles of length 4, then b1+b² = 4. So b¹ = b² = 2. Note that there is −3x ^a+1 in Q5(G). Hence, there is one more term in Q5(H) that equal to −x 3 . Thus, b³ = 2 or b⁴ = 2.

If b³ = 2, then H has five cycles of length 4, a contradiction.

If b⁴ = 2, then b³ = 2. So H has eight cycles of length 4, a contradiction.

Case 1.2 b⁵ = 3, b⁶ 6= 3. Since H has girth 4, then b⁶ ≥ 4. Given that H has three cycles of length 4, then b¹ + b² = 4 and b¹ + b³ = 4. So b¹ = b² = b³ = 2. Now H has four cycles of length 4, a contradiction.

Case 1.3 b⁵ 6= 3, b⁶ 6= 3. Since H has girth 4, then b⁵ ≥ 4 and b⁶ ≥ 4. Given that H has three cycles of length 4, then b¹ + b² = 4, b¹ + b³ = 4 and b¹ + b⁴ = 4 or b² + b³ = 4 . Therefore, we have two cases to consider.

Case 1.3.1 b¹ + b⁴ = 4. So b¹ = b⁴ = 2. Thus, b¹ = b² = b³ = b⁴ = 2. Hence H has six cycles of length 4, a contradiction.

Case 1.3.2 b² + b³ = 4. So b² = b³ = 2. Thus, b¹ = b² = b³ = 2. It follows from equation 3 that 2b + c = b⁴ + b⁵ + b6. Then we obtain the following after simplification.

\[Q_{6}(G) = 6x^{2b+5} + x^{2b+1} + 12x^{b+c+5} + 2x^{b+c+1} + 8x^{b+7} + 6x^{b+3} + 4x^{c+7} + 3x^{c+3} + x^{9} + 2x^{7} - \left(x^{2b+c+1} + 3x^{2b+6} + x^{2b+4} + 3x^{2b+3} + 6x^{b+c+6} + 2x^{b+c+4} + 6x^{b+c+3} + 2x^{b+8} + x^{b+6} + 4x^{b+5} + 2x^{b+1} + x^{c+8} + 3x^{c+6} + 2x^{c+5} + x^{c+1} + 3x^{8}\right),\] \[Q_{6}(H) = x^{b_4+b_5+6} + 3x^{b_4+b_5+4} + x^{b_4+b_5+1} + x^{b_4+b_6+6} + 3x^{b_4+b_6+4} + x^{b_4+b_6+1} + x^{b_4+7} + 4x^{b_4+3} + 6x^{b_5+b_6+5} + x^{b_5+b_6+1} + 3x^{b_5+6} + x^{b_5+4} + 3x^{b_5+3} + 3x^{b_6+6} + x^{b_6+4} + 3x^{b_6+3} + 3x^{5} - \left(x^{b_4+b_5+b_6+1} + x^{b_4+b_5+7} + 4x^{b_4+b_5+3} + x^{b_4+b_6+7} + 4x^{b_4+b_6+3} + x^{b_4+6} + 3x^{b_4+4} + x^{b_4+1} + 3x^{b_5+b_6+6} + x^{b_5+b_6+4} + 3x^{b_5+b_6+3} + 3x^{b_5+b_6+3} + 3x^{b_5+6} + 6x^{b_5+5} + x^{b_5+1} + x^{b_6+5} + x^{b_6+1} + 2x^{6} + x^{4}\right).\]

Comparing the l.r.p. in Q6(G) and the l.r.p. in Q6(H), we have b = 3 or c = 3. If c = 3, then b = 2 or b = 3. By Lemma 2.10, G is χ-unique for both cases. So b = 3. Note that there is 2x b+1 in Q6(G), thus, b⁴ = 3. Simplifying Q6(G) and Q6(H), we obtain the following.

\[Q_{7}(G) = 5x^{c+8} + x^{c+7} + x^{c+4} + 3x^{c+3} + 4x^{11} + 6x^{10} + 3x^{7} + 4x^{6} - (3x^{c+9} + 6x^{c+6} + 2x^{c+5} + x^{c+1} + 3x^{12} + 7x^{9} + 7x^{8}),\] \[Q_{7}(H) = x^{b_{5}+9} + 3x^{b_{5}+7} + 2x^{b_{5}+4} + 3x^{b_{5}+3} + x^{b_{6}+9} + 3x^{b_{6}+7} + 2x^{b_{6}+4} + 3x^{b_{6}+3} + 3x^{5} - (2x^{b_{5}+b_{6}+4} + x^{b_{5}+10} + x^{b_{5}+6} + 6x^{b_{5}+5} + x^{b_{5}+1} + x^{b_{6}+10} + x^{b_{6}+6} + 6x^{b_{6}+5} + x^{b_{6}+1} + 3x^{7}).\]

Consider the term 3x 5 in Q7(H). Thus, b⁵ = 4 and b⁶ = 4. Therefore c = 5. However, we obtain Q7(G) 6= Q7(H), a contradiction.

Case 2 a = 3. Therefore, g(G) = g(H) = 2a = 6. There are three cycles of length 6 in G and H, respectively. Without loss of generality, we have three cases to consider, that are b⁵ = b⁶ = 5 or b⁵ = 5, b⁶ 6= 5 or b⁵ 6= 5, b⁶ 6= 5.

Case 2.1 b⁵ = b⁶ = 5. Therefore, b¹ + b² = 6. Thus, we have b¹ = 2, b² = 4 or b¹ = b² = 3. Case 2.1.1 b¹ = 2, b² = 4. It follows from equation 3 that 2b + c = b³ + b⁴ + 7. Since 3 ≤ b ≤ c and 4 ≤ b³ ≤ b4, by cancelling the equal terms, there is −x 3 in Q5(H) but not in Q5(G), a contradiction.

Case 2.1.2 b¹ = b² = 3. From equation 3, we obtain

\[2b + c = b_3 + b_4 + 7 (4)\]

We obtain the following after simplification.

\[Q_8(G) = x^{2b+c+3} + 6x^{b+c+7} + 6x^{b+c+6} + 2x^{b+c+1} + 3x^{2b+7} + 3x^{2b+6} + x^{2b+1} + 2x^{b+10} + 6x^{b+9} + 2x^{b+5} + 6x^{b+4} + x^{c+10} + 3x^{c+9} + x^{c+5} + 3x^{c+4} + x^{12} + 3x^{8} + 2x^{7} - (x^{2b+c+1} + 6x^{b+c+8} + 8x^{b+c+4} + 3x^{2b+8} + 4x^{2b+4} + 2x^{b+11} + 12x^{b+7} + 2x^{b+1} + x^{c+11} + 6x^{c+7} + x^{c+1} + 4x^{10} + x^{6}),\] \[Q_8(H) = 3x^{b_3+b_4+7} + x^{b_3+b_4+1} + 2x^{b_3+14} + x^{b_3+13} + 4x^{b_3+10} + 2x^{b_3+6} + 2x^{b_3+4} + x^{b_3+3} + 2x^{b_4+14} + x^{b_4+13} + 4x^{b_4+10} + 2x^{b_4+6} + 2x^{b_4+4} + x^{b_4+3} + x^{17} + 2x^{16} + 2x^{13} + 6x^9 - (3x^{b_3+b_4+6} + x^{b_3+b_4+2} + 2x^{b_3+15} + x^{b_3+11} + 4x^{b_3+9} + 2x^{b_3+8} + 2x^{b_3+5} + x^{b_3+1} + 2x^{b_4+15} + x^{b_4+11} + 4x^{b_4+9} + 2x^{b_4+8} + 2x^{b_4+5} + x^{b_4+1} + x^{18} + 3x^{14} + 2x^{12} + 3x^{11} + x^8).\]

Comparing the l.r.p. in Q8(G) and the l.r.p. in Q8(H), we have b³ = 5 or b⁴ = 5. Case 2.1.2.1 b³ = 5. Then we obtain the following after simplification.

\[Q_{9}(G) = x^{2b+c+3} + 6x^{b+c+7} + 6x^{b+c+6} + 2x^{b+c+1} + 3x^{2b+7} + 3x^{2b+6} + x^{2b+1} + 2x^{b+10} + 6x^{b+9} + 2x^{b+5} + 6x^{b+4} + x^{c+10} + 3x^{c+9} + x^{c+5} + 3x^{c+4} + x^{12} + 3x^{8} + 2x^{7} - (x^{2b+c+1} + 6x^{b+c+8} + 8x^{b+c+4} + 3x^{2b+8} + 4x^{2b+4} + 2x^{b+11} + 12x^{b+7} + 2x^{b+1} + x^{c+11} + 6x^{c+7} + x^{c+1} + 2x^{10}),\] \[Q_{9}(H) = 2x^{b_4+14} + x^{b_4+13} + 3x^{b_4+12} + 4x^{b_4+10} + 3x^{b_4+6} + 2x^{b_4+4} + x^{b_4+3} + 2x^{19} + x^{17} + x^{16} + 4x^{15} + 8x^{9} - (2x^{b_4+15} + 4x^{b_4+11} + 4x^{b_4+9} + 2x^{b_4+8} + x^{b_4+7} + 2x^{b_4+5} + x^{b_4+1} + 2x^{20} + 7x^{14} + 2x^{12} + x^{11}).\]

Consider the term 2x 7 in Q9(G). We have b = 6 or c = 6.

If b = 6, then c = b4. However, Q9(G) 6= Q9(H), a contradiction.

If c = 6, then we obtain b = 6 and b⁴ = 6. Therefore, G ∼= θ(3, 3, 3, 6, 6, 6). By Lemma 2.10, G is χ-unique.

Case 2.1.2.2 b⁴ = 5. Then, we have b³ = 3 or b³ = 4 or b³ = 5.

Case 2.1.2.2(a) If b³ = 3, then H has five cycles of length 6, a contradiction.

Case 2.1.2.2(b) If b³ = 4, then there is −x 5 in Q8(H). Hence, b = 4 or c = 4.

If b = 4, by equation 4 we have c = 8. But Q8(G) 6= Q8(H), a contradiction.

If c = 4, by equation 4 we have b = 6. But 3 ≤ b ≤ 4, a contradiction.

Case 2.1.2.2(c) If b³ = 5, then it follows from equation 4 that 2b + c = 17. We obtain the following after simplification.

\[Q_{10}(G) = x^{2b+c+3} + 6x^{b+c+7} + 6x^{b+c+6} + 2x^{b+c+1} + 3x^{2b+7} + 3x^{2b+6} + x^{2b+1} + 2x^{b+10} + 6x^{b+9} + 2x^{b+5} + 6x^{b+4} + x^{c+10} + 3x^{c+9} + x^{c+5} + 3x^{c+4} + x^{12} + 2x^{8} + 2x^{7} - (x^{2b+c+1} + 6x^{b+c+8} + 8x^{b+c+4} + 3x^{2b+8} + 4x^{2b+4} + 2x^{b+11} + 12x^{b+7} + 2x^{b+1} + x^{c+11} + 6x^{c+7} + x^{c+1}),\] \[Q_{10}(H) = 4x^{19} + x^{18} + 4x^{17} + 8x^{15} + 2x^{11} + 10x^{9} - (4x^{20} + 3x^{16} + 11x^{14} + 2x^{13} + 3x^{12} + x^{6}).\]

Compare the l.r.p. in Q10(G) and the l.r.p. in Q10(H). We have b = 5 or c = 5. Since the coefficient of −x ^b+1 is 2, then c = 5. If c = 5, we have b = 6. But 3 ≤ b ≤ 5, a contradiction.

Case 2.2 b⁵ = 5, b⁶ 6= 5. Therefore, b¹ + b² = 6 and b¹ + b³ = 6. Thus, b² = b3. Hence, we have b¹ = 2, b² = b³ = 4 or b¹ = b² = b³ = 3.

Case 2.2.1 b¹ = 2, b² = b³ = 4. It follows from equation 3 that 2b + c = b⁴ + b⁶ + 6. However, cancelling the equal terms we obtain Q5(G) 6= Q5(H), a contradiction.

Case 2.2.2 b¹ = b² = b³ = 3. Then H has four cycles of length 6, a contradiction.

Case 2.3 b⁵ 6= 5, b⁶ 6= 5. Note that the girth of H is 6, thus b⁵ ≥ 6 and b⁶ ≥ 6. Since H has three cycles of length 6, therefore b¹ + b² = 6, b¹ + b³ = 6 and b¹ + b⁴ = 6 or b² + b³ = 6 .

Case 2.3.1 b¹ + b⁴ = 6. Considering b¹ + b² = 6 and b¹ + b3=6, then b² = b³ = b4. Hence, we have b¹ = 2, b² = b³ = b⁴ = 4 or b¹ = b² = b³ = b⁴ = 3.

Case 2.3.1.1 b¹ = 2, b² = b³ = b⁴ = 4. It follows from equation 3 that 2b + c = b⁵ + b⁶ + 5. Cancelling the equal terms we obtain Q5(G) 6= Q5(H), a contradiction.

Case 2.3.1.2 b¹ = b² = b³ = b⁴ = 3. Then H has six cycles of length 6, a contradiction.

Case 2.3.2 b² + b³ = 6. Considering b¹ + b² = 6 and b¹ + b³ = 6, we have b¹ = b² = b³ = 3. It follows from equation 3 that 2b + c = b⁴ + b⁵ + b6. We obtain the following after simplification.

\[\begin{array}{lll} Q_{11}(G) & = & 6x^{b+c+7} + 6x^{b+c+6} + 2x^{b+c+1} + 3x^{2b+7} + 3x^{2b+6} + x^{2b+1} + \\ & 2x^{b+10} + 6x^{b+9} + 2x^{b+5} + 6x^{b+4} + x^{c+10} + 3x^{c+9} + x^{c+5} + \\ & 3x^{c+4} + x^{12} + 3x^8 - \left(6x^{b+c+8} + 8x^{b+c+4} + 3x^{2b+8} + 4x^{2b+4} + 2x^{b+11} + 12x^{b+7} + 2x^{b+1} + x^{c+11} + 6x^{c+7} + x^{c+1} + 4x^{10} + x^6\right), \\ Q_{11}(H) & = & x^{b_4+b_5+9} + 3x^{b_4+b_5+5} + x^{b_4+b_5+1} + x^{b_4+b_6+9} + 3x^{b_4+b_6+5} + \\ & x^{b_4+b_6+1} + x^{b_4+10} + 3x^{b_4+4} + x^{b_4+3} + 3x^{b_5+b_6+7} + 3x^{b_5+b_6+6} + \\ & x^{b_5+b_6+1} + 3x^{b_5+8} + 4x^{b_5+4} + 3x^{b_6+8} + 4x^{b_6+4} + 3x^6 - \\ & \left(x^{b_4+b_5+10} + 3x^{b_4+b_5+4} + x^{b_4+b_5+3} + x^{b_4+b_6+10} + 3x^{b_4+b_6+4} + \\ & x^{b_4+b_6+3} + x^{b_4+9} + 3x^{b_4+5} + x^{b_4+1} + 3x^{b_5+b_6+8} + 4x^{b_5+b_6+4} + \\ & 3x^{b_5+7} + 3x^{b_5+6} + x^{b_5+1} + 3x^{b_6+7} + 3x^{b_6+6} + x^{b_6+1} + 3x^8 + x^4 \right). \end{array}\]

Comparing the l.r.p. in Q11(G) and the l.r.p. in Q11(H), we have b = 3 or c = 3. If b = 3, then G ∼= θ(3, 3, 3, 3, 3, c). By Lemma 2.10, G is χ-unique. If c = 3, then G ∼= θ(3, 3, 3, 3, 3, 3). By Lemma 2.2, G is χ-unique.

<u>Case C</u> \(H \in g_e(\theta(b_1, b_2, b_3, b_4, b_5), C_{b_6+1})\) where \(2 \le b_1 \le b_2 \le b_3 \le b_4 \le b_5\) and \(2 \le b_6\). As \(G \cong \theta(a, a, a, b, b, c)\) and \(H \in g_e(\theta(b_1, b_2, b_3, b_4, b_5), C_{b_6+1})\), then

\[Q_{12}(G) = x(x^{a}-1)^{3}(x^{b}-1)^{2}(x^{c}-1) - (x^{a}-x)^{3}(x^{b}-x)^{2}(x^{c}-x),\] \[Q_{12}(H) = x(x^{b_{1}}-1)(x^{b_{2}}-1)(x^{b_{3}}-1)(x^{b_{4}}-1)(x^{b_{5}}-1)(x^{b_{6}}-1) - (x^{b_{1}}-x)(x^{b_{2}}-x)(x^{b_{3}}-x)(x^{b_{4}}-x)(x^{b_{5}}-x)(x^{b_{6}}-1).\]

By equation 3, \(Q_{12}(G) = Q_{12}(H)\) yields,

\[Q_{13}(G) = 2x^{3a+b+1} + x^{3a+c+1} + x^{3a+3} + 3x^{2a+2b+1} + 6x^{2a+b+c+1} + 6x^{2a+b+3} + 3x^{2a+c+3} + 3x^{2a+1} + 3x^{a+2b+c+1} + 3x^{a+2b+3} + 6x^{a+b+c+3} + 6x^{a+b+1} + 3x^{a+c+1} + 3x^{a+5} + x^{2b+c+3} + x^{2b+1} + 2x^{b+c+1} + 2x^{b+5} + x^{c+5} - (2x^{3a+b+2} + x^{3a+c+2} + x^{3a+1} + 3x^{2a+2b+2} + 6x^{2a+b+c+2} + 6x^{2a+b+1} + 3x^{2a+c+1} + 3x^{2a+4} + 3x^{a+2b+c+2} + 3x^{a+2b+1} + 6x^{a+b+c+1} + 6x^{a+b+4} + 3x^{a+c+4} + 3x^{a+1} + x^{2b+c+1} + x^{2b+4} + 2x^{b+c+4} + 2x^{b+1} + x^{c+1} + x^{6}),\]

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Consider the l.r.p. in Q13(G) that is a + 1 and the l.r.p. in Q13(H), that is 5. Since a = 4 and a ≥ 2, we have three cases to consider, (1) a = 2 or (2) a = 3 or (3) a = 4.

Case 1 a = 2. Therefore, g(G) = g(H) = 2a = 4 and H has three cycles of length 4. Hence, we have b⁶ = 3 or b⁶ 6= 3.

Case 1.1 b⁶ = 3. Then, we have b¹ + b² = 4 or b¹ + b³ = 4. Thus, b¹ = b² = b³ = 2. However, H has four cycles of length 4, a contradiction.

Case 1.2 b⁶ 6= 3. Note that g(H) = 4, then b⁶ ≥ 4. Then, we have b¹ + b² = 4, b¹ + b³ = 4 and b¹ + b⁴ = 4 or b² + b³ = 4 . So, we have two cases to consider.

Case 1.2.1 b¹ + b⁴ = 4. Since b¹ + b² = 4 and b¹ + b³ = 4, then we know that b¹ = b² = b³ = b⁴ = 2. Now H has six cycles of length 4, a contradiction.

Case 1.2.2 b² + b³ = 4. Since b¹ + b² = 4 and b¹ + b³ = 4, then b¹ = b² = b³ = 2. From equation 3, we obtain

\[2b + c = b_4 + b_5 + b_6 (5)\]

Then, we obtain the following after simplification.

\[Q_{14}(G) = 6x^{2b+5} + x^{2b+1} + 12x^{b+c+5} + 2x^{b+c+1} + 8x^{b+7} + 6x^{b+3} + 4x^{c+7} + 3x^{c+3} + x^9 + 2x^7 + x^5 - (x^{2b+c+1} + 3x^{2b+6} + x^{2b+4} + 3x^{2b+3} + 6x^{b+c+6} + 2x^{b+c+4} + 6x^{b+c+3} + 2x^{b+8} + 6x^{b+6} + 4x^{b+5} + 2x^{b+1} + x^{c+8} + 3x^{c+6} + 2x^{c+5} + x^{c+1} + 3x^8 + x^6),\] \[Q_{14}(H) = x^{b_4+b_5+6} + 3x^{b_4+b_5+4} + x^{b_4+b_5+1} + 6x^{b_4+b_6+5} + x^{b_4+b_6+1} + 3x^{b_4+6} + x^{b_4+4} + 3x^{b_4+3} + 6x^{b_5+b_6+5} + x^{b_5+b_6+1} + 3x^{b_5+6} + x^{b_5+4} + 3x^{b_5+3} + 4x^{b_6+7} + 3x^{b_6+3} + x^8 + 3x^6 - (x^{b_4+b_5+b_6+1} + x^{b_4+b_5+7} + 4x^{b_4+b_5+3} + 3x^{b_4+b_6+6} + x^{b_4+b_6+4} + 3x^{b_4+b_6+3} + 6x^{b_4+5} + x^{b_4+1} + 3x^{b_5+b_6+6} + x^{b_5+b_6+4} + 3x^{b_5+b_6+3} + 6x^{b_5+5} + x^{b_5+1} + x^{b_6+8} + 3x^{b_6+6} + 2x^{b_6+5} + x^{b_6+1} + 4x^7).\]

Consider the l.r.p. in Q14(G). We have b = 4 or c = 4.

Case 1.2.2.1 b = 4. Since there is −2x ^b+1 in Q14(G), we have b⁴ = 4 or b⁵ = 4 or b⁶ = 4. If b⁴ = 4, then it follows from equation 5 that c + 4 = b⁵ + b6. However, Q14(G) 6= Q14(H), a contradiction.

If b⁵ = 4, then it follows from equation 5 that c + 4 = b⁴ + b6. However, Q14(G) 6= Q14(H), a contradiction.

If b⁶ = 4, then it follows from equation 5 that c + 4 = b⁴ + b5. However, Q14(G) 6= Q14(H), a contradiction.

Case 1.2.2.2 c = 4. We obtain the following after simplification.

\[Q_{15}(G) = 5x^{2b+5} + x^{2b+1} + 12x^{b+9} + 2x^{b+7} + 6x^{b+3} + 4x^{11} + 5x^{7} - (3x^{2b+6} + x^{2b+4} + 3x^{2b+3} + 6x^{b+10} + 4x^{b+8} + 6x^{b+6} + 2x^{b+5} + 2x^{b+1} + x^{12} + 3x^{10} + x^{9} + 3x^{8}),\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Compare the l.r.p. in Q15(G) and the l.r.p. in Q15(H). Then we have b = 3. Simplifying Q15(G) and Q15(H), we obtain the following.

\[\begin{array}{lll} Q_{16}(G) & = & 8x^{12} + 5x^{11} + 6x^7 + 6x^6 - \left(6x^{13} + 2x^{10} + 10x^9 + 5x^8 + 2x^4\right), \\ Q_{16}(H) & = & x^{b_4 + b_5 + 6} + 3x^{b_4 + b_5 + 4} + x^{b_4 + b_5 + 1} + 6x^{b_4 + b_6 + 5} + x^{b_4 + b_6 + 1} + \\ & & 3x^{b_4 + 6} + x^{b_4 + 4} + 3x^{b_4 + 3} + 6x^{b_5 + b_6 + 5} + x^{b_5 + b_6 + 1} + 3x^{b_5 + 6} + \\ & & x^{b_5 + 4} + 3x^{b_5 + 3} + 4x^{b_6 + 7} + 3x^{b_6 + 3} + x^8 + 4x^6 - \left(x^{b_4 + b_5 + b_6 + 1} + x^{b_4 + b_5 + 7} + 4x^{b_4 + b_5 + 3} + 3x^{b_4 + b_6 + 6} + x^{b_4 + b_6 + 4} + 3x^{b_4 + b_6 + 3} + \\ & & & 6x^{b_4 + 5} + x^{b_4 + 1} + 3x^{b_5 + b_6 + 6} + x^{b_5 + b_6 + 4} + 3x^{b_5 + b_6 + 3} + 6x^{b_5 + 5} + \\ & & & x^{b_5 + 1} + x^{b_6 + 8} + 3x^{b_6 + 6} + 2x^{b_6 + 5} + x^{b_6 + 1} + 4x^7 \right). \end{array}\]

Considering the term −2x 4 in Q16(G), we have b⁴ = 3 and b⁵ = 3. It follows from equation 5 that b⁶ = 4. However, we obtain Q16(G) 6= Q16(H), a contradiction.

Case 2 a = 3. So g(G) = g(H) = 2a = 6. Both G and H has three cycles of length 6, respectively. Then, we have b⁶ = 5 or b⁶ 6= 5.

Case 2.1 b⁶ = 5. Therefore, b¹ + b² = 6 and b¹ + b³ = 6. So b² = b3. Thus, we have b¹ = 2, b² = b³ = 4 or b¹ = b² = b³ = 3.

Case 2.1.1 b¹ = 2, b² = b³ = 4. It follows from equation 3 that 2b + c = b⁴ + b⁵ + 4. However, we obtain Q13(G) 6= Q13(H), a contradiction.

Case 2.1.2 b¹ = b² = b³ = 3. Then H has four cycles of length 6, a contradiction.

Case 2.2 b⁶ 6= 5. Since H has three cycles of length 6, then we have b¹ + b² = 6, b¹ + b³ = 6 and b¹ + b⁴ = 6 or b² + b³ = 6 .

Case 2.2.1 b¹ + b⁴ = 6. Note that b¹ + b² = 6 and b¹ + b³ = 6. Therefore, b² = b³ = b4. Hence, we have b¹ = 2, b² = b³ = b⁴ = 4 or b¹ = b² = b³ = b⁴ = 3.

Case 2.2.1.1 b¹ = 2, b² = b³ = b⁴ = 4. It follows from equation 3 that 2b + c = b⁵ + b⁶ + 5. However, after simplification, we obtain Q13(G) 6= Q13(H), a contradiction.

<u>Case 2.2.1.2</u> \(b_1 = b_2 = b_3 = b_4 = 3\). Therefore, H has six cycles of length 6, a contradiction. <u>Case 2.2.2</u> \(b_2 + b_3 = 6\). Note that \(b_1 + b_2 = 6\) and \(b_1 + b_3 = 6\). Therefore \(b_1 = b_2 = b_3 = 3\). From equation 3, we have

\[2b + c = b_4 + b_5 + b_6 \tag{6}\]

We obtain the following after simplification.

\[Q_{17}(G) = 3x^{2b+7} + 3x^{2b+6} + x^{2b+1} + 6x^{b+c+7} + 6x^{b+c+6} + 2x^{b+c+1} + 2x^{b+10} + 6x^{b+9} + 2x^{b+5} + 6x^{b+4} + x^{c+10} + 3x^{c+9} + x^{c+5} + 3x^{c+4} + x^{12} + 3x^8 - (3x^{2b+8} + 4x^{2b+4} + 6x^{b+c+8} + 8x^{b+c+4} + 2x^{b+11} + 12x^{b+7} + 2x^{b+1} + x^{c+11} + 6x^{c+7} + x^{c+1} + 3x^{10} + x^6),\] \[Q_{17}(H) = x^{b_4+b_5+9} + 3x^{b_4+b_5+5} + x^{b_4+b_5+1} + 3x^{b_4+b_6+7} + 3x^{b_4+b_6+6} + x^{b_4+b_6+1} + 3x^{b_4+8} + 4x^{b_4+4} + 3x^{b_5+b_6+7} + 3x^{b_5+b_6+6} + x^{b_5+b_6+1} + 3x^{b_5+8} + 4x^{b_5+4} + x^{b_6+10} + 3x^{b_6+9} + x^{b_6+5} + 3x^{b_6+4} + x^{11} + 3x^7 - (x^{b_4+b_5+10} + 3x^{b_4+b_5+4} + x^{b_4+b_5+3} + 3x^{b_4+b_6+8} + 4x^{b_4+b_6+4} + 3x^{b_4+7} + 3x^{b_4+6} + x^{b_4+1} + 3x^{b_5+b_6+8} + 4x^{b_5+b_6+4} + 3x^{b_5+7} + 3x^{b_5+6} + x^{b_5+1} + x^{b_6+11} + 6x^{b_6+7} + x^{b_6+1} + 3x^9 + x^5).\]

Compare the l.r.p. in \(Q_{17}(G)\) and the l.r.p. in \(Q_{17}(H)\). We have b=4 or c=4.

<u>Case 2.2.2.1</u> b=4. There is one term in \(Q_{17}(H)\) that equal to \(-x^5\). Since \(b_6 \ge 6\), we have \(b_4=4\) or \(b_5=4\).

If \(b_4=4\), then it follows from equation 6 that \(c+4=b_5+b_6\). Cancelling the equal terms, we obtain \(b_5=5\) and \(b_6=6\). So c=7. But, \(Q_{17}(G)\neq Q_{17}(H)\), a contradiction.

If \(b_5 = 4\), then it follows from equation 6 that \(c + 4 = b_4 + b_6\). Since \(b_6 \ge 6\), by cancelling the equal terms in \(Q_{17}(G)\) and \(Q_{17}(H)\), we obtain \(b_4 = 5\). But \(3 \le b_4 \le 4\), a contradiction.

<u>Case 2.2.2.2</u> c=4. Therefore, b=3 or b=4. If b=3, then \(G\cong \theta(3,3,3,3,3,4)\). By Lemma 2.10, G is \(\chi\)-unique. If b=4, then \(G\cong \theta(3,3,3,4,4,4)\). Similarly, by Lemma 2.10, G is \(\chi\)-unique.

<u>Case 3</u> a=4. Therefore, g(G)=g(H)=2a=8 and both G and H has three cycles of length 8, respectively. Then, we have to consider for \(b_6=7\) or \(b_6\neq 7\).

<u>Case 3.1</u> \(b_6 = 7\). Therefore, \(b_1 + b_2 = 8\) and \(b_1 + b_3 = 8\). So, we know that \(b_2 = b_3\). Hence, we have \(b_1 = 2\), \(b_2 = b_3 = 6\) or \(b_1 = 3\), \(b_2 = b_3 = 5\) or \(b_1 = b_2 = b_3 = 4\).

<u>Case 3.1.1</u> \(b_1 = 2, b_2 = b_3 = 6\). It follows from equation 3 that \(2b + c = b_4 + b_5 + 9\). Since \(4 \le b \le c\), after simplification, we obtain \(-x^3\) is in \(Q_{13}(H)\) but not in \(Q_{13}(G)\), a contradiction.

<u>Case 3.1.2</u> \(b_1 = 3, b_2 = b_3 = 5\). It follows from equation 3 that \(2b + c = b_4 + b_5 + 8\). Similar to Case 3.1.1, we obtain \(Q_{13}(G) \neq Q_{13}(H)\), a contradiction.

<u>Case 3.1.3</u> \(b_1 = b_2 = b_3 = 4\). But H has four cycles of length 8, a contradiction.

<u>Case 3.2</u> \(b_6 \neq 7\). Since the girth of H is 8, then \(b_6 \geq 8\). So \(b_1 + b_2 = 8\), \(b_1 + b_3 = 8\) and \((b_1 + b_4 = 8 \text{ or } b_2 + b_3 = 8)\). Hence, we have two cases to consider.

<u>Case 3.2.1</u> \(b_1 + b_4 = 8\). Since \(b_1 + b_2 = 8\) and \(b_1 + b_3 = 8\), we know that \(b_2 = b_3 = b_4\). So we have \(b_1 = 2\), \(b_2 = b_3 = b_4 = 6\) or \(b_1 = 3\), \(b_2 = b_3 = b_4 = 5\) or \(b_1 = b_2 = b_3 = b_4 = 4\).

<u>Case 3.2.1.1</u> \(b_1 = 2, b_2 = b_3 = b_4 = 6\). It follows from equation 3 that \(2b + c = b_5 + b_6 + 8\). Similar to the above cases, we obtain \(Q_{13}(G) \neq Q_{13}(H)\), a contradiction.

<u>Case 3.2.1.2</u> \(b_1 = 3, b_2 = b_3 = b_4 = 5\). It follows from equation 3 that \(2b + c = b_5 + b_6 + 6\). Similar to the above cases, we obtain \(Q_{13}(G) \neq Q_{13}(H)\), a contradiction.

<u>Case 3.2.1.3</u> \(b_1 = b_2 = b_3 = b_4 = 4\). But H has six cycles of length 8, a contradiction.

<u>Case 3.2.2</u> \(b_2 + b_3 = 8\). Since \(b_1 + b_2 = 8\) and \(b_1 + b_3 = 8\), we know that \(b_1 = b_2 = b_3\). Therefore, \(b_1 = b_2 = b_3 = 4\). It follows from equation 3 that \(2b + c = b_4 + b_5 + b_6\). We obtain the following after simplification.

\[\begin{array}{lll} Q_{18}(G) & = & 3x^{2b+9} + 3x^{2b+7} + x^{2b+1} + 6x^{b+c+9} + 6x^{b+c+7} + 2x^{b+c+1} + \\ & & 2x^{b+13} + 6x^{b+11} + 8x^{b+5} + x^{c+13} + 3x^{c+11} + 4x^{c+5} + x^{15} + \\ & & 3x^9 - \left(3x^{2b+10} + 3x^{2b+5} + x^{2b+4} + 6x^{b+c+10} + 6x^{b+c+5} + \right. \\ & & & 2x^{b+c+4} + 2x^{b+14} + 6x^{b+9} + 6x^{b+8} + 2x^{b+1} + x^{c+14} + 3x^{c+9} + \\ & & & 3x^{c+8} + x^{c+1} + 3x^{12} + x^6 \right), \\ Q_{18}(H) & = & & x^{b_4+b_5+12} + 3x^{b_4+b_5+6} + x^{b_4+b_5+1} + 3x^{b_4+b_6+9} + 3x^{b_4+b_6+7} + \\ & & & & x^{b_4+b_6+1} + 3x^{b_4+10} + 3x^{b_4+5} + x^{b_4+4} + 3x^{b_5+b_6+9} + 3x^{b_5+b_6+7} + \\ & & & x^{b_5+b_6+1} + 3x^{b_5+10} + 3x^{b_5+5} + x^{b_5+4} + x^{b_6+13} + 3x^{b_6+11} + \\ & & 4x^{b_6+5} + x^{14} + 3x^8 - \left(x^{b_4+b_5+13} + 3x^{b_4+b_5+5} + x^{b_4+b_5+3} + 3x^{b_4+b_5+3} + 3x^{b_4+b_6+10} + 3x^{b_4+b_6+5} + x^{b_4+b_6+4} + 3x^{b_4+9} + 3x^{b_4+7} + x^{b_4+1} + \\ & & 3x^{b_5+b_6+10} + 3x^{b_5+b_6+5} + x^{b_5+b_6+4} + 3x^{b_5+9} + 3x^{b_5+7} + x^{b_5+1} + \\ & & x^{b_6+14} + 3x^{b_6+9} + 3x^{b_6+8} + x^{b_6+1} + 3x^{11} + x^5 \right). \end{array}\]

Compare the l.r.p. in \(Q_{18}(G)\) and the l.r.p. in \(Q_{18}(H)\). We have b=4 or c=4. If b=4, then \(G\cong \theta(4,4,4,4,4,c)\). By Lemma 2.10, G is \(\chi\)-unique. If c=4, then \(G\cong \theta(4,4,4,4,4,4)\). By Lemma 2.2, G is \(\chi\)-unique. This completes the proof of Theorem 3.1.

4. Conclusion

It is natural to ask the following question: for which choices \((a_1, a_2, \cdots, a_6)\) where \(a_1 \leq a_2 \leq \cdots \leq a_6\), the graph \(\theta(a_1, a_2, \cdots, a_6)\) is \(\chi\)-unique? In general, this problem still remains open. In the next paper, the chromaticity of another type of the graph \(\theta(a_1, a_2, \cdots, a_6)\) where \(a_1, a_2, \cdots, a_6\) assume exactly three distinct values will be given.

Acknowledgement

The authors are thankful to the anonymous referee for the comments and suggestions.

References

• [1] X. W. Bao and X. E. Chen, Chromaticity of the graph θ(a, b, c, d, e) (in Chinese), J. Xinjiang Univ. Natur. Sci. 11 (1994), 19-22.
• [2] C. Y. Chao and E. G. Whitehead Jr., On chromatic equivalence of graphs, Theory and Applications of Graphs, Lecture Notes in Math. 642, Springer, Berlin (1978), 121-131.
• [3] X. E. Chen, X. W. Bao and K. Z. Ouyang, Chromaticity of the graph θ(a, b, c, d), J. Shaanxi Normal Univ. 20 (1992), 75-79.
• [4] F. M. Dong, K. M. Koh and K. L. Teo, Chromatic polynomials and chromaticity of graphs, World Scientific Publishing Ptd. Ltd. Singapore, 2005, pp. 105-123.
• [5] F. M. Dong, K. L. Teo, C. H. C. Little, M. Hendy, and K. M. Koh, Chromatically unique multibridge graphs, The Electronic Journal of Combinatorics, 11 (2004), #R12.
• [6] F. Harary, Graph theory, Addison-Wesley Publishing Company Inc., United States of America, 1972.
• [7] A. M. Khalaf, Chromaticity of a certain k-bridge graphs, Doctoral Dissertation, Universiti Putra Malaysia, Serdang, Malaysia, 2010.
• [8] A. M. Khalaf and Y. H. Peng, Another proof of a family of chromatically unique 5-bridge graphs, International Journal of Applied Mathematics 22 (6) (2009), 1009-1020.
• [9] A. M. Khalaf and Y. H. Peng, A note on chromaticity of k-bridge graphs, Far East Journal of Mathematical Sciences 34 (3) (2009), 353-359.
• [10] A. M. Khalaf and Y. H. Peng, The chromatic uniqueness of a family of 6-bridge graphs, AKCE Journal of Graphs and Combinatorics 6 (3) (2009), 393-400.
• [11] A. M. Khalaf and Y. H. Peng, Chromaticity of the 6-bridge graph θ(a, a, a, b, c, c), International Journal of Applied Mathematics 22 (7) (2009), 1087-1111.
• [12] A. M. Khalaf and Y. H. Peng, A family of chromatically unique 6-bridge graphs, Ars Combinatoria 94 (2010), 211-220.
• [13] A. M. Khalaf, Y. H. Peng and K. A. Atan, Chromaticity of 5-bridge graphs (II), International Journal of Applied Mathematics 23 (2010), 791-808.
• [14] K. M. Koh and K. L. Teo, The search for chromatically unique graphs, J. Graph Combin. 6 (1990), 259-285.
• [15] K. M. Koh and K. L. Teo, The search for chromatically unique graphs-II, Discrete Math. 172 (1997), 59-78.

• [16] X. F. Li, A family of chromatically unique 5-bridge graphs, Ars Combinatoria 88 (2008), 415-428.
• [17] X. F. Li and X. S. Wei, The chromatic uniqueness of a family of 5-bridge graphs (in Chinese), J. Qinghai Normal Univ. 2 (2001), 12-17.
• [18] B. Loerinc, Note: Chromatic uniqueness of the generalized θ-graph, Discrete Mathematics 23 (1978), 313-316.
• [19] C.D. Wakelin and D.R. Woodall, Chromatic polynomials, polygon trees and outer-planar graphs, J. Graph Theory 16 (1992), 459-466.
• [20] D. B. West, Introduction to graph theory, 2nd edition, Prentice Hall, Inc., United States of America, 2001.
• [21] S. J. Xu, Classes of chromatically equivalent graphs and polygon trees, Discrete Math. 133 (1994), 349-358.
• [22] S. J. Xu, J. J. Liu and Y. H. Peng, The chromaticity of s-bridge graphs and related graphs, Discrete Math. 135 (1994), 349-358.
• [23] C. F. Ye, The chromatic uniqueness of 6-bridge graphs (in Chinese), J. Math. Study 34 (4) (2001), 399-421.
• [24] C. F. Ye, The chromatic uniqueness of s-bridge graphs (in Chinese), J. Xinjiang Univ. Natur. Sci. 19 (3) (2002), 246-265.
• [25] A.A. Zykov, On some properties of linear complexes, Amer. Math. Soc. Transl. 79 (1952); translated from Math. Sb. 24 (66) (1949), 163-188.