On the Edge-balanced Index Set of a class of Power-cycle Nested Network Graph

Published Online October 2013 in MECS DOI: 10.5815/ijmecs.2013.09.04

• A.    History

  In 1966 B.M.Stewart first introduced the theory of graph, by means of labeling function of vertex and edge. Since then, numerous domestic and international researchers have been working on the research of this aspect and winning a series of research results. In 1995, M.C.Kong and other scholars researched the concepts of the edge-balanced graph and the strong edge-balanced graph and put forward two conjectures. In 2002, B.L.C hen etc expanded edge-balance multiple graph concept in reference [2], proved that the conjecture in reference [1] is true and obtained a graph is edge-balanced is not NP-difficult problem. In 2006-2008, Alexander, Harris, etc made a research of vertex-balanced index sets and friendly index sets in reference [3-5]. In 2008, Sub-Ryung used the structure method to study the new family of edge-balanced graph in reference [6]. In 2010, D Chopra researched the edge-balanced index sets of wheel graph in reference [7]. In 2011, Sin-Min Lee, C.C.Chou, M.Galiardi, M.K ong etc discussed the edge-balanced index sets of L-product of cycles with stars in reference [8]. Since 2011, Zheng Yuge and her students have researched the edge-balanced index sets of a class

of chain graph in reference [9] and edge-balance index sets of the complete graphs reference [12]. Basing on this research, they also completely research the edge-balanced index sets of the equal-cycle nested graph in reference [13].

In graph of power-cycle nested graph C _X P 6 , the difficulty of the problem multiplied when n is bigger. In this article, by the use of the process clawed nested-cycle sub-graph and single point sector sub-graph, the edge-balanced index sets of the power-cycle nested graph C₆ m _x P ₆ are solved when m >  4 and m = 4 ( mod5 ) .

• B.    Definition

A graph G is an ordered pair ( v ( g ) _; e ( g ) ) consisting of a set v ( g ) of vertices and a set e ( g ) , disjoint from V ( g ) , of edges, together with an incidence function that associates with each edge of G an unordered pair of vertices of G . The graphs are all simple in this paper.

Definition 1.1 In graph G, let: f: E (G) ^ Z is a edge labeling function, namely to define f {e} = 0or1 . The edge set labeling 0 or 1 is recorded as E(0), E(1) , using ex (0) , ex (1) to present the number of E(0),E(1). According to the edge labeling f , we can define f+ : V(G) > {0,1}, if ex (0) is more than ex (1), f + (X) = 0, the vertex is labeling 0; if e (0) is less than e (1), f + (x) = 1, the vertex is labeling 1; otherwise, the vertex X is unlabeled. e (0) or e (1) presents the radix number of the edge collection that the edges linked x are labeling 0 or 1. The radix number of the vertex setV (0) ,V (1) is presented by v (0) or v (1), respectively.

Definition 1.2 In graph G , let: f _: e ( G ) ^ Z is an edge labeling function, if| e (0) - e (1) | < 1, f is considered as an edge-friendly labeling of the graph G .

Definition 1.3 The edge-balanced index set of the graph EBI ( G ) , is defined as { | v (0) - v (1) |: the edge labeling f is edge-friendly}

Definition 1.4 _P is a ray way that every road contains

P m ₆

m points, and that there are 6 branches at any points

Figure 1

except the terminal point of each road.

Definition 1.6 The power-cycle nested graph C _x P is the Cartesian product of c and p .

Two examples of graphs should serve to clarify the definition:

f m - 4

С xP = C _гхР I I 6^m m 6 6²2 6

U V i .0

, labeled the nested-cycle sub-

graph V ( 1 _e N ). Based on the starting points of the ray

paths, v is divided into 6 5 t ^{+ 4} sector graphs, denoted by

U 1 , U ₂, ^ , U ₆s , _{+ 4} , where these sector graphs is in the same and record as

U j = U ( j e { 1,2,3, - ,6^{5 1 + 4} } ) .

For clarity, the edge labeled 0 ( 1 ) is named 0-edge (1-edge), the vertex labeled 0 ( 1 ) is named 0-vertex (0-vertex).

Simply, we will have the following marks: Recorded the 6 ⁱ vertices on the i-th cycle in clockwise order as: L , L , L ,•••,L ,,t .The ray paths in the power-cycle ¹²³ 6 - 16

nested graph are denoted by ：

1, ^ 2,. ^ 3,- ^ —> ( m - 2 ) ^ ( m - 1 )

‘ 1            ^z 2 ^z 3                    ^V             ' \ m - 2 ) ^V ' \ m - 1 )

k <  m ) .

Definition 1.7 In the power-cycle nested graph , a 1-vertex x is considered to be saturated, if 6 ^m     m⁶

the n edges linked to x satisfy e_x (1)= e_x (0)+2 when the degree of vertex is even or the n edges linked to x satisfy e_x (1)= e_x (0)+1when the degree of vertex is odd ; otherwise, the 1-vertex x is unsaturated. A 0-vetex x is considered to be saturated, if the n edges linked to x are all 0-edges; otherwise, the 0-vertex x is unsaturated.

Definition 1.8 In the power-cycle nested graph C ^{6 m x P} m ⁶ , let ^m = ^{5 1 + 4( 1 G} N ) ,the induced sub-graph of the vertices, which the ray paths through the points with the vertices on the ^{5 1 + 4} cycle as starting points and the vertices on the⁵ t ⁺ 1) ^{+ 4} cycle as the terminal points, denoted by ^{V t '} .And the graph ^{V t '} subtract the edge on ^{5 1 + 2} is thought as the clawed nested-cycle sub-

V graph ^t .

In short, we introduce the concept of divisibility for power-cycle nested graph, it is obvious that

• II.    THE EDGE-BALANCE INDEX SETS OF NESTED GRAPH

^C 6 "  ^{X P}m 6 ( m = ⁴ ( mod⁴ ) ⁵ )

Lemma 1: For the power-cycle nested graph c_ _x p , when m = 4

max { EBI ( C 6 4 x P 4_i ) } = 1242

Proof. There are 3102 edges in the power-cycle nested graph c _{4 x} p , let edge labeling function is an edgefriendly labeling that| e (0) - e (1)| < 1, there are 1551 0-edges.

In short, we only mark the 0-edges of the graph, the left edges are 1-edges.

The edges on the second circle and the third circle are all 0-edges except the edges 2₃2₄ 、 2₉2₁₀ .

The edges linked to the vertices on the second circle

• 2 , ( i = 6 5 + 1 , s = 0,1, t = 1,2, k = 1,2; z = 6 s + 1 , 3

< s <  5,3 <  1 <  5 ) are all 0-edges,

The edges linked to the vertices on the third circle

• 3 , ( , = 6² s + 6 1 + k - 6 | s = 0,1, 1 = 1,2,1 <  k <  6;

s = 0,1, 1 = 3,4,1 <  k <  3; s = 0,1, 1 = 5,6, k = 1,2;

2 <  s <  5,1 <  1 <  3,1 <  k <  6; 2 <  s <  5,4 <  1 <  6, k = 1,2; ) are all 0-edges,

The 0-edges between the third circle and the forth circle

• 3 , 4 j ( i = 6² s + 6 1 + k - 6, j = 6 ( i - 1 ) + l |s = 0,1, 1 = 3,4,4 <  k <  6, l = 1,6; s = 0,1, 1 = 5,6,3 <  k <  6, l = 1,6;2 <  s <  5,4 <  1 <  6,3 <  k <  6, l = 1,6; ) ^are all 0-edges,

The edges on the forth circle

• 4 , 4 j ( i = 6³ s + 6² 1 + 6 k + l - 42, j = i + 1 | s = 0,1, 1 = 3,4,4 <  k <  6, l = 2,4; s = 0,1, 1 = 5,6,3 <  k <  6, l = 2,4;2 <  s <  5,4 <  1 <  6,3 <  k <  6, l = 2,4 ) are all 0-edges, then v ( 0 ) = 156 , | v ( 0 ) - v ( 1 )| = 1242 .

In this structure graph c x p , it is apparent that the vertices are all saturated 0-point and saturated 1-point. The degree of 0-point is 9, therefore, in order to change the label of one 0-point, we need to interchange 5 0-edges. And it must increase the number of 0-point and decrease the number of 1-point meanwhile. Then max EBI ( C2 x p^ ) = 1242.

Lemma 2 : For the single point sector sub-graph U , the maximum value of edge-balanced index is

v ( 0 ) - v ( 1 ) = 7464 .

Proof. In order to conveniently research, in single point sector sub-graph U , there are 5 arcs, denoted as the first arc, the second arc, the third arc, the forth arc and the fifth arc from inside to outside in turn.

The starting point is denoted by u , the ray path meets the                 i-th                arc                at

• 1 1 ,1 2 , - 1₆;2₁,2₂, - 2₆₂; — 5₁,5₂, — 5₆₅ in clockwise order.

The ray path starts from u as follows: u ^ ¹ i , ^ ² i ₂ ^ ³ i ₃ ^ ⁴ i ₄ ^ ⁵ i ₅ ⁽ i k = ⁽ i k - 1 ) ⁺ j ^; 1 <  i 1 , j <  5 )

Now, we labeling sector graph U , the construction method of the 0-edges is given, the rest are all labeled 0-edges.

The edges on the i ( 1 <  i <  4 ) arc are labeling 0.

The edges linked to the vertices on the first arc 1 i ( 4 <  i <  6 ) are all 0-edges,

The edges linked to the vertices on the second arc 2 i ( 19 <  i <  36 ) ( i = 6 5 + t ,0 <  5 <  2, t = 5,6 ) are all 0-edges,

The edges linked to the vertices on the third arc 3 i ( 109 <  i <  216 ) ( i = 6² 5 + 6 1 + k - 6,0 <  5 <  2,1 <  t <  4, k = 5,6,0 <  5 <  2; t = 5,6,1 <  k <  6 are all 0-edges,

The edges linked to the vertices on the forth arc 4 i ( 649 <  i <  930 ) ( i = 6³ 5 + 6² 1 + 6 k + l - 4210 <  s <  1,1 <  t <  4,1 <  k <  4, l = 5,6; 0 <  5 <  1,1 <  t <  4, k = 5,6,1 <  l <  6,0 <  5 <  1, t = 5,6,1 <  k <  6,1 <  l <  6 ) are all 0-edges,

The 0-edges between the forth arc and the fifth arc 4 i 5 j ( i = 6³ 5 + 6² 1 + 6 k + l - 42, j = 6 ( i - 1 ) + p , 0 <  5 <  1,1 <  t <  4,1 <  k <  4,1 <  l <  4, p = 5,6 ) ( 931 <  i <  1296, j = 5580 + 12 k + t ,0 <  k <  182, t = 1,12 ) are all 0-edges,

The edges on the fifth arc

5 i 5 j ( i = 6⁴ 5 + 6³ 1 + 6² k + 6 1 + p - 258, j = i + 1, 0 <  5 <  1,1 <  t <  3,1 <  k <  4,1 <  l <  4, p = 1,3; i

= 5580 + 12 k + t , j = i + 1,0 <  k <  182, t = 2,4, 6,8,10 ) are all 0-edges.

By calculating, the sector graph U is a friendly labeling, the vertices are all saturated 0-point and saturated 1-point. The degree of 0-point is 9, therefore, in order to change the label of one 0-point, we need to interchange 5 0-edges. And it must increase the number of 0-point and decrease the number of 1-point, meanwhile. Then, the maximum value of edge-balanced index is v ( 0 ) — v ( 1 ) = 7454 .

Lemma 3 : For the power-cycle nested graph C m _x p^ , when m = 4 ( mod5 ) and m >  4

^max { EBI ( ^C 6 m ^x P m 6 ) }

5 x 6 ^{m + 4} + 4 x 6 ^{m + 3} + 3 x 6 ^{m + 2} + 2 x 6 ^{m + 1} - 16794

6⁵ - 1

Proof. When m = 4 , the formula can be proved by lemma 1.

Now, we prove the formula is established when m >  4.

First of all, structure the graph of maximum edge- balanced index.

When m >  4 ,

C x P ^{m x} m

^ m - 4    ^

^p- и 5 V.

,

V V number the foundation graph and the nested-cycle subgraph.

The label of the foundation graph          is the

6 ^m      m 6

same as lemma 1.

The label of the nested-cycle sub-graph is the same as lemma 2.In the power-cycle nested graph C _x p , the foundation graph has the maximum radix number of edge-balanced index.

u is an undefined point in each of the single point sector sub-graph that won't affect the global maximum radix number of edge-balanced index. The nested-cycle sub-graph has the maximum radix number of edge-balanced index, then max { EBI ( U ) } = 7464

In power-cycle nested graph h C m x P m , the first nested-cycle has 6 ⁴ single point sector sub-graph, the second nested-cycle has 6⁹ single point sector subgraph • •• , the i nested-cycle has 6 ^{m - 5} single point sector sub-graph, then in the power-cycle nested graph c _x p I v ( 0 ) - v ( 1 )| = ( 6⁴ + 6⁹ + • 6 ^m " ¹⁰ + 6 ^m " ⁵ ) x 7464 + 1242 = 5 x 6 ^{m + 4} + 4 x 6 ^{m + 3} + 3 x 6 ^{m + 2} + 2 x 6 ^{m + 1} - 16794 6 5^ 1

Therefore, in power-cycle nested graph h C^m x pm max {EBI ( C6m x pm6 )} =

5 х 6 m ^{+ 4} + 4 x 6 m + 3 + 3 x 6 m ^{+ 2} + 2 x 6 m ^{+ 1} - 16794 6 5 - 1

In the following proof, make the e labeled graph that its index is max {EBI ( C6m x Pm6 )}

= 5 x 6 m ^{+ 4} + 4 x 6 m ^{+ 3} + 3 x 6 m ^{+ 2} + 2 x 6 m ^{+ 1} - 16794 6 5 - 1

In the Lemma 3 as the foundation graph and transform it to be the graph corresponding all index .

Obviously, the label of the sub-graph is the same as original graph.

Lemma 4 For the single point sector sub-graph U , { 7462,7460,7458 — 6,4,2,0 } c EBI ( U ) .

Proof. In sector graph U from lemma 2, there is | v ( 0 ) - v ( 1)| = 7464, interchange the 0-edges and 1-edges partly and the following steps are all on the basis of the previous labeled graph. We use i g j h ^. s t p l to present that the edge i_gj_h is from 0-edge into 1-edge and edge s _t p _l is from1-edge into 0-edge.

Step1:

4 i 5 j ^ 5 j - 1 5 j ( i = 6³ s + 6² t + 6 k + 1 - 6² - 6, j = 6 ( i - 1 ) + p , s = 0,1,2, t = 1,2,3, k = 1,2,3,4, 1 = 1,2,3,4, p = 5,6 )

| v ( 1 ) - v ( 0 )| = { 7462,7460, — , 6698,6696 }

Step2:

4 i 5 j ^ 5 j - 1 5 j ( i = 6³ s + 6² t + 6 k + 1 - 6² - 6, j = 6 ( i - 1 ) + p , s = 0,1,2, t = 1,2,3, k = 1,2,3 ,4, 1 = 5,6, p = 2,4,6 )

| v ( 1 ) - v ( 0 )| = { 6694,6692, — ,5930,5928 }

Step3:

4 _i 5 _j о 5 _/ _ ₁5 _j ( i = 6³ s + 6² 1 + 6 k + 1 - 6² - 6, j = 6 ( i - 1 ) + p , s = 0,1,2, t = 1,2,3,4, k = 5,6, 1 = 1,2,3,4,5,6, p = 2,4,6 )

I v ( 1 ) - v ( 0 )| = { 5926,5924, — , 4478,4476 }

Step4:

4 i 5 j о 5 _j - ₁5 _j ( i = 6³ s + 6² 1 + 6 k + 1 - 6² - 6, j = 6 ( i - 1 ) + p , s = 0,1,2, t = 5,6, k = 1,2,3,4,

5,6, 1 = 1,2,3,4,5,6, p = 2,4,6 ) | v ( 1 ) - v ( 0 )| = { 4774,4772, — ,3050,3048 }

Step5:

45 j о 5 _{j - 1}5 _j ( 649 <  i <  930, j = 6 ( i - 1 ) + k , k = 2,4,6 )

| v ( 1 ) - v ( 0 )| = { 3046,3044, — , 794,792 }

Step6:

4 i 5 j о 5 j _{+ 1}5 j ( 931 <  i <  1296, j = 5580 + 12 k + 1,0 <  k <  182 )

4 _i 5 _j о 5 _{j - 1}5 _j ( 931 <  i <  1296, j = 5580 + 12 k + 12,0 <  k <  182 )

I v ( 1 ) - v ( 0 )| = { 790,788, — ,62,60 }

Step7:

4 i 5 j ^ 5 j - 1 5 j ( 1267 <  i <  1296, j = 7596 + 12 k + p ,0 <  k <  14, p = 3,5,9,12 ) |v ( 1 ) - v ( 0 )| = { 58,56, — ,4,2,0 } ,

Proposition is proved.

• Theorem 1 : For the power-cycle   nested

graph C 6 m x P m , when m = 4 ( mod5 ) and m ^ ⁴

• 5 x 6 ^{m + 4} + 4 x 6 ^{m + 3} + 3 x 6 ^{m + 2} + 2 x 6 ^{m + 1} - 16794 6⁵ - 1

• - 2, — 4,3,2,1,0 } c EBI ( C 6 m x P m 6 ) .

Proof. In the following proof, every step is all on the basis of the previous labeled graph we will make the labeled graph that its index is max {EBI (C6m x Pm6 )}

= 5 x 6 ^{m + 4} + 4 x 6 ^{m + 3} + 3 x 6 ^{m + 2} + 2 x 6 ^{m + 1} - 16794 6⁵ - 1

in the Lemma 2 as the foundation graph and transform it to be the graph corresponding all index.

(1) The proof about even index.

Make the following transformation

Step1:

3 i 4 j ^ 4 ₎ _ ₁4 ₎ ( i = 6² s + 6 1 + k - 6, j = 6 ( i - 1 )

+ l|5 = 0,1, t = 1,2,1 <  k <  6, l = 2,4,6, 5 = 0,1, 3 <  t <  6, k = 1,2, l = 2,4,6;2 <  5 <  5,1 <  t <  3, 1 <  k <  6, l = 2,4,6;2 <  5 <  5,4 <  t <  6, k = 1,2, l = 2,4,6 )

Step2:

3 i 4 j о 4 j - 1 4 j ( i = 6² 5 + 6 t + k — 6, j = 6 ( i — 1 ) + l\ 5 = 0,1,3 <  t <  6,4 <  k <  6, l = 6;2 <  5 <  5,4 <  t <  6,3 <  k <  6, l = 6 )

Step 3 ：

3 i 4 j о 4 j ₊₁ 4 j ( i = 6² 5 + 6 t + k — 6, j = 6 ( i — 1 ) + 1 , 5 = 0,1,3 <  t <  6,4 <  k <  6, l = 1;2 <  5 <

5,4 <  t < 6,3 <  k <  6, l = 1 )

Step 4 ：

3 i 4 j о 4 j _— 1 4 j ( i = 6² 5 + 6 t + k — 6, j = 6 ( i — 1 ) + 1 |2 <  5 <  4,1 <  t <  3,1 <  k <  6, l = 3; 5 = 5, t = 1,2,1 <  k <  6, l = 3; 5 = 5, t = 3,1 <  k <  3, l = 3 )

Then obtain following index respectively f 5 x 6 m+4 + 4 x 6 m+3 + 3 x 6 m+2 + 2 x 6 m+1 —16794 _

[                           6⁵ — 1

5 x 6 m ^{+ 4} + 4 x 6 m ^{+ 3} + 3 x 6 m ^{+ 2} + 2 x 6 m ^{+ 1} — 16794

6⁵ — 1

• — 4, ■ “ ,

  • 5 x 6 ^{m + 4} + 4 x 6 ^{m + 3} + 3 x 6 ^{m + 2} + 2 x 6 ^{m + 1} — 16794

6⁵ — 1

— 1242 }

Then make the transformation from step one to step seven in lemma 3 for sector graph U 1 , U ₂, ■ , U _fi36 which belong to V 0 in turn and obtain the following index respectively.

• 5 x 6 ^{m + 4} + 4 x 6 ^{m + 3} + 3 x 6 ^{m + 2} + 2 x 6 ^{m + 1} — 16794 , „ „ „ ------------------;--1244, 6 5 — 1                                    ,

  5 x 6 ^{m + 4} + 4 x 6 ^{m + 3} + 3 x 6 ^{m + 2} + 2 x 6 ^{m + 1} — 16794

  ----------------;--1246, - , 6⁵ — 1

• 5 x 6 m ^{+ 4} + 4 x 6 m ^{+ 3} + 3 x 6 m ^{+ 2} + 2 x 6 m ^{+ 1} — 16794

6⁵ — 1

• — 6⁴ x 7464 — 1242 }

Finally make the transformation for V1 V ■ Vt in turn, and then obtain following index respectively f 5 x 6m+4 + 4 x 6m+3 + 3x 6m+2 + 2 x 6m+1 —16794

— 6⁴ x 7464 — 1242,

6⁵ — 1

5 x 6 ^{m + 4} + 4 x 6 ^{m + 3} + 3 x 6 ^{m + 2} + 2 x 6 ^{m + 1} — 16794

6⁵ — 1

— 6⁴ x 7464 — 1244, - 4,2,0 }

• ( 2) The proof about odd index.

First make the transformation 1 1 2 3 О 2 2 2 3

Then make the following transformation

Step 1 ：

3 i 4 j о 4 j _— 1 4 j ( i = 6² 5 + 6 1 + k — 6, j = 6 ( i — 1 ) + 1| 5 = 0,1, t = 1,2,1 <  k <  6, l = 2,4,6, 5 = 0, 1,3 <  t <  6, k = 1,2, l = 2,4,6;2 <  5 <  5,1 <  t <  3,1 <  k <  6, l = 2,4,6;2 <  5 <  5,4 <  t <  6, k = 1,2, l = 2,4,6 )

Step2 ：

3 i 4 j о 4 j _— 1 4 j ( i = 6² 5 + 6 1 + k — 6, j = 6 ( i — 1 ) + 1\5 = 0,1,3 <  t <  6,4 <  k <  6, l = 6;2 <  5 <  5, 4 <  t <  6,3 <  k <  6, l = 6 )

Step3 ：

3 i 4 j о 4 j ₊₁ 4 j ( i = 6² 5 + 6 1 + k — 6, j = 6 ( i — 1 ) + 1 , 5 = 0,1,3 <  t <  6,4 <  k <  6, l = 1;2 <  5 <  5,

4 <  t <  6,3 <  k <  6, l = 1 )

Step4 ：

3 i 4 j о 4 j _— 1 4 j ( i = 6² 5 + 6 1 + k — 6, j = 6 ( i — 1 ) + 1 12 <  5 <  4,1 <  t <  3,1 <  k <  6, l = 3; 5 = 5, t = 1,2,1 <  k <  6, l = 3; 5 = 5, t = 3, k = 1,2, l = 3 )

Then obtain following index respectively f 5 x 6m+4 + 4 x 6m+3 + 3 x 6 m+2 + 2 x 6m+1 —16794 .

I                                  25

[

• 5    x 6 ^{m + 4} + 4 x 6 ^{m + 3} + 3 x 6 ^{m + 2} + 2 x 6 ^{m + 1} — 16794

,,

6⁵ — 1

• 5    x 6m+4 + 4 x 6m+3 + 3 x 6m+2 + 2 x 6m+1 —16794 —1241} 65 — 1’

Then make the transformation from step one to step seven in     lemma      3 for sector graph                which belong to V in turn and

12     6 36                 0

obtain the following index respectively.

• _< 5 х 6 m ^{+ 4} + 4 х 6 m ^{+ 3} + 3 х 6 m ⁺ 2 + 2 х 6 m ^{+ 1} - 16794 ,

I                       6⁵ - 1

5 х 6 m ^{+ 4} + 4 х 6 m ^{+ 3} + 3 х 6 m ^{+ 2} + 2 х 6 m ^{+ 1} - 16794

----------------;--1245, - , 6⁵ - 1

• 5 х 6 m ^{+ 4} + 4 х 6 m ^{+ 3} + 3 х 6 m ^{+ 2} + 2 х 6 m ^{+ 1} - 16794

6⁵ - 1

• - 6⁴ х 7464 - 1241 }

Finally make the transformation for V 1 V 2 — V t in turn, and then obtain following index respectively

' 5 х 6 ^{m + 4} + 4 х 6 ^{m + 3} + 3 х 6 ^{m + 2} + 2 х 6 ^{m + 1} - 16794

• - 6⁴ х 7464 - 1243,

  5 х 6 ^{m + 4} + 4 х 6 ^{m + 3} + 3 х 6 ^{m + 2} + 2 х 6 ^{m + 1} - 16794 6 5^- 1

• - 6⁴ х 7464 - 1245, - 5,3,1 }

In conclusion, theorem was proved.

Based on Lemma 3and Theorem 1, we have

• III. CONCLUSION

For the power-cycle nested graph C _х P , when 6 ^m      m 6

m = 4(mod5) and m >  4

f 5 х 6 ^{m + 4} + 4 х 6 ^{m + 3} + 3 х 6 ^{m + 2} + 2 х 6 ^{m + 1} - 16794

|                           6 5 - 1                           ,

5 х 6 ^{m + 4} + 4 х 6 ^{m + 3} + 3 х 6 ^{m + 2} + 2 х 6 ^{m + 1} - 16794

6⁵ - 1

- 1, - 4,3,2,1,0 } c EBI ( C 6 m х P m 6 )

The theory of this thesis can be applied to computer science and information engineering and the proving method can be a reference to solve the problem of the power-cycle nested graph C m х P m .

ACKNOWLEDGMENT

Thanks for project supported by the Innovating Foundation of Henan Polytechnic University for the Master Thesis. Thanks for project supported by Applied

Mathematics Provincial-level Key Discipline of Henan Province and Operational Research and Cybernetics Key Discipline of Henan Polytechnic University. Thanks for project supported by the Ph.D. Foundation of Henan Polytechnic University Grant No.B2011-085.