الفهرس 
Applications of ODCsOnly 14 pages are availabe for public view
 |  | from | 111 |  |  |
| | | from | 111 | | |
Abstract
Graph theory plays an important role in contemporary life in an indirect way, such
as telecommunication network technologies, airlines, electronic and electrical circuits,
molecular bonds, and analysis of the huge social networks that currently exist on
the internet. For example, the map is a virtual graph, each vertex is an individual
city, and each edge means that there is a hyperlink between two cities. In general,
a graph consists of vertices (called points or nodes) that are connected by edges
(called lines or links). Graph theory is an essential part of discrete mathematics.
Graph theory is used to model mathematical structures to analyze multiple problems
found in abundance in our daily lives successfully. Mathematical structures show
relations between objects in a simple and fast way for many real-world problems and
provide successful problem analysis. The decomposition of the graph into subgraphs
is used to solve many problems in many applications such as improving the use of
databases. Since the data that comes from a relational database can be converted
into a complicated graph and the decomposition of the complicated graph into small
graphs managing to get the data or the information concerned with an object in a
fast way and without e§ort. The Orthogonal Double Covers (ODCs) is a branch of
graph theory and is considered a special class of graph decompositions.
An ODCs of any graph K by T ; is a collection G =f ( ) : 2 v(K)g of isomorphic subgraphs ( ) of K (called pages), with applying two conditions (i) every edge
of K exists exactly two times in G and (ii) if the two vertices a and b are adjacent in
2
K, then (a) and (b) share one edge.
In Chapter 1, we present the introduction containing the review of literature, some
basic deÖnitions, notations, and some applications in scheduling based on the properties of ODCs and the graph decompositions. In Chapter 2, we construct the ODCs
of the complete bipartite graphs Kn;n by graph-caterpillars (symmetric graphs, disjoint symmetric graphs, and copies of disjoint symmetric graphs), complete bipartite
graph, and copies of complete bipartite graph using symmetric starter vectors. Also,
we extend the complete bipartite graphs based on the Cartesian product, and we
introduce a general description of the symmetric starter graphs using the edge set. In
Chapter 3, we construct cyclic ODCs by joint and disjoint unions of new generally
described graphs. Finally, we prove the existence of orthogonal labeling for some
di§erent inÖnite graph classes and hence, the existence of the cyclic ODCs of some
di§erent inÖnite circulant graphs.