Transcript On the Edge Balance Index of the L

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