Transcript On the Edge Balance Index of Flux Capacitor and L

On the Edge Balance Index of Flux
Capacitor, Centipede,
L-Product
Graphs
Meg Galiardi and Dan Perry
EBI(FC(n,m)) =
{0,1,. . .,n-1} if m is odd,
{0,1,. . .,n-1} if n is even and m is even,
{0,1,. . .,n} if n is odd and m is even.
Abstract- Let G be a graph with vertex set V (G) and edge set
E(G), and let Z2 = {0, 1}. A labeling f : E(G) → Z2 of a graph G is
said to be edge-friendly if {|ef (0) − ef (1)| ≤ 1}. An edge-friendly
labeling f induces a partial vertex labeling f+ : V (G) → Z2 defined
by f+(x) = 0 if the number of edges labeled by 0 incident on x is
more than the number of edges labeled by 1 incident on x.
Similarly, f+(x) = 1 if the number of edges labeled by 1 incident on
x is more than the number of edges labeled by 0 incident on x.
f+(x) is not define if the number of edges labeled by 1 incident on
x is equal to the number of edges labeled by 0 incident on x. For i
Є Z2, let vf (i) = card{v Є V (G) : f+(v) = i} and ef (i) = card{e Є E(G)
: f(e) = i}. 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}.
EBI(St(n)XLCm) =
{0, 1...n + 1} when m is odd
{0, 1...n} when n is even and m is even
{0, 1...n + 1} when n is odd and m is even
EBI(Ce(n,3)) =
{0,1} if n=3,
{0,1,. . .,k} if n=2k is even, kЄZ
{0,1,. . .,k-1} if n=2k+1 is odd, kЄZ, k≥2.
Graph edges are labeled by either 0 or 1. For an edge-friendly
labeling, the total difference in 0 and 1 edges can be at most 1.
Vertices are then labeled 0 if the number of 0-edges adjacent to it
is more than the number of 1-edges. Vertices are labeled 1 if the
number of 1-edges adjacent to it is more than the number of 0edges. If there are an equal number of 0 and 1 edges adjacent to
a vertex, it remains unlabeled.
Flux Capacitor Graph (FC(3,8))
The edge balance index (EBI) is the set of all possible difference
in 1 and 0 vertices such that the graph has an edge-friendly
labeling.
A flux capacitor graph is composed of two different types of
graphs, a star graph and a cycle. A star, St(n), consists of a
center vertex, s0, and n other vertices each connected to the
center. A cycle, 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
Cm graph.
If n=2k+1 is odd, where kЄZ,
EBI(Ce(n,4)) =
{0,1,. . ., 3 + 8[(k-1)/5]} if k-1=0 in Mod 5,
{0,1,. . ., 4 + 8[(k-2)/5]} if k-1=1 in Mod 5.
{0,1,. . ., 6 + 8[(k-3)/5]} if k-1=2 in Mod 5.
{0,1,. . ., 8[(k+1)/5]} if k-1=3 in Mod 5.
{0,1,. . ., 9 + 8[(k-5)/5]} if k-1=4 in Mod 5.
If n=2k is even, where kЄZ,
EBI(Ce(n,4)) =
{0,1,. . ., 3 + 8[(k-2)/5]} if k-2=0 in Mod
{0,1,. . ., 4 + 8[(k-3)/5]} if k-2=1 in Mod
{0,1,. . ., 6 + 8[(k-4)/5]} if k-2=2 in Mod
{0,1,. . ., 8[(k)/5]} if k-2=3 in Mod 5.
{0,1,. . ., 9 + 8[(k-6)/5]} if k-2=4 in Mod
L-Product of Star by Cycle (St(4)XLC4)
An L-product graph of star by cycle 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.
A Centipede Graph is composed of two cycle graphs. A cycle, Cn,
consists of n vertices each connected to 2 others to form a cycle
where n≥3. There is then a cycle, Cm, attached to each vertex of
Cn. Ce(n,m) is the abbreviation.
Centipede Graph (Ce(7,4))
5,
5.
5.
5.
If m ≥ 5,
EBI(Ce(n,m)) =
{0,1,. . ., n} if m is odd,
{0,1,. . ., n + 1} if m is even and n is odd.
{0,1,. . ., n} if m and n are even.