Chapter 1 Preliminaries

Chapter 1
Preliminaries
This chapter includes certain denitions and known results
needed for the subsequent development of the study. For a nonempty set X , the set of all subsets of X is denoted by 2X . By Ac, we
mean, the complement of a set A. The vertex set and edge set of
the graph G under consideration are always denoted by V and E
respectively. G0 G means G0 is a subgraph of G while G0 G
indicates G0 is a proper subgraph of G. Similar states with respect
to supergraphs are denoted by and respectively. Throughout
this thesis, l, m and n stand for natural numbers without restrictions unless and otherwise mentioned. The empty graph of order
n is denoted by Nn . G[v ; : : : ; vn ] stands for the subgraph of G
induced by the vertices v ; : : : ; vn. The order and size of a graph
G is denoted by o(G) and s(G) respectively. When we say G is
a (p; q)-graph it means that p = o(G) and q = s(G). When two
graphs are non-isomorphic they are said to be dierent. The basic notations and denitions in Graph Theory and Topology are
1
1
11
1 Preliminaries
12
assumed to be familiar to the reader.
[3]Let G = (V; E ) be a graph and X be a
nonempty set. Then a mapping f : V ! 2X or f : E ! 2X or f :
(V [ E ) ! 2X is called a set-assignment or set-valuation of the
vertices or edges or both.
Definition 1.0.1.
Theorem 1.0.2.
[3] Every graph has a set-valuation.
[3] Let G = (V; E ) be a given graph and X be
a nonempty set. Then a set-valuation f : V [ E ! 2X is said to
be a set-indexer of G if
Definition 1.0.3.
1. f (u; v) = f (u) f (v), 8(u; v) 2 E , where `' denotes the
binary operation of taking the symmetric dierence of the
sets in 2X
2. the restriction maps f jV and f jE are both injective.
In this case, X is called an indexing set of G. Clearly, a graph
can have many indexing sets and the minimum of the cardinalities
of the indexing sets is said to be the set-indexing number of G,
denoted by (G). The set-indexing number of trivial graph K is
dened to be zero.
1
Theorem 1.0.4.
[3] Every graph has a set-indexer.
Theorem 1.0.5.
[3] If X is an indexing set of G = (V; E ).
Then
(i). jE j 2jX j 1 and
(ii). dlog2 (jE j + 1)e (G) jV j 1, where d e is the ceiling
function.
1 Preliminaries
13
[3] If G0 is a subgraph of G, then (G0) Theorem 1.0.6.
(G ).
Theorem 1.0.7.
Theorem 1.0.8.
[3] If G = G0, then (G) = (G0).
8
<
[3] (Kn) = : n 1 if 1 n 5
n 2 if 6 n 7
6
!7
6
X n 1 7
7
6
5; n 4
)
[3] (Kn) 4log (1 +
j
3
Theorem 1.0.9.
2
j =0
and b c is the oor function.
Theorem 1.0.10.
[4] The set-indexing number of the Heawood
Theorem 1.0.11.
[4] The set-indexing number of the Petersen
Theorem 1.0.12.
[3] Let G be any graph and X (G) denote
Graph is 5.
graph is 5.
the set of all optimal set-indexers f of G with respect to a set
X such that f (u) = ; for some u 2 V (G). Then X (G) is
nonempty.
Theorem 1.0.13.
jV j 5.
[3] If G be a graph with (G) = jV j 1, then
[3] A graph G is set-graceful if (G) = log (jE j+
1) and the corresponding set-indexer is called set-graceful labeling
and it is an optimal set-indexer of G.
Theorem 1.0.15. [33] K ; is not set-graceful.
Theorem 1.0.16. [3] The star K ;
is set-graceful.
Theorem 1.0.17. [31] The complete graph Kn is set-graceful
if and only if n 2 f2; 3; 6g.
Definition 1.0.14.
2
35
1 2n
1
1 Preliminaries
14
Theorem 1.0.18.
[33] If a (p; q){graph G is set-graceful, then
q = 2m 1 for some positive integer m.
[15] An embedding of a graph H in a graph
G is an isomorphism between H and a subgraph of G.
Definition 1.0.19.
[24] A set-indexer f of G with indexing set
X is said to be topogenic if the family f (V ) [ f (E ) is a topology
on X where f (V ) = ff (v); v 2 V g and f (E ) = ff (u) f (v);
(u; v) 2 E g.
Definition 1.0.20.
[21] A graph G is said to be k-partite if its
vertex set V can be partitioned in to k nonempty sets V ; : : : ; Vk
such that every edge in G joins vertices from dierent subsets.
Thus k = 2 gives us the bipartite graphs. The k-partite graph G
is said to the complete k-partite graph if, for each i 6= j , every
vertex of the subsets Vi is adjacent to every vertex of the subset
Vj .
Definition 1.0.21.
1
[18] The join G _ H of two vertex disjoint
graphs G and H has V (G _ H ) = V (G) [ V (H ) and E (G _ H ) =
E (G) [ E (H ) [ f(u; v): u 2 V (G), v 2 V (H )g.
Definition 1.0.22.
[37] The join K _ Pn of K and Pn is called
a fan and is denoted by Fn .
Definition 1.0.23.
1
1
+1
[30] The wheel graph with n spokes, Wn, is
the graph that consists of an n-cycle and one additional vertex,
say u, that is adjacent to all the vertices of the cycle.
Definition 1.0.24.
[37] The helm Hn is the graph obtained from
the wheel Wn = Cn _ K by attaching a pendant edge at each
vertex of Cn.
Definition 1.0.25.
1
1 Preliminaries
15
[9] An n-sun is a graph that consists of a cycle
Cn and an edge terminating in a vertex of degree one attached to
each vertex of Cn.
Definition 1.0.26.
[46] The double star graph ST (m; n) is the
graph formed by two stars K ;m and K ;n by joining their centers
by an edge.
Definition 1.0.27.
1
Definition 1.0.28.
joining Pn and K .
1
[23] The double fan graph is obtained by
2
[33] For a graph G, the splitting graph S 0(G)
is obtained from G by adding for each vertex v of G, a new vertex
say v0 so that v0 is adjacent to every vertex that is adjacent to v.
Definition 1.0.29.
[18] The line graph L(G) of a nonempty graph
G is that graph whose vertex set is E (G) and two vertices e and
f of L(G) are adjacent if and only if e and f are adjacent edges
in G.
Definition 1.0.30.
[33] The twing is a graph obtained from a
path by attaching exactly two pendant edges to each internal vertex of the path.
Definition 1.0.31.
Definition 1.0.32.
Nm .
[5] The triangular book is the graph K _
2
[23] The Gear graph is obtained from the
wheel by adding a vertex between every pair of adjacent vertices
of the cycle.
Definition 1.0.33.
[11] A spider graph is a tree with at most one
branch point (that is, at most one vertex v such that d(v) 3).
Definition 1.0.34.
1 Preliminaries
16
[23] Caterpillar is a tree with the property
that the removal of its pendant vertices leaves a path.
Definition 1.0.35.
[12] For n 3, there is no topology on n
points having k open sets, where 3 2n < k < 2n .
Theorem 1.0.36.
2
For an integer k 2, let t(k) denote the smallest positive integer such that there exists a topology on t(k) points
having k open sets.
Notation 1.0.37.
Theorem 1.0.38.
[34] For all k 2, t(k) blog kc + 2.
Theorem 1.0.39.
[34] t(4) = 2, t(5) = 3, t(7) = 4 = t(9) and
t(11) = 5.
4
3
2
[34] For 8 n 15, 3 t(n) 5 and for
16 n 31, 4 t(n) 7.
Theorem 1.0.40.
For every n 1, let T (n; k) denote the number
of topologies on n points having k open sets.
Notation 1.0.41.
[12] For every n 3, T (n; n + 4) =
n! and T (4; 7) = 54.
Theorem 1.0.42.
(n
3)(n2 +15n+20)
48
Theorem 1.0.43.
1.
[34] T (4; 11) = 0, T (5; 22) = 0 and T (5; 11)
[39] A topological space (X; ) is said to be
nite if the set X is nite.
Definition 1.0.44.
[22] An Alexandro space is a set X together
with a system F of subsets satisfying the following axioms
Definition 1.0.45.
(i) the intersection of a countable number of sets from F is a
set in F.
1 Preliminaries
17
(ii) The union of a nite number of sets from F is a set in F.
(iii) ; and X are in F.
[22] A topological space (X; ) is called a
door space if and only if each subset of X is either open or closed.
Definition 1.0.46.
[20]A topological space is called a quasidiscrete if every open set is closed and vice versa.
Definition 1.0.47.
[21] For any graph G a complete subgraph
of G is called a clique of G. The number of vertices in a largest
clique of G is called the clique number of G and denoted by cl(G).
Definition 1.0.48.

Download Report