On the Quick Construction of the Edge-Balance Index Sets of a Classes of Nested Network Graph

Published Online July 2012 in MECS

I.   IntroductionA.  History

Binary labeling are a simplification of graceful labeling, introduced by Cahit [1]in his seminal paper on cordial graphs. Since then, other nation of balance in binary labeling ([2] and [3] for example) have been introduced and much work has been done to classify graphs. So far, the problem is far from complete, though there are classifications of index sets for specific graph classes (see [4] and [5] for example).

Our objective is to assign a binary labeling to some substructure of graphs so that the assignment is balanced and induces a labeling on some other substructure. We then attempt to classify the degree of imbalance in the induced labeling of the graph. We hope that such an index set could form an invariant that in some way can distinguish classes of graphs. In this paper, we focus on the edge-balance index set of a class of nested network graphs.

• B.    Definition

For basic graph theoretic nation and definitions see

Diestel [6]. All graphs G(V, E) are finite, simple, and undirected with vertex set V and edge set E . The number of vertices is

denoted v(G) and the number of edges is denoted e(G).

Let G(V, E) be a graph with vertex set V and edge set E . Integers set Z = {0,1}. Given an edge labeling functions f : E(G) ^ Z^ .That is to say, Ve e E(G),  f {e}=0 or 1. According to the edge labeling f, we define an associated partial vertex labeling f+ : V(G)^ Z2 as follow. Define f +(V) to be 0 if it is incident to more 0-edges than 1-edges and 1 if it is incident to more 1-edges than 0-edges, if the vertex v is incident to an equal number of 0-and 1-edges, leave it unlabeled. Hence f+ is a partial function. For each i e{0,1}   , let  e, (i) = {MV ep: f (uv)= i}   , and

V y ( i ) = { v e V : f ⁺ ( v ) = i } .If no ambiguity occurs, we could omit the subscript and simply write e ( i ) and v ( i ) respectively.

Definition 1.1 An edge labeling f: E(G)^{0,1}of the graph G is said to be edge-friendly if|e^ (о) — e^ (1) < 1

where

e^ (i )     is the cardinality of the

set {e e E(G): f (e) = i} fori e{0,1}.[7]

Definition 1.2 the value ^ (o) — v^ (1) is called on edge-balance index of G under an edge-friendly labeling f . The edge-balance index set of the graph g , denoted by EBI (G), is defined as the set of all possible edge-balance indices of G , that is the set |vy (0)- vf (1) : f is an edge friendly labeling of G} .[7]

Specifically ， the maximum of edge-balance index denoted by max { EBI ( G )}

• C.    The nested network graph

The following constructions of graph were considered in [8].

Definition 1.3 The graph is denoted byP , which is mn the nm paths which is m vertex in each path and every vertex has n bifurcates except the last vertex of path

< i <  . ,1 <  j <  k ,2 <  k <  n } ,

and. In among, V (p )={(i). ^

^E ( p .. ) = Я( i ) j ( i + 1 ), . )

1 < i < .,1 < j < ki,

2 < k < n ,0 < r < k — 1

Definition 1.4 The graph is denoted by C , which is the m circle which is the inner circle containing n vertex and the vertex number of m circle from inside to outside successively increase by power exponent a. In among, V ( C m ) = { ( i)_ |1 < i < . ,1 <  j < k i ,2 < k < n } ,

E (C.)={(OjOj 1

Definition 1.5 The sigh C . X P m denotes the power circles nested network graph by the power circles graph, C m , and the paths shape graph, P _m .

Definition 5: The nested graph is denoted by

C m X P , which is the graph P embedded in the _n      m_n                              m_n

graph C. . In among, V ( c.. X Bn) = V ( C. )=V (Bn),

EC x P )= E f c Jlj E f P ).

• _n m m _nn m m _n

Example: The figure 1 gives several C . X P

₄       m ₄

graphs.

^C 4^{2 X P} 2 4         ^C 4 3 ^{X P} 3 4         ^C 4 4 ^X P

Figure 1 several C _л. X P graphs. 4       m 4

For convenience We will have the following label for the nested network graph ：

The vertices of the inner circle in clockwise order were labeled as follows: ( 1 ) 1 , ( 1 ) 2 ,-.., ( 1 ) _n - 1 , ( 1 ) _n ; Similarly, from inside to outside the vertices of the circle in clockwise were labeled as follows: ⁽ . ) 1 , ⁽ . ) 2 , ⁽ . ) 3 , ⁽ . ) ₄ -, ⁽ . ) n . — 1 , ⁽ m ) n . . Among them, symbols ( j ) says the i th vertex in the j th circle.

The paths begin with the vertex ( 1 ) , as follows:

(1) 1 A (2) 1 A (3) 1 A ^ A ( . — 1) 1 A ( . ) 1 ;

⁽¹⁾1 A ⁽²⁾1 A ⁽³⁾1 A----A ⁽ . ^— 1) 1 A ⁽ . ) 2 ;

(1)1 A (2)1 A (3)1 A ^ A (. —1)1 A (.).;

0)1 A (2)1 A (3)1 A    A (. — 1)2 A (.).+1;

(1)1 A (2)n1 ^ (3)n2 ^     > (. — 1)n.—2 ^ (.)n.—1—1;

(1)1 ^ (2).i ^ (3)n2 ^----> (. — 1)n.—2 ^ (.)n.—1 ;

Similarly, the paths begin with the vertex ( 1 )^ , as follows:

(1) n ^ ⁽²⁾ n 2 — n + 1 ^ ⁽³⁾ n ³ — n 2 + 1 ^ ^ ^ ( . — 1) n . — 1 — n . — 2 + 1 ^ ( . ) n . — n . — 1 + 1 ; ⁽¹⁾ n ^ ⁽²⁾ n 2 — n + 1 ^ ⁽³⁾ n ³ — n ’-+ 1 ^ ™ ^ ⁽ . — 1) n . — 1 — n . — 2 + 1 ^ ⁽ . ) n . — n . — 1 + 2 ;

• ⁽¹⁾ n ^ ⁽²⁾ n¹ — n + 1 ^ ⁽³⁾ n ³ — n ²+ 1 ^ "■ ^ ⁽ . — 1) n . — 1 — n . — 2 + 1 ^ ⁽ . ) n . — n . — 1 ₊ n ; ⁽¹⁾ n A ⁽²⁾ n ³— n + 1 ^ ⁽³⁾ n ³ — n ²+ 1 ^ ^ ^ ⁽ . — 1) n . — 1 — n . — 2 + 1 ^ ⁽ . ) n . — n . — 1 ₊ n + 1 ;

• (1)n A (2)n2 A (3)n3 A     A (. — 1)n.—1 A (.)n. —J;

• (1)n A (2)n2 A (3)n3 A----A (. — 1)n.—I A (.)n. ;

The above says that the C _n . X P .^ have n* " paths.

We call an edge labeling of f ( xy ) is 1 to be 1-edge and an edge labeling of f ( xy ) is 0 to be 0-edge, the vertex labeling is 1 to be 1-vertex and the vertex labeling is 0 to be 0-vertex when the context is clear.

• II.    The Construction of the Maximum of EdgeBalance Index

A common approach to finding the edge-balanced index set is to start by finding the maximum element in the set and then produce the smaller values by a series of edge-label switches. The following lemma gives on the maximum edge-balanced index set of the nested network graphs.

For the edge-friendly labeling of the graph C P ( m >  2 ) , ₄ m m ₄

Y stands for the total edges of the graph .we discuss the edge-balance index set of this graph from the following three parts: m = 2 ( mod3 ) ; m = 0 ( mod3 ) ; m = 1 ( mod3 ) . But, in this paper, we only researcher it when m = 0 ( mod3 ) and m = 2 ( mod3 ) .

Lemma 1: For the graph C x Pm (m > 2) , whenm = 0(mod3) , max{EBI(C4m x PJ} = 4m — 2.

Proof: First, structure the graphics with the maximum edge - balance index:

Because the power circles nested graph were nested by the power circle graph and the paths shape graph. For convenience, we will label respectively the power circle graph and the paths shape graph.

In the paths shape graph, we mark all edges for 0-edge which are in the paths

( j - 1) a ( j ) b ( j +1 ) c ( j + 2 ) d ( j = 3 k + 1,1 <  j <  m ;1 <  a < 4 j ^—1; b = 3 + r + 8 s ,0 <  r <  3,1 <  b <  4 j ; c = 9 + r + 32 s ,0 <  r <  15,1 <  c <  4 j ^{+ 1}; d = 33 + r +128 s ,0 <  r < 63,1 <  d < 4 j ⁺²; r , s eN, k eN⁺ ) .

And let the label of edges ( j )₆( j + 1)_c ( j = 3 k + 1,1 <  j <  m ;

b = 1 + r + 6 s + 8 1 ; c = 1 + 7 r + 24 s + 32 1 , r , s e { 0,1 } , 1 e N , 1 <  b <  4 j ,1 <  c <  4 j ^{+ 1}, k eN ⁺ ) ;( j ) _c ( j + 1) _d ( j = 3 k +2,1 <  j <  m ; c = 2 + r + 24 s + 32 1 ,0 <  r <  5, s e { 0,1 } ,1 <  c <  4 j ; d = 5 + 7 r + 8 s + 96 1 +128 u , r e { 0,1 } , s e { 0,1,2 } , 1 e { 0,1 } , u eN ,0 <  d <  4 j ^{+ 1}, k eN⁺ ) ;( j )_c( j + 1)^ ( j = 3 k + 2,1 <  j <  m ; c = 25 + 32 s ;

d = 97 + r + 128 s , r e { 0,1 , 2 } , s eN ,1 < c < 4 j ,1 <  d < 4 ^{j + 1}, k eN + ) were signed 0-edge. In addition, the edges of the paths ( 1} ( 2 )₆( 3} ( a = 1,2;1 < b < 9;1 < c < 36, b , c eN ) and the edges ( 1 )₄ ( 2 )₁₆ and ( ²X ( ³L ( 1 < b < 9, b eN ; c = 37 + 7 r + 8 s , r , s e { 0,1,2 } ) are the 0-edge, the other edges in the paths is labeled as 1.

In the power circles graph, we mark all edges for 0-edge which are in the circles j = 3 k + 1,3 k + 2 ( k eN + ) . In the 3 k + 3th circle, let the edges ( j )^( j )_4t]( j = 3 k + 3,1 <  j < m ;

d = 1+2 r+124s+1281, or 29+2 r+1281, r e{0,1}, s e{0,1}, 1 eN,1 < d < 4 j, k eN+) and   (j)rf(j)d+i(j = 3k + 3,1 < j

т „        ,   „              2x4 m⁺¹-20   , г

In the graph, there are y = 2 x 4_____2- edges, of which 2m+1 — 3 are the 0-edge .According to the definition of edge-friendly labeling, | e(0) — e(1) |< 1, we can get the edge-friendly labeling of the labeled graph by calculation. In this labeled graph, all the vertices (j)Д j = 3k +1+1,1 < j< m;a = 1 + 2x41 + r + 8x4‘s,

1 e{0,1} ,0 < r< 4¹⁺¹— (—1)‘ — 1,1 < a< 4j, r,s e N, k e N⁺) are 0-vertex., others are 1-vertex except the vertex (2)_o(a = 1 + r,0< r<8,r eN),(1),,(1)₂. Thus, we can gain ,(0) = ^{2 x 4}m-1 ⁺¹.

Due to v (g) = 4 4 vertices in this graph which is defined by the f⁺ , one of the vertices is not defined, .hen ,(1) = ¹4^xtm+5. After this

I^{v (0) — v (1)}l =

2 x 4^m—1+1  14 x 4 ^m—1— 5

3             3

= 4^m — 2.

We can prove EBI(C₄„ _xP ) = 4^m_—2 is the maximum of edge-balance index in the graph ^C4 - x Pm4 (m > ²) .

In this labeled graph, the vertices of the outside circle have 3 adjacent edges, and the edges adjacent to the vertices of the inner circle are 6, the edges next to the vertices of others circles are 7. The degree of 0-virtex is seven except six degree point in the inner circle. what’s more, the adjacent edges with 0-vertex is 0-edge,the adjacent edges with 1-vertex whose degree is three is only one, the adjacent edge with 1-vertex whose degree is seven is three，the adjacent edge with 1-vertex whose degree is six is two. When we change the 0-vertex into 1-vertex or undefined vertex, we must take out two 0-edges. Thus, wherever we put the two 0-edge, the number of the 0-vertex will increase, meanwhile the number of the 1-vertex will not increase. So the difference value is maximum, that’s to say: max{EBI(C4m xPm)} = 4m — 2.

Lemma 2:  For the graph c^ xP^(m > 2) , whenm = 2(mod3), max{EBI(C4m x P )} = 4m — 2.

Proof: First, structure the graphics with the maximum edge - balance index:

Because the power circles nested graph were nested by the power circle graph and the paths shape graph.

For convenience, we will label respectively the power circle graph and the paths shape graph.

In the paths shape graph, we mark all edges for 0-edge which are in the paths

(.j - 1) a (. j) b (. j + 1). ( j + 2 ) d

(j = 3 k ,1 < j< m;1< a< 4^j-1; b = 3 + r+8 s ,0 < r< 3,1 < b< 4^j; c = 9 + r + 32s, 0 < r< 15,1 < c< 4^j+1;

d = 33+r+128s,0 < r < 63,1 < d < 4j\r,s eN,k eN+)  .

And let the label of edges (j)₆ (j+1)_c(j = 3k,1 < j< m;

b = 1+r+6s+8t; c = 1+7 r+24 s+32t, r, s e{0,1}, t eN,1 < b< 4^j,1 < c< 4^j+l, k eN⁺); (j )_c( j+Цп (j=3 k+1,1 < j< m; c = 2+r+24 s+32t ,0 < r< 5, s e{0,1} ,1 < c< 4^j; d=5+7 r+8s+961+128u, r e{0,1}, s e{0,1,2}, t e{0,1}, u eN,0 < d< 4^j+1, k eN⁺); (jX (j +1X (j = ³k +1,1 < j< m; c = 25 + 32s; d = 97 + r +128s, r e{0,1,2},seN,1 <c<4^j,1 <d<4^j+1,k eN+) Were signed 0-edge. In addition, the edges (1Ц2)_t(a=2,3,4;b=5+r,0<r< 15,reN) are the 0-edge, the other edges in the paths is labeled as 1.

In the power circles graph, we mark all edges for 0-edge which are in the circles j = 3 k and j = 3k +1(k eN⁺). In the j = 3k + 2(k eN⁺) circle, let the edges

(j) d (j) d+1 (j = 3 k+2,1 < j < m; d = 1 + 2 r+124s + 128t or29+2r + 128t, r e{0,1}, s e {0,1}, t e N,1 < d < 4j, k e N+) and (jMj X+1 (j = 3 k + 2,1 < j < m; d = 6+2 r+8 s + 96t+128u, r, s e {0,1,2}, t e{0,1}, u eN,1 < d < 4j, k eN+) were signed 0-edge. In addition, all the edges in the first circle and the edges (2 )1( 2 )2, (2 ), ( 2 ). in the second circle, the other edges in the circles is labeled as 1.

In the graph, there are ₌^{2 x 4}m^{+1 - 20} edges, of which ^Y        3

2m+1 — 3 are the 0-edge .According to the definition of edge-friendly labeling, | e(0) — e(1) |< 1, we can get the edge-friendly labeling of the labeled graph by calculation. In this labeled graph, all the vertices (j )_й( j = 3 k+1,1 < j< m; a = 1+2 x 4 t + r+8 x 4 ts, t e{0,1} ,0 < r< 4 t⁺¹—(—1) t—t, 1 <_a<4^j,r,_seN,k_eN⁺) are 0-vertex. Others are 1-vertex except the vertex (1)₂, (1)₃, (1)₄  . Thus, we can

• •     ,       9 у A^m—1 4-1

gain v (0 )= ^{2 x 4}^ ⁺¹.

Due to v ( g ) = ⁴m⁺1 ⁴vertices in this graph which is defined by the f⁺ , one of the vertices is not defined, then _v(1) =^{14 x}4'^-1^{— 5} . After this v(0) — v(1)| = 4^m — 2.

We can prove EBI(C^ x p ) = 4^m — 2 is the maximum of edge-balance index in the graph C_xP mi > 2).

₄^m     m₄

In this labeled graph, the vertices of the outside circle have 3 adjacent edges, and the edges adjacent to the vertices of the inner circle are 6, the edges next to the vertices of others circles are 7. The degree of 0-virtex is seven except six degree point in the inner circle. what’s more, the adjacent edges with 0-vertex is 0-edge,the adjacent edges with 1-vertex whose degree is three is only one, the adjacent edge with 1-vertex whose degree is seven is three, the adjacent edge with 1-vertex whose degree is six is two. When we change the 0-vertex into 1-vertex or undefined vertex, we must take out two 0-edges. Thus, wherever we put the two 0-edges, the number of the 0-vertex will increase; meanwhile the number of the 1-vertex will not increase. So the difference value is maximum, that’s to say: max{EBI(C4m xPm^)} = 4^m — 2.

• III.    The Construction of the Edge-balance Index

Lemma 3: In the graph C x P (m > 2) when ₄^m     m₄

m = 0(mod3), {4m — 3,4m — 4,-,2,1,0} c EBI(C^ xPm).

Proof: In the lemma 3, when _m = 0(_mod3), we get max{EBI(C2m x P„₂)} = 4^m — 2.

Below transform is based on the biggest index labeled graph constructed form lemma 3, and every step all proceeds is based on the previous step to transform, which in turn constructs labeling graphs corresponding with the index.

Among the (2k — 1)_r(2k)_sо (2k)Д2k)_s+1 means that we exchange (2k — 1)_r(2k)₅ and (2k) _r (2k)_s+1 which are 0-edge and 1-edge respectively.

First, build an even index set:

Step 1: In turn exchange ⁽²)a⁽³⁾b ° ⁽²)a⁽³⁾b+1

(a = {1,2,3,-,8,9};b = 1+2r,re{0,1,---,16,17}),we can obtain 18 labeled graphs of even edge-balance indexes which are {4^m — 4,4^m — 6,4^m — 8,---,4^m — 34,4^m — 36,4^m — 38}. Step 2: In turn exchange (2)^ (3)^ ° (2)^ (3)^ (a = {10,11,12,13,14,15}; b = 37+7 r+8 s; c = 40+r+8s, r e {0,1},

^ ^{0,1,2}), we can obtain 6 labeled graphs of even edge-balance indexes which are

{4m - 40,4m - 42,4m - 44,4m - 46,4m - 48,4m - 50}. Step 3: In turn exchange (3)b (³)b₊₁° (²)a (³)b+1 (a = {10,11,12,13,14,15,16}; b = 39+4r,re{0,1,2,3,4,5,6}), we can obtain these labeled graphs of even edgebalance indexes which are

{4m - 52,4m - 54,4m - 56,4m - 58,4m - 60,4m - 62,4m - 64}. Step 4: In tun exchange ( j)a ( j +1)b О ( j + 1)b ( j + 1)b+1

(j = 3 k+2,1 < j< m; a = 9+r+321 ,0 < r< 16; b = 33+2 r +1285,0 < r< 33, s eN,1 < a< 4j,1 <b< 4j⁺¹,k eN⁺) we can obtain these labeled graphs of even edge-balance indexes which are '                    29 (4m - 64)'

J 4^m - 66,4^m - 68, • • •,    ---------² J

^m - 64

- 2,--.,2,0

Odd index collection structures as follows:

Step 1: Exchange (1) (1) _о (1)₃ (1)₄, we can obtain

the

edge-balance

indexes

which

are|v(0)-v(1)| = 4^m -3.

Step ^{2: In} turn exchange (²)_a (³)_b⁰ (²)_a (³)_b+1

(a = {1,2,3,-,8,9}; b = 1+2r,r e {0,1,---,16,17})

，we can obtain 18 labeled graphs of odd edge-balance indexes which are

{4^m - 5,4^m

—

7，4^m

-9,---,4^m -35,4^m -37,4^m -39}

.

Step 3: In turn exchange (2) (3) о (2)^ (3)

Step 5: In turn exchange (j +1)b (j+1)b+1 _O( j)a (j +1)b

(j = 3 k+2,1 < j < m; a = 2+r+24s+321; b = 6+4 r+96s+1281, r e{0,1,2,3,4,5},s e{0,1},1 eN,1 < a <4j,0

29(4^m - 64)       17(4^m - 64)

63          ,   ,      63

Step 6: In turn exchange ( j)a ( j + 1)b o( j)a ( j + 1)c (j = 3 k + 2,1 < j< m; a = 2 + 2s + 241 + 32u; b = 5 + 7 r+8 s+961 + 128u; c = 8 + r + 8s + 961 + 128u, r e{0,1},s e {0,1,2}, 1 e{0,1}, u eN,0 < a< 4 j ,1 < b< 4j⁺¹, k eN⁺), we can obtain these labeled graphs of even edge-balance indexes which are

17 (4^m - 64)        5 ( 4^m - 64)'

63         ^,"",     63      *

Step 7: In turn exchange (j +1)b(j+1)b+1 o(j)a(j +1)b (j = 3k + 2,1 < j < m; a = 1 + 31 r + 321; b = 1 + 2r +124s +1281, re{0,1},se{0,1}, 1 eN,1

5 (4 m - 64) _₂   4^m - 64

63        ,"',   63

Step 8: ^In tun exchange ( j⁺1)b ( j⁺1)b +1 о ( j)a ( j⁺1)b

(j = 3 k+2,1 < j< m; a = 8+321; b = 29+1281, 1 eN,1 < a< 4^j,

1 < b< 4^j+1, k e N⁺) , we can obtain these labeled graphs of even edge-balance indexes which are

(a = {10,11,12,13,14,15}; b = 37 + 7 r+8 s; c = 40+8s, r e{0,1}, s e{0,1,2} ，we can obtain 6 labeled graphs of odd edge-balance indexes which are

{4^m - 41,4^m - 43,4^m - 45,4^m - 47,4^m - 49,4^m - 51} •

Step 4: In turn exchange ⁽³⁾b⁽³⁾b+1 ^{0 (2})a⁽³⁾b+1

(a = {10,11,12,13,14,15};b = 39+4r,r e {0,1,2,3,4,5})  , we can obtain 6 labeled graphs of odd edge-balance indexes which are

{4^m -53,4^m -55,4^m -57,4^m -59,4^m -61,4^m -63}.

Repeat the fourth, fifth, sixth, seventh, eighth step when the even index set were structured, we can obtain these labeled graphs of odd edge-balance indexes which are respectively{4m -65,4^m -67,---,7,5,3,1} -

In conclusion, we can prove

{4^m - 3,4^m - 4, • ■ •, 2,1,0} c EBI(C₄m x P_m<)

.

Lemma 4: In the graphq. xp^ (m>2), whenm = 2(mod3) ,

{4m - 3,4m - 4,..., 2,1,0} c EBI(qm x Pm ).

Proof: In the lemma 2, when m = 2(mod3) , we getmax{EBI(C4m x ?m_t)} = 4^m - 2.

Below transform is based on the biggest index labeled graph constructed form lemma 2, and every step all proceeds is based on the previous step to transform, which in turn constructs labeling graphs corresponding with the index.

First, build an even index set:

Step 1: Exchange (2) (2)₂o(2)₂(2) , we can obtain the edge-balance indexes which are. v(0)- v(1)| = 4^m - 4

Step 2: In turn exchange

(1)a(²)b °²)b(²)b+i(a €{^2,3,4};b = ³+²r,1 <r<6^,r€ⁿ) , we can obtain 6 labeled graphs of even edge-balance indexes which are {4m - 6,4^m - 8,4m-10,4m-12,4^m-14,4^m-16} •

Step 3: In turn exchange (j)a (^j +1)b ° (^j +1)b (^j +1)b+1

(j = 3k+1,1 < j< m; a = 9 + r + 321,0 < r< 16; b = 33 + 2r +128s,

0<r<33,s€N,1 <a<4j,1 <b<4j^+l,k€N⁺) - we can obtain these labeled graphs of even edge-balance indexes which are I                      29 (4^m -16)] .

J 4^m -18,4^m -20,--,—

Step 4: In turn exchange (j +1)b (j +1)b₊₁° (j)a (j +1)b

(j = 3k +1,1 < j< m; a = 2 + r + 24s+321; b = 6 + 4r + 96s + 1281, r €{0,1,2,3,4,5),s €{0,1},1 eN,1 < a< 4^j,1 < b< 4j⁺¹, k eN⁺)- we can obtain these labeled graphs of even edge-balance indexes

'29(4^m -16)

63           :

17(4m -16)'

63       ¹.

which are

,

Step 5: In turn exchange ( j)a ( j + 1)_b °( j)a ( j + 1)c

(j = 3k +1,1 < j< m; a = 2 + 2s + 241 + 32u; b = 5 + 7r + 8s + 961 + 128u; c = 8+r+8 s+961+128u, r €{0,1}, s €{0,1,2}, 1 €{0,1}, u €N,0 < a< 4j,1 < b< 4 j+1, k €N⁺) ，we can obtain these labeled graphs of even edgebalance indexes which areI 17 (4^m -16)      5 (4^m -16)1.

|   63    2,"",^T" j

Step 6: In turn exchange (j +1)b (j +1)b+1 °(j)_a (j +1)b (j = 3k +1,1 < j< m; a = 1 + 31 r + 321; b = 1 + 2r +124s +1281, r €{0,1}, s €{0,1}, 1 €N,1 < a< 4j,1 < b< 4^j+1, k €N⁺) - ^{we can} obtain these labeled graphs of even edge-balance indexes which are [ ⁵(^{4m -16})       (⁴m^-16)] .

I     6.3       2         63 j

Step ^7:In turn exchange ( j + 1)b ( j + 1)b+1 O(j)a (j + 1)b (j = 3 k+1,1 < j< m; a = 8+321; b = 29+1281, 1 €N,1 < a< 4j,1 < b< 4^j+1, k eN⁺) ，we can obtain these labeled graphs of even edgebalance indexes which are I ⁴m -¹⁶_2 ... 2 о > •

I 63         ^,"'^{,  ,}I

Odd index collection structures as follows:

Step 1: Exchange (2) (2 )₂°(2) (1) , we can obtain the edge-balance indexes which are |v ( 0)- v (1)| = 4^m - 3.

Step 2: In turn exchange

(1) a (²) b °(²) b (²) b+1 (a €{^2,3,4}; b = ³ + ²r ,1 < r< 6 r €ⁿ) - ^we can obtain 6 labeled graphs of odd edge-balance indexes which are 1^{4m -16} _₂ ... ₂ol •

I 63 ^,‘“^{, ,}I

Repeat the third, fourth, fifth, sixth, seventh step when the even index set were structured, we can obtain these labeled graphs of odd edge-balance indexes which are respectivel

{4m -17,4m -19,4m -21,4m -23,-,7,5,3,1}.

In conclusion we can prove

{4m - 3,4m - 4,-,2,1,0}c EBI (C^ xPm )•

• IV.    Conclusion

According to lemma 1, 2 and lemma 3, 4, we can get the following theorem:

Theorem 1: In the graph C_4m x P^ (m > 2), when

m = 0,2(mod3), EBI(Cm x?m4)=.{4m-2,4m-3rs3,2,1,0}

Acknowledgments

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.