الفهرس 
Chapter one: Some Basic concepts of graphOnly 14 pages are availabe for public view
 |  | from | 91 |  |  |
| | | from | 91 | | |
Abstract
Radio labeling is an extension of distance two labeling, which is used to assign
channels to the transmitters of radio network such that the network satisfies all the
interference constraints. This assignment of channels to the transmitters is popularly
known as channel assignment problem, which was introduced by Hale in 1980. For
the solution of channel assignment problem, the interference graph is developed and
assignment of channels converted into graph labeling (a graph labeling is an
assignment of label to each vertex according to certain rule). In interference graph,
the vertices are used to represent transmitters, and there is a major interference
between two transmitters if the corresponding pair of vertices are adjacent. While
there is minor interference between transmitters if corresponding vertices are at
distance two, and there is no interference between transmitters if they are at distance
three or beyond it. In other words, very close transmitters are represented by adjacent
vertices, and close transmitters are represented by the vertices which are at distance
two apart.
A radio labeling of a connected graph G is a map h from the vertices of G to
N such that |ℎ (𝑥) − ℎ (𝑦)| ≥ diam (𝐺) + 1 − d(𝑥, 𝑦) where diam(G) is the diameter of
graph and d(x, y) is the distance between two vertices. The radio number of h rn(h)
is the maximum number assigned to any vertex of G. The radio number of G,
rn(G),is the minimum value of rn(h) taken over all radio labelings h of G.
A radio mean labeling of connected graph G=(V,E) is one to one function h
from the set of vertices V, to the set of natural numbers 𝑁 such that for each distinct
vertices x and y of G, ⌈
ℎ(𝑥)+ℎ(𝑦)
2
⌉ ≥ 𝑑𝑖𝑎𝑚(𝐺) + 1 − 𝑑(𝑥, 𝑦)where d(x,y)is the
distance between two vertices x&y and the diam(G) is the diameter of G . The radio
mean number of ℎ denoted 𝑟𝑚n(ℎ), is the maximum number assigned to vertices of
III
G. The radio mean number of G, 𝑟𝑚n(𝐺) is the minimum value of 𝑟𝑚𝑛(ℎ) taken
over all possible radio mean labeling h of G.
In this thesis, the radio number of triangular snake graph, double triangular snake,
graph, Δ(𝟏,𝒌) , Δ(𝟐,𝒌) and Home graph are introduced, On the other hand, the radio
mean number of triangular snake graph, subdivision of triangular snake graph, Δ(𝟏,𝒌)
and Home graph also introduced.
The thesis consists of five chapters:
Chapter 1: Some basic concepts of graph theory.
In this chapter, we introduce some basic definitions of graph theory.
Chapter 2: Related Work.
In this chapter, we introduced some related work.
Chapter 3: The Radio number of graphs.
We presented the main results of the upper bound of radio number of
triangular and double triangular snake graphs with giving some examples and the
algorithms that used to get the results of the radio number of the given graphs. We
obtained that the upper bound of triangular snake of even blocks is 𝑘2 +
𝑘
2
and for
odd blocks is 𝑘2 + 𝑘 −
𝑘
2
. The upper bound of double triangular snake graph is 3
𝑖𝑓 𝑘 =1, 7 𝑖𝑓 𝑘 =2, 2𝑘2 − 𝑘 +3 𝑖𝑓 𝑘 𝑖𝑠 𝑜𝑑𝑑, 2𝑘2 − 𝑘 + 2 𝑖𝑓 𝑘 𝑖𝑠 𝑒𝑣𝑒𝑛. In addition,
we presented the main results of the upper bound of radio number of Δ (1, 𝑘) and Δ (2,
𝑘) graphs with giving some examples. We obtained that the upper bound of Δ (1, 𝑘) is
given by 6 𝑘 =1, 2𝑘2 + 2𝑘 + 3 𝑖𝑓 𝑘 𝑖𝑠 𝑜𝑑𝑑, 2𝑘2 + 2𝑘 + 4 𝑖𝑓 𝑘 𝑖𝑠 𝑒𝑣𝑒𝑛. The upper
bound of radio number of Δ (2, 𝑘) is 2𝑘2 + 9𝑘 + 14 if 𝑘 𝑖𝑠 𝑒𝑣𝑒𝑛, 2𝑘2 + 9𝑘 + 13 if k is
𝑜𝑑𝑑. The upper bound of radio number of home graph is 2𝑘2 + 4𝑘 +
1 𝑖𝑓 𝑘 𝑖𝑠 𝑒𝑣𝑒𝑛,
3
2
𝑘2 +
13
2
𝑘 − 1 𝑖𝑓 𝑘 𝑖𝑠 𝑜𝑑𝑑.Chapter 4: The Radio mean number of graphs.
We presented the main results of the upper bound of radio mean number of
triangular and subdivision of triangular snake graph with giving some examples.
We obtained that the upper bound of radio mean number of triangular snake given
by 3 if 𝑘 =1 , 3𝑘 − 2 𝑖𝑓 𝑘 𝑖𝑠 𝑜𝑑𝑑, 3𝑘 − 1 𝑖𝑓 𝑘 𝑖𝑠 𝑒𝑣𝑒𝑛. The upper bound of radio
mean number of subdivision of triangular snake is 7𝑘 + 1 𝑖𝑓 𝑘 𝑖𝑠 𝑜𝑑𝑑 and 7𝑘 + 2 𝑖𝑓
𝑘 𝑖𝑠 𝑒𝑣𝑒𝑛. We also presented the main results of the upper bound of radio mean
number of subdivisions of double triangular snake graph and Δ (1, 𝑘) with giving some
examples. We obtained that the upper bound of radio mean number of subdivisions
of double triangular snake graph is given by 10𝑘+1 𝑖𝑓 𝑘 𝑖𝑠 𝑜𝑑𝑑, 10𝑘 + 2 𝑖𝑓 𝑘 𝑖𝑠
𝑒𝑣𝑒𝑛.The upper bound of radio mean number of subdivision of triangular snake is
4𝑘 + 1𝑓𝑜𝑟 𝑘 ≥ 2. The upper bound of radio mean number of home graph is 4𝑘 +
2 𝑘 ≥ 2.
Chapter 5: Conclusion and future works.
In this chapter, the conclusion and future works are proposed.