الفهرس | Only 14 pages are availabe for public view |
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. |