Transcript Slides - Stonehill College

On the Edge-Balance Index of Flux
Capacitor and L-Product of Star by
Cycle Graphs
Meghan Galiardi, Daniel Perry, Hsin-hao Su
Stone hill College
Labeling of the Graphs
• The edges of the graph are labeled by the group
Z2={0, 1}
• The vertices are labeled according to the adjacent
edges
– Vertex labeled 0 if the number of edges adjacent
labeled 0 is greater than the edges labeled 1
– Vertex labeled 1 if the number of edges adjacent
labeled 1 is greater than the edges labeled 0
– Vertex unlabeled if the number of edges adjacent
labeled 0 is equal to the edges labeled 1
Edge-Friendly Graphs
• The graphs are said
to be edge-friendly if
the number of 1edges and 0-edges
differ by no more
than 1.
|e(0)-e(1)|≤ 1
Example:
total edges = 12
e(0) = 6
e(1) = 6
Edge-Balance Index Set
• The edge-balance index is
the difference between 0vertices and 1-vertices
EBI =|v(0) – v(1)|
• The edge-balance index set
for graph G is the set of all
possible edge-balance
indices that G can have
• We looked for the edgebalance index sets of two
types of graphs
Example:
v(0) = 3
v(1) = 2
EBI = 1
Flux Capacitor Graphs
• Definition : A flux capacitor graph is composed of two
different types of graphs, a star graph and a cycle graph. A star
graph, St(n), consists of a center vertex and n surrounding
vertices each connected to the center. A cycle graph, Cm,
consists of m vertices each connected to 2 others to form a
cycle where m≥3. A flux capacitor graph, FC(n, m), is a St(n)
graph where on each outer vertex there is a graph Cm.
St(3)
C3
FC(3, 3)
Theorems
• EBI(FC(n, m)) =
{0, 1, … , n-1} if m is odd
{0, 1, … , n} if n is odd and m is even
{0, 1, … , n-1} if n is even and m is even
How we proved it
• Started with FC(n, 3) and FC(n, 4)
• First we looked for the most efficient way to label
the graphs as to achieve the highest EBI
• From the highest EBI we looked at how we can
rearrange the graphs to decrement the EBI by 1
• We rearranged the graphs as many times as it
took to achieve EBI from the highest all the way
to 0
• The results we found also generalized for any
FC(n, m)
FC(n, 3)
EBI(FC(n, 3)) = {0, 1, … , n-1}
Most efficient way to label is to
label the star with all 1-edges and
then alternate the cycle with 0 and
1-edges. This creates EBI = n-1.
To decrease the EBI by one, simply switch
a 0-edge and a 1-edge on one of the
cycles. This changes the 0-vertex to a 1vertex and adds an additional 0-vertex.
Since v(0) was greater that v(1). This
change causes the EBI to decrease by 1.
|v(0) – v(1)| = 1
|v(0) – v(1)| = 0
EBI = {0, 1}
Note: We assumed that e(0)≥e(1) and by our labeling v(0)≥v(1). The opposite can also be
assumed, but the results for the EBI will still be the same so we only have to look at one
case
FC(n, 4) if n is even
EBI(FC(n, 4)) = {0, 1, … , n-1}
When n is even the most efficient
way to label the graph is shown
below. This creates EBI = n-1.
Again the edges can be rearranged to
decrement the EBI by 1 each time,
and all the EBI from n-1 all the way
to 0.
|v(0) – v(1)| = 1
|v(0) – v(1)| = 0
EBI = {0, 1}
FC(n, 4) if n is odd
EBI(FC(n, 4)) = {0, 1, … , n}
The same can be done when n is
odd, there is just a slightly different
way of labeling the graph for the
highest EBI. This creates EBI = n-1.
|v(0) – v(1)| = 3
|v(0) – v(1)| = 2
Again the edges can be rearranged to
decrement the EBI by 1 each time,
and all the EBI from n-1 all the way
to 0.
|v(0) – v(1)| = 1
EBI = {0, 1, 2, 3}
|v(0) – v(1)| = 0
FC(n, m)
The results for EBI(FC(n, m)) generalize from FC(n, 3) and FC(n, 4)
Example: EBI(FC(4, 7)) = {0, 1, 2, 3}
|v(0) – v(1)| = 3
|v(0) – v(1)| = 2
|v(0) – v(1)| = 1
|v(0) – v(1)| =0
L-Product of Cycle by Star
• Definition: An L-product of cycle by star graph
is the same as a flux capacitor graph, the only
difference being there is an additional cycle,
Cm, on the center vertex of the star. It is
represented as St(n)xLCm.
St(3)xLC3
Theorems
• EBI(St(n)xLCm) =
{0, 1, … , n+1} if m is odd
{0, 1, … , n+1} if n is odd and m is even
{0, 1, … , n} if n is even and m is even
How we proved it
• We started with FC(n+1, m). By removing 1 edge and merging
2 vertices we can create St(n)xLCm
• When m is odd, EBI(FC(n, m)) = {0, 1, … , n-1}
• EBI(FC(n+1, m)) = {0, 1, … , n}
• FC(n+1, m) has an even number of edges. Removing an edge
will keep the graph edge friendly and cause the EBI to change
at most by 1
• So EBI(St(n)xLCm) = {0, 1, … , n+1} when m is odd
How we proved it
•
•
•
•
When n+1 is even and m is even,
When n is even EBI(FC(n, m)) = {0, 1, … , n-1}
When n+1 is even EBI(FC(n+1, m)) = {0, 1, … , n}
FC(n+1, m) has an even number of edges.
Removing an edge will keep the graph edge
friendly and cause the EBI to change at most by 1
• Starting with n+1 even and removing the edge
makes n odd, while m stays even
• So EBI(St(n)xLCm) = {0, 1, … , n+1} when n is odd
and m is even
How we proved it
• When n+1 is odd and m is even,
• FC(n+1, m) has an odd number of edges.
Removing an edge may not keep the graph
edge friendly so the previous method does
not work
• Results from the flux capacitor graphs could
not be used so we created a most efficient
way to label
• It was found EBI(St(n)xLCm) = {0, 1, … , n} when
n is even and m is even
St(2)xLC3
|v(0) – v(1)| = 3
|v(0) – v(1)| = 2
|v(0) – v(1)| = 1
n is even, m is odd
EBI(St(n)xLCm) = {0, 1, … , n+1}
EBI = {0, 1, 2, 3}
|v(0) – v(1)| = 0
Conclusions
• EBI(FC(n, m)) =
{0, 1, … , n-1} if m is odd
{0, 1, … , n} if n is odd and m is even
{0, 1, … , n-1} if n is even and m is even
• EBI(St(n)xLCm) =
{0, 1, … , n+1} if m is odd
{0, 1, … , n+1} if n is odd and m is even
{0, 1, … , n} if n is even and m is even