Edge-balanced Index Sets of the Nested Graph with Power-cycle C5mxPm5 (I)

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

• I. INTRODUCTION

  Graph theory is an important branch of discrete mathematics which regards figure as the research object. B.M.Stewart introduced a theory in 1966 which use the vertices of graph and the label function of edges making the vertices of graph correspond to the edges, through the mapping function and then studies the characteristics and inherent characteristics of all kinds of figure. Its theory can be applied to the information engineering, communication network, computer science, economics and management, medicine and so on. Over the years many domestic and foreign researchers devote themselves to this area, and have access to a series of results.

In 1995, M.C.Kong and others defined the edge-balanced graph and strong edge-balanced graph in reference [1], and put forward two conjectures: Conjecture 1: All trees except Sn , n is odd, are edge-balanced. Conjecture 2: All connected regular graphs except K2 are edge-balanced. The reference [2] extends the concept of edge-balanced labeling to multigraphs and completely characterizes the edge-balanced multigraphs, and proves the two conjectures are true in the reference [1], at the same time proves the problem of decide a graph is edge-balanced does not belong to NP-hard. In 2008, Alexander and Harris studied the vertex -balanced index and friendly index sets of the figure in the literature [3-5].

Since 2009, author and her student Juan Lu solved the edge-balanced index sets of chain graph. In 2010, Ying Wang started the research about the edge-balanced index sets of the equal-cycle nested graph [7].From 2010, Hongjuan Tian[8] and others began the study of edge-balanced index sets of the nested graph with power-cycle. With the increase of n, the difficulty of graph design of odd n increases, ingenious design of classification is required for a nested transform edge index. In this paper, lay emphasis on the research about the graph when n = 5 .Using the innovative methods and techniques , categories design, proof method of five-vertices sector sub graph-group and other methods of Graph theory and Combinatorial mathematics, which have Completely solved the existence of the edge-balanced index set, construction methods and formulas proof. We choose different n, the subgraph of construction is different in actual operation. The research of power-cycle nested graph C₅m * P_m is divided into three parts.But in this paper we only research it when m = 1(mod3) and m >  4 .

The paper is organized as follows. In Section 2 ,we give the definitions that we shall consider. In section 3 includes the graphs with maximum edge-balanced index and using five-vertices sector subgraph-group to proof the lemmas. The main theorem is presented in Section 4. The final Section 5 contains the conclusion.

• II. PRELIMINARY NOTES

In graph theory, a graph G is an ordered pair ( v ( g ) , e ( g ) ) consists of vertex set V ( G ) and edge set e ( G ) , together with an incidence function that associates with each edge of G an ordered pair of vertices of G .

Definition 1 In graph G , let: f: E(G) ^ Z be an edge labeling function, that is to say, Ve e E(G) to define f (e) = 0 or 1 .The edge set labeled 0 or 1 is recorded as E(0) and E(1) , using e(0), e(1) to present the number of E(0), E(1) . According to the edge labeling f, we can define f+ : у ( g ) > {0,1}. If ex (0) is more than ex (1) , f+ (x) = о ,the vertex x is labeled 0 ;if ex (0) is less than ex (1), f+ (x) = 1 ,the vertex x is labeled 1;otherwise, the vertex x is unlabeled. e (0) or ex (1) presents the radix number of the edge collection that the edges linked x are labeled 0 or 1 .The radix number of the vertex setV(0),V(1) is presented by v(0) or v(1) .

Definition 2 Let: f : E ( G ) >  Z is an edge labeling function of G . If | e (0) — e (1) | < 1 , f is considered as an edge-friendly labeling of the graph G .

Definition 3 EBI ( G ) = {| v (0) — v (1)| : the edge labeling f is edge-friendly } is thought as the edge-balanced index set of the graph G , if there is an edgefriendly labeling f in a graph G .

Definition 4 C _m shows the graph contains m cycles, and the number of the vertices is added by power exponent from the inner cycle to the outer.

Definition 5 P m is a ray path that every road contains m points, and there are five branches at any points except the terminal point of each road.

Definition 6 The    power-cycle    nested graph Cm x Pm is the Cartesian product of Cm and Pms .

Example. Fig. 1 illustrates two graphs of C , x P m

C ₅ 2 x P _{2 s} C 5 3 x P ₃ 5 Fig. 1: two graphs of C 5 m X P m

For convenience ,we will have the following label for the nested network graph ： The vertices of the most inner circle in clockwise order are labeled as follows: ( 1 ) i , ( 1 ) 2 , ( 1 ) 3 , ( 1 ) 4 , ( 1 ) 5 . Similarly, from inside to outside ,the vertices of the most outside circle in clockwise are labeled as follows: ^{( m} L^{( m} V" , ^{( m} ) 5 ^m — 1 , ^{( m} ) 5 ^m .

(1)₄ >  (2), >  (3). >  - >  ( m — ²) m — 2 >  ( m — l) m — 1 >  ( m) m

That is:

• ⁽ i ; = ⁵⁽ i ;— 1 ^{— 1) +} Л — 1 ;1 <  i 1 <  5;1 <  j _t — 1 <  5;2 < ^k<  ^m )

• ^{( 1 )} 1    >^{( 2} ) 1   >^{( 3 )} 1 >  ^—   >^{( m — 1 )} 1    >^{( m} X;

• ^{( 1 )} 1   >^{( 2} ) 1 >^{( 3 )} 1 >  ^-   >^{( m — 1 )} 1   >^{( m} X;

• ^{( 1 )} 1 >^{( 2} ) 5 1 >^{( 3 )} 5 2 >---->^{( m — 1 )} 5 m — 2 >⁽ m ) 5(5 m — 2 — 1) + 4 ;

• ^{( 1 )} 1 >^{( 2} ) 5 1 >^{( 3 )} 5 2 >---- >⁽ m — ^{1 )} 5 m — 2 >⁽ m ) 5 m — 1 ;

^{( 1 )} 5 >^{( 2} ) 5 2 >^{( 3} ) 5 3 >     >⁽ m — ^{1 )} 5 m — 1 >⁽ m ) 5(5 m — 1 — 1) + 4 ;

^{( 1 )} 5 >^{( 2} ) 5 2 >^{( 3} ) 5 3 >---->⁽ m — ^{1 )} 5 m — 1 >⁽ m ) 5 m

The above says that the C 5 m x P m has 5 m paths.

Definition 7 A 1-vertex x is considered to be saturated, if the n edges linked to x satisfy e_x (1)= e_x (0)+1 ,when n is an odd number; e_x (1)= e_x (0)+2 ,when n is an even number ;otherwise, the 1-vertex x is unsaturated.A 0-vertex 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 8 Let m = 3t +1(t e N+) ,the induced subgraph of the vertices, which the ray paths through the points with the vertices on the 31 +1(t e N+) cycle as starting points and the vertices on the 3(t +1) + 1(t e N+) .cycle as the terminal points,is thought as the nested-cycle subgraph,denoted by уд t = 1,2,—, m—4

Definition 9 For the nested-cycle subgraph ,based on starting points of the ray paths, v_t ^ t = 1,2, - , m - 4 j ( _m >  4) is subdivided into sector subgraph equally.If the ray path’s starting points is on the d th cycle.Then the nested-cycle subgraph can be divided into 5 ^s sector graphs,denoted separately as 5 1 , 5 ₂<- , 5 5 _S .

Definition 10 For the sector subgraphs in the given nested-cycle subgraph, denoted 5 (0 = 5 ₅,+ 1 и 5 ₅ i ₊ 2 и 5 ₅,+ 3 и 5 ₅ i + 4 и 5 _м(0 <  i <  5 - 1) as five ^- vertices sector subgraph-group, and the label of the S ( i ) is in the same, denoted by 5 = 5 ( i ) .

• III.    LEMMAS AND PROOF

Lemma 1 For the power-cycle nested graph C5„ x Pm , when m = 4, max {EBI(C54 x P4 )} = 594

Proof: Firstly, construct the maximum edge-balanced index about C x P :

5 ⁴       4 5

Because the power-circle nested graph is nested by the power-circle graph and the ray paths graph. We will label respectively the power circle graph and the ray paths graph.

Step 1: We mark all edges as 0-edge which are in the paths of <1>,2>,<3>and in the circles of <4>,<5>,<6>.

< 1 >  (1) a (2) ь (3) c (4) d

'a e [ 1,5 ] ; b = 3 + w + 5 5 , w e [ 0,2 ] , 5 e [ 0,4 ] ; ' c = 11 + w + 25 5 , w e [ 0,14 ] , 5 e [ 0,4 ] ;

^ d = 51 + w + 125 5 , w e [ 0,74 ] , 5 e [ 0,4 ]      _?

< 2 >  (2) ь (3) c (4) d

' b = 1 + w + 5 5 , w e [ 0,1 ] , 5 e [ 0,4 ] ;

c = 5 + w + 25 5 , w e { 0,5 } , 5 e [ 0,4 ] ;

_к d = 21 + w + 125 5 ,w e [ 0,4 ] и [ 24,29 ] , 5 e [ 0,4 ] ^

< 3 >  (3) c (4) d

^ c = 1 + w + 25 5 , w e [ 0,3 ] и [ 5,8 ] , 5 e [ 0,4 ] ;

^ d = 1 + 5 w + 125 5 , w e [ 0,3 ] и [ 5,8 ] , 5 e [ 0,4 ]

<4> The 2th circle and the 3th circle.

<5>(4) d (4) ( d = 2 + 2 w + 5 5 + 125 f , w e [ 0,1 ] ; 5 e [ 0,3 ] и [ 5,8 ] ; f e [ 0,4 ] ) <  6 >  (4) d (4) d + 1 ( d = 47 + 2 w , w e [ 0,16 ] )

Step 2: On the basis of step1,

(3) _c (4) _d ( c = 11 + w , w e [ 0,5 ] , d = 51 + w , w e [ 0,29 ] ), (2) 2 (3) 10 , (3) 10 (4) 47 , (3) 10 (4) 48 , (3) 10 (4) 49 and

⁽³⁾ 10 ⁽⁴⁾ 50 have been marked 0-edges,then turn them from 0-edges to 1-edges.

Step 3: The other edges in the C, x P are labeled as1. 5 ⁴       4 5

In the graph, there are 1555 edges,of which 777 are the 0-edges.According to the definition of edge-friendly labeling, I e (0) - e (1) I < 1 ,we can get the edge-friendly labeling of the labeled graph by calculation. All the vertices

• ( 2 ) . ( i = 3 + w + 5 5 , w e [ 0,2 ] , 5 e [ 0,4 ] ) ,

• ( 3 ) . ( i = 5 + 25 w , w e [ 0,4 ] ) , ( 3 ) i ( i = 17 + w , w e [ 0,8 ] ) ,

( 3 ) i ( i = 35 + w + 25 5 , w e [ 0,15 ] , 5 e [ 0,3 ] ) are labeled as 0.There are 93 0-vertices,so | v (1) - v (0)| = |687 - 93| = 594 .

We can prove EBI ( C 5 ₄ x P ₄) = 594 is the maximum of edge-balanced index in the graph C 5₄ x P 4 .

In order to change the label of any 0-vertex into 1-vertex or unlabeled, we need to interchange 4 0-edges and 1-edges at least, but any of the 1-vertex’s label changes, we only need to interchange 2 0-edges and 1-edge at least. It is obvious that the interchanging must bring v (0) increases or remains unchanged, and meanwhile v (1) decreases definitely. Thus the value of I v ( 1 ) - v ( 0 )| reduces. That’s to say:

max { EBI ( C 5 4 x P ₄ 5 ) } = | v (1) - v (0)| = 594

Lemma 2 In the C_ x P , for the five-vertices 5        m ₅

sector subgraph group 5 , max { EBI ( 5 ) } = 589

Proof:Because these five-vertices sector subgraph-group have the same characteristics of edge and vertex. We only give the label of 5 = 5(0) = 5, и 52 и 53 и 54 и 55, the other   five-vertices 5(i)(1 < i < 5a-1 -1)   sector subgraph-group have the same label as S(0) .

Firstly, construct the maximum edge-balanced index about S :

Step 1: We mark all edges for 0-edge which are in the paths of <1>,<2>,<3>and in the circle of <4>,<5>,<6>,<7>.

< ¹ > (^d) a (^d + 1 ) b (^d + ² ) c (^d + ³ ) d

'a e [ 1,5 ] ; b = 1 + w + 5 5 , w e [ 0,1 ] , 5 e [ 0,4 ] ;

c = 1 + w + 25 5 , w e [ 0,9 ] , 5 e [ 0,4 ] ;

^ d = 1 + w + 125 5 , w e [ 0,49 ] , 5 e [ 0,4 ] ,      ^

^ b = 3 + w + 5 5 , w e [ 0,2 ] , s e [ 0,4 ] ;

< 2 > ( а+ 1 ) b ( а+ ² ) , ( s+ 3 ) d

c = 11 + w + 25 s , w e [ 0,1 ] o [ 5,7 ] u [ 10,11 ] , s e [ 0,4 ] ;

_v d = 51 + w , w e [ 0,9 ] u [ 25,39 ] o [ 50,59 ]

< 3 > ( a+ 2 ) c ( a+ 3 ) d

^ c = 13 + w + 25 s , w e [ 0,2 ] o [ 6,7 ] u [ 10,12 ] , s e [ 0,4 ] ; ' _v d = 61 + w + 125 s , w e { 0,5,10,30,35,50,55,60 } , s e [ 0,4 ]_y

< 4 >  ( d + 2) th

< ⁵ > (^d + 1 ) b (^d + 1 ) b + 1

( b = 1 + w + 5 s ,

V w ^e[ O,¹ ]^ ⁴ }

'

s e [ 0,4 ] _y

< ⁶ > ( 5 + ³ ) d (^d + ³ ) d + 1

' d = 62 + 2 w + 5 s + 125 f , w e [ 0,1 ] ; ' _V s e [ 0,2 ] u [ 6,7 ] u [ 10,12 ] , f e [ 0,4 ] _y

< 7 >  ( 5 + 3 ) d ( d + 3 ) d _{+ 1} ( d = 1 + 2 w , w e [ 0,4 ] )

Step 2: On the basis of step1,

(^d + ² ) c ( 3 + 3 ) ,

' ^c = ^{1 +} w • w ^{e[ 0},1 1 •'

_V d = 1 + w , w e [ 0,9 ] ^

v ( 1 ) decreases, so the value of v ( 1 ) - _v ( 0 )| reduces.

That’s to say: max { EBI ( 5 ) } = 589.

Step 3: The other edges in the S are labeled as 1.

In the S graph, there are 1500 edges,of which 775 are the 0-edges.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

( d + 1 ) b ( b = 1 + w + 5 s , w e [ 0,1 ] , s e [ 0,4 ] ) ( 5 + 2 ) _c ( c = 1 + w + 25 s , w e [ 2,11 ] u [ 15,17 ] u [ 20,21 ] , s e [ 0,4 ] ) ( 5 + 2 ) c ( c = 26 + w + 25 s , w e [ 0,1 ] , s e [ 0,3 ] )

are 0-vertices, v ( 0 ) =93 .In order to satisfy the index calculation of nested-cycle,the number of vertex of S doses’t include ( S )_e ( a e [ 1,5 ] ) .Thus | v (1) - v (0)| = |682 - 93| = 589.

We can prove EBI ( 5 ) = 589 is the maximum of edge-balanced index in the graph S .

In this labeled graph, the vertices in S are all saturated.

In order to turn the label of any 0-vertex to1-vertex or unlabeled, we need to interchange 4 0-edges and 1-edges at least, but any of the 1-vertex’s label changes, only need to interchange 3 0-edges and 1-edges at least.Obviously, if change 0-vertex’s label ,then v(0) increases or remains unchanged, and meanwhile when m = 1(mod3) and m > 4, max { EBI ( C5m

19 х 5 ^{m - 1} + 1

х P ) =---------- m ₅

Proof : For m = 4 , the formula can be proved by Lemma 1.

When m >4 , firstly,construct the graphics with the maximum edge-balanced index of C 5 _m x P m .

Obviously,

^C 5 m Х P m 5 = C 5 4 Х ^p _% J U V t = 1

V J

,the

maximum

edge-balanced index labeling method of C ₄ x P 4_; is the same as we structure in lemma 1. For the nested-cycle m - 4

subgraph I J v consists 5—^-125 5 ,the 5 in the / = 1 i                      124

Vt( t = 1,2,™, m-4' ,whose maximum edge-balanced index labeling method is the same as we construct in lemma 2.During the process of label , we know the C^m x Pm satisfies the friendly labeling,and the characteristic of vertices remain unchanged,so this graphics is the maximum edge-balanced index.

We shall prove max { EBI ( C m x P m ) } = ^{19 x} 5^ —+ 1 .

According to lemma 2,we know max {ebi(5)} = 589, if the starting points at the 5th = 3t +1(t e N+) cycle,then the graph can be divided into 5d sector subgraphs and 5s 1 five-vertices sector subgraph-group.That’s to say v4t = 1,2,—,m- 4^ has 53t five-vertices sector subgraph-group.By computing, we can get the maximum edge-balanced index of Cm, x Pm .

m — 4

max{EBI(C5m x Pm )} = max {EBI ( C54 x P4 )} + ^ max {EBI ( Vt)} t=1

= 594 + 589 x 5 3 +589 x 5⁶ + — + 589 x 5 ^{m — 4}

19 x 5 ^{m — 1} + 1

The proof is completed.

Lemma 4 For S in nested-cycle subgraph

V „ — 4 ( m >  7) , { 588,587, — ,1,0 } c EBI ( S ) .

( 5 + 2 ) c ( 5 + 3 ) d

45 + 3 ) d ( 5 + 3 ) d + 1

Proof : In the lemma 2,we get max { ebi ( S ) } = 589 .

4 c = 13 + w + 55+25f, 4 w e[0,2], 5 e{0,2}, f e[0,4]; d = 61+5 w +1255, чwe[0,2]u[10,11],5 e[0,4] ^

we can obtain 25 labeled graphs of odd edge-balanced indexes which are { 89,87, — ,41 }

we exchange (2 k — 1) r (2 k ) ₅ and (2 k ) ₅ (2 k ) _{5 + 1} which

Step5: In turn exchange

( 5 + 2 ) c ( 5 + 2 ) c + 1 ^ ( 5 + 2 ) c + 1 ( a + 3 ) d

are 0-edge and 1-edge respectively. First, build an odd index set:

4 c = 13 + w + 55+25f, " w e[0,1], 5 e{0,2}, f e[0,4]; d = 70+5 w + 1255, чwe{0,1,10,11},5 e[0,4]

Step 1: In turn exchange

(^d + 2 ) . (^d + 3 ) d

4^d + 3 ) d (^d + ³ ) d + 1

' c e [ 3,10 ],           '

d = 11 + w + 5 5 ,

^ w e [ 0,2 ] , 5 e [ 0,7 ] ,

we can

obtain 24 labeled graphs of odd edge-balanced indexes which are { 587,585, — , 543,541 } .

Step 2: In turn exchange

(^d + 3 ) c ( 5 + 4 ) d 45 + 3 ) d ( 5 + 3 ) d + 1

⁴ c = 26 + w + 25 5 ,            '

w e [ 0,9 ] , 5 e [ 0,3 ] ;

d = 126 + w + 55 +125f, ч w e [0,2], 5 e [0,9], f e[0,3].

we can obtain 120labeled graphs of odd edge-balanced indexes which are { 539,537, - , 299,301 } .

Step 3: In turn exchange

we can obtain 20 labeled graphs of odd edge-balanced indexes which are { 39,37, — 3,1 }

Even index set structures as follows:

Stepl: Exchange ( ^{d + 3 )} ( ^{d + 3 )} 2 ^ ^{(d + 2 ) (d + 3 )} 2 , we can obtain one labeled graphs of even edge-balanced indexes which is { 588 } .

Step2:Repeat from the first to fifth step as we construct the odd index sets .Thus we can obtain these labeled graphs of even edge-balanced indexes which are respectively { 586,584, — , 2,0 } .

The proof is completed.

Lemma 5 For every of S in the nested-cycle subgraph,

V_t (1 <  t <  m _ 7)( m >  10), { 588,587, — ,1,0 } c EBI ( S ) .

( 5+ ³ ) c ( 5+ 4 ) d ^ ( a + 3 ) d ( a + 3 ) d + 1

c = 11 + w + 25 5 ,                   '

w e[0,1]u[5,7]u[10,11], 5 e [0,4]; d = 51 + w + 55+125f, w e [0,2], ч 5 e[0,1]u[5,7]u[10,11], f e[0,4] , we can obtain 105 labeled graphs of odd edge-balanced indexes which are {299,333, —,93,91}.

Step 4: In turn exchange

We know the (5)a (a e[1,5]) of SV^ regards as the poinds on the (d + 3)th circle of SV, when we calculate .One SV> of Vt corresponds to 125 SV , we select 117 SVfrom 125 SV + ,we change them as the following order ,in turn exchange ,             ,                ,           , I a e [1,5]

(^d + 1 ) b + 1 (^d + 1 ) b o h' ' 1 ) b (^d) a l. -J r_n41 ^ b = 5 + 5 w , w e [ 0,4 ]

( 3 ) c ( 4 ),

o ( 4 ) d ( 4 ) d + 1

,we can

change 585 1-vertex on the third circle of S_V into unlabeled, so that the index can decrease by 585, respectively 585 labeled graphs are obtained. By the lemma 2, max{ EBI ( S )} = 589 ,so { 588,587, ^ ,5 } c EBI ( S V ) , then we select one S V again , in turn exchange

I a e [ 1,4 ]             ^

( s+ 1 ) ( s+ 1 ) o ( s+ 1 ) ( a ) l                       I ’

’b+1V     bb          bbV k (b = 5 + 5 w, w e[0,3]J similarly, we can change 4 1-vertex on the third circle of SV into unlabeled,so that the index can decrease by 4,respectively 4 labeled graphs are obtained, so{4,3 21} cEBI(SV).That is {588,587,-,0} cEBI(SV )(1

The proof is completed.

Lemma 6 In nested-cycle subgraph C₅„ x P_m ,when m = 4 , {593,591,... ,1,0} c EBI(C54 xP4 ) .

Proof:Below transform is based on the biggest index labeled graph constructed form lemma 1, and every step 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: In turn exchange

(³)c (⁴)

^o(4)d⁽⁴⁾d+1

। c = 1 + w + 5 s + 25 f, ' w e [0,3], s e [0,1], f e [0,4]; d = 1 + 5 w + 25 s +125 f, v w e [0,3], s e [0,1], f e [0,4] j

we can obtain 40 labeled graphs of even edge-balanced indexes which are {592,590, —,516,514} .

Step 2: In turn exchange

। c = 36 + w + 5 s, w e[0,14],    '

s e[0,3];

d = 176 + w + 5 s +125 f, vwe[0,2],s e[0,14], f e[0,3]J we can obtain 180 labeled graphs of even edge-balanced indexes which are{512,508,-,156,154} .

Step 3: In turn exchange

(3)c (4)d o(4)d (4)d+1

। c = 30 + 5 w + 25 s,

we[0,1], s e[0,3];

d = 146 + w + 25 s +125 f,

(we[0,2],s e[0,1], f e[0,3]J

we can obtain 24 labeled graphs of even edge-balanced indexes which are {152,150 > •• ,108 106} .

Step 4: In turn exchange

Ic = 17 + w, w e [0,8];              ^

⁽³⁾c ⁽⁴⁾d^O(4)d⁽⁴⁾d+11,                                  r_n81l,

^d = 81 + w + 5s, w e [0,2], s e [0,8]J

we can obtain 27 labeled graphs of even edge-balanced indexes which are {104,102,^, 54,52} .

Step5: In turn exchange

(3)c (3).

о

(3) c (4),

। c = 26 + w + 5 s+25 f, w e[0,2], s e[0,1], f e[0,3];

d = 126+5 w +125 s,

(we[0,2]u[5,7],s e[0,3]     J

we can obtain 24 labeled graphs of even edge-balanced indexes which are {50,48,,6,4}.

Step6: In turn exchange

(1)1 (²)1 о (²)1 (²)2, (1)2 (²)6 о (²)6 (²)7 ,we can obtain 2 labeled graphs of even edge-balanced indexes which are {2,0} .

Odd index set structures as follows:

Stepl: Exchange (1) (2)₃о (1) (1)₂,we can obtain one edge-balanced indexes which is {593} .

Step2: Repeat from the first to fifth step as we construct the odd index sets .Thus we can obtain these labeled graphs of even edge-balanced indexes which are respectively{586,584,^,2,0}.

Step3: Exchange (1)1 (2)1 o(2)1 (2)2 ,we can obtain one edge-balanced indexes which is {1}.

The proof is completed.

Lemma 7 In the nested graph with power-cycle

C₅m x Pm , when m = 1(mod 3) and m > 4,

. 19x5^m ' -3 19x5^m ' -7     .

^{-----4-----,-----4-----, -^,1,0} ^{c EBI (C}5 m^xPm 5)

Proof: ©When m = 4 , the formula can be proved by lemma 6.

Now, we prove the formula was established when m > 4 . Below transform is based on the biggest index labeled graph constructed form lemma 3.

Step 1: According to changing method of S in lemma 4.By lemma 4,every S_v ’s index in V₁ can reduces by 589, when we exchange, we can obtain 589 labeled graphs conversely, so {589,588, -,0}c EBI (S).

Step 2: To select 118 S _v fromV₁, in turn exchange

(a^e[1,5]           1 , we can

( ) b+i( ) b ^( ) b( ) a V ь = 5 + 5 w, w

Step3: Then we select one S from V , in turn v1                 1

exchange ⁽⁵⁾*+1⁽⁵⁾* ^ ⁽⁵⁾*⁽⁴⁾„

a e [1,4]

b = 5 + 5 w, w e[0,3]

we can obtain 4 edge-balanced indexes which are

{3,2,1,0} ,so {3,2,1,0} c EBI(C57 x P.y

= C54 X P45 U U v

t=1

V 7

Step 1: According to changing method of S in lemma 4.By lemma 4,every SV ’s index in V_m4 can reduces by

589, when we exchange, we can obtain 589 labeled graphs conversely, vm-4has 5^m-4Svm4 ,which have the 33

same change method asS in lemma 4,so that the index can decrease by 589x5^m-4 ,when we exchange, we can obtain     589 x 5^m-4     labeled graphs. So

, 19 x 5m^-1- 3 19 x 5m^-1- 7     19 x 5m^-1- 2356 x 5m^-4+1]              „

^{----4----,----4----^----------4----------^{C EBI(C}5■^{X P}m5 )

Step 2: According to changing method of S in lemma 5.All the S of v,(1 < t < m—7) have the same t3

changing method asS in lemma 5,so that the index can

- 2375

.That is

a         .   19 x 5^m—4

decrease by

119 x 5^m-4- 3 19 x 5^m-4 {₄,₄

—

7                    I

—,—,595,5941cEBI(C5„ xPm5)^.

Step 3: Repeat step 2 and step 3, when m = 7 , we can obtain 594 labeled edge-balanced graphs whose indexes are {593,592,^,0} ,So

119 x 5^m-1- 3 19 x 5^m-1- 7 {₄,₄

1,0} c EBI(C5m X Pm5)(m > 10).

The proof is completed.

• IV.    THEOREM

According to lemma 3 and lemma7, we can get the following theorem.

Theorem 1: In the nested graph with power-cycle C₅m x P_m; when m = 1(mod3) and m > 4,

EBI ( C5 m X Pm 5) = {

19 X 5 m +1 19 X 5 m^-1

4 Г

- 3

1,0}

• V.    CONCLUSION

In this paper ,in order to study the edge-balanced index sets of the nested graph with power-cycle C₅m x Pm ,we introduced the five-vertices sector subgraph-group, showing the proof of the computational formula, at the same time giving the construction of the corresponding graphs. The resulting work using the same method will be investigated in a future paper.

ACKNOWLEDGMENTS

This work was financially supported by Applied Mathematics Provincial-level Key Discipline of Henan Province, Operational Research and Cybernetics Key Discipline of Henan Polytechnic University and the Education Department of Henan province science and technology research project.