Transcript Slide 1

Terry Rose
Professor Hsin-hao Su
Background

Graph




Vertices: V(G) and v(n)
Edges: E(G) and e(n)
Undirected
Simple

|v(0)-v(1)|
 |e(0)-e(1)|
 Label

Balance Index Sets
Example of BI
v(0) = 3
v(1) = 3
|v(0)-v(1)| = 0 ≤1
e(0) = 2
e(1) = 1
|e(0)-e(1)|= 1
BI(G) = {0,1,2}
How exactly to calculate BI

Every vertices combination
 Place 0’s first then remaining vertices are 1’s
Balance
 Remove redundant balance indexes

Example
Tracker for set [0, 1, 2]
0 appeared 6 times
1 appeared 12 times
2 appeared 2 times
Tracker for set [0, 1, 2]
0 appeared 3 times
1 appeared 6 times
2 appeared 1 times
Graph Theory

Cycle graph
 n vertices in a circle
 Inner vertices

Star graph
 m vertices to each inner vertex
 Outer vertices

 Number of vertices = m*n+n

First Case m is odd
 Number of vertices is even

Second Case m is even
 Number of vertices is odd


composes an inner cycle
to each vertex of

Composed of two disjoint sets, A and B
 |A| = m and |B| = n

Every vertex in A has an edge to every
vertex in B
Any Graph with bi-degree vertex set
|A|+|B| is even

Let there be m 0-vertices with deg a
 M-m 0-vertices with deg b
 |A|-m 1-vertices with deg a
 M-(|A|-m) 1-vertices with deg b
 For purposes of generality, |A|<|B|
|A|+|B| is odd

Floater vertex placed in set B
Bi-degree vertex set plus one vertex