On the Edge Balance Index of the L

March 20, 2018 | Author: Anonymous | Category: N/A
Share Embed


Short Description

Download On the Edge Balance Index of the L...

Description

Dan Bouchard, Patrick Clark*, HsinHao Su Stonehill College

Let G be a simple graph with vertex set V (G) and edge set E(G). Let Z2 = {0, 1}.

1

1

1

x

x

0 An edge labeling f : E(G) → Z2 induces a vertex partial labeling f+ : V (G) → Z2 defined by f+(v) = 0 if the edges labeled 0 incident on v is more than the number of edges labeled 1 incident on v, and f+(v) = 1 if the edges labeled 1 incident on v is more than the number of edges labeled 0 incident on v.

0 0

0

0



ef (0) = # of 0-edges ef (1) = # of 1-edges vf (0) = # of 0-vertices vf (1) = # of 1-vertices ef (0) = 5 ef (1) = 4 vf (0) = 5 vf (1) = 2

0

1

0 1

0



1

0

1

1

0

0

0

1

0

0

0

An edge labeling f of a graph G is said to be edge-friendly if |ef (0) − ef (1)|≤ 1. A graph G is said to be an edgebalanced graph if there is an edge-friendly labeling f of G satisfying |vf (0) − vf (1)| ≤ 1.

The edge-balance index set of the graph G, EBI(G), is defined as {|vf (0) − vf (1)| : the edge labeling f is edge-friendly.}.



An L-product with cycle by star graph is composed of a cycle graph and n star graphs. St(2) C3XLSt(2)

C3 St(2)

St(2)



In particular, the focus of our research consisted of analyzing graphs of the form CnXLSt(m), where m is even and greater than 2.



In a CnXLSt(m) m is even and greater than 2, we notice that all of the vertices are grouped into n packages. These packages consist of m degree 1 vertices and 1 degree m+2 vertex.

Package

Each of the m degree 1 vertices must be labeled, and it's labeling is completely dependent on the labeling of it's incident edge. The degree m + 2 vertex in each package ho can be either labeled or unlabeled.







Remember that for every friendly labeling, the EBI Is given by |vf (0) − vf (1)| . For the purposes of my study, it is essential to determine the highest EBI possible for a particular graph. Two main strategies seem apparent, either maximize vf (0) or minimize vf (1).

Although a similar argument can be made otherwise, lets consider a graph in which the total number of vertices is even.

C3XLSt(4)

𝑛 𝑚+1 +1

Number of 0-edges: , where n is the 2 number of vertices accounted for by the cycle, and m is the number of outer vertices for each star. We have m+2 edges in each package, and to maximize vf (0), we must label in such a way to make as many of the red vertices as possible 0vertices. 𝑚+2

This requires that : + 1 edges in a package be 02 edges, and we place these on edges outside of the cycle, as each vertex out side the cycle is only degree 1.. By doing this for as many packages as possible before we run out of 0-edges to work with, we will maximize vf (0)

0 0

0 0

0

𝑛 𝑚+1

Number of 1-edges: , where n is the 2 number of vertices accounted for by the cycle, and m is the number of outer vertices for each star.

C3XLSt(4)

We have m+2 edges in each package, and to minimize vf (1), we must label in such a way to make as many of the red vertices as possible unlabeled. 𝑚+2 2

This requires that : edges.

edges in a package be 1-

By doing this for as many packages as possible before we run out of 1-edges to work with, we will minimize vf (1)

1

1 1

x



For the case of maximizing vf (0), using the division algorithm we



can write : =( + 1) k + r, where k is the number of 2 2 packages where we were able to create a 0-vertex on the cycle, and r is the number of 0-edges that left to be placed on the outer edges. For the case of minimizing vf (1), using the division algorithm we



𝑛 𝑚+1

𝑚+2

𝑛 𝑚+1

𝑚+2

can write : =( ) q + j, where j is the number of packages 2 2 where we were able to create an unlabeled vertex on the cycle, and r is the number of 0-edges that left to be placed on the outer edges. By using algebra to compare these equations, we arrive at the result that k>q, allowing us to conclude that it is more effective to maximize vf (0)

Step 1 - Label each of the n edges of the cycle with a 1. Step 2 - For as many packages as possible given the amount of 0-edgeswe have, label one more than half of the edges incident to a degree 1 vertex in a package with a 0. Step 3 - Starting at the package next to the last package we were able to label by Step 2, label each degree 1 edge with a 1 until we have used all of our 0-edges. Step 4 - Label the rest of our edges with 1.

0

0

0

0 1

1

1

0

1

1 1

1

0 0 0



  

   

Given our equations relating the total number of 0-edges and 1-edges to the number required to make the degree m+2 vertex in a package the same label, we were able to conclude the following Equation 1:

𝑛 𝑚+1 +1 2 𝑛 𝑚+1 +1 2

=(

𝑚+2 + 2 𝑚+2 + 2

1) k + r.

Equation 2: =( 1) q + j Theorem: The Highest Edge Balance Index for any Cn xL St(m) graphs where m is even and greater than 2 is 𝑚+2 {2k+1 if n is odd and r < } 2 𝑚+2 {2k+2 if n is odd and r >= } 2 𝑚+2 {2q if n is even and j < } 2 𝑚+2 {2q+1 if n is even and j >= } 2





After developing the algorithm to produce the highest EBI for our graphs, we considered how to lower the EBI for our graphs to produce and EBI set. We proceeded by considering how we can make switches within our highest EBI labeling that can effectively lower our EBI by 1 or 2.



𝑚+2 2

If a packages contains at least +1 0-edges and at least 1 1-edge, we can make a label switch within that package to reduce the EBI by 2.

Switch!!!!





      

For any friendly labeling that contains at least 1 package that 𝑚+2 is composed of less than -1 0-edges or 1-edges and at 2 𝑚+2 least 1 package that is composed of exactly +1 edges of 2 the same label, we can make a label switch to increase our EBI by 1. . . . . . switch!!! . . .



Theorem: The Highest Edge Balance Index for any Cn xL St(m) graphs where m is even and greater than 2 is



{0,1,2,…,



{0,1,2,…,



{0,1,2,…,



{0,1,2,…,

𝑚+2 2k+1 if n is odd and r < } 2 𝑚+2 2k+2 if n is odd and r >= } 2 𝑚+2 2q if n is even and j < } 2 𝑚+2 2q+1 if n is even and j >= } 2

View more...

Comments

Copyright © 2017 DOCUMEN Inc.