الفهرس 
1.1 Survey about Orthogonal Double CoversOnly 14 pages are availabe for public view
 |  | from | 107 |  |  |
| | | from | 107 | | |
Abstract
Combinatorial design theory is the study of arranging elements of a finite set into patterns (subsets, blocks) according to specified rule. These designs are close to a wide range of applications in areas such as statistics, design of the physical experiments, cryptography and information theory. A large number of combinatorial design problems can be described in terms of edge decomposition of graphs. Graph decompositions have been studied since the 19th century. Their investigation is originated by various combinatorial problems, the best known among them are Kirkman’s problems of 15 strolling schoolgirls and Euler’s problems of 36 army officers. Many combinatorial and algebraic structures are linked to these objects. For an overview of the subject, the reader may refer to the book of Bosák [14]. The vast results in this area are summarized in the CRC Handbook of Combinatorial Designs [4]. Throughout the thesis we study a special class of graph decompositions, called Orthogonal Double Cover (ODC). An orthogonal double cover (ODC) of a graph H ( graph of degree ) is a collection of spanning sub-graphs (pages) of H such that they cover every edge of H twice and the intersection of any two of them contains exactly one edge. If all the pages are isomorphic to some graph , we speak of an ODC of H by . An ODC of H is cyclic (CODC) if the cyclic group of order is a subgroup of the automorphism group of the collection forming Cyclic orthogonal double cover. The main aim of this thesis is to study, investigate, construct and prove the existence of ODCs of H by for infinite classes of where H is the cayley graph. The thesis is organized as follows: In chapter one, the review of literature, the basic definitions and notations are presented, and the background information about orthogonality are introduced.
In chapter two, the construction of orthogonal double covers of complete bipartite graph is considered. Throughout this chapter we use the symmetric starter tools to construct these covers. Using these tools, we construct the ODCs of by for certain infinite classes of graphs such as ODCs of by a complete bipartite graph, ODCs of by a special class of disjoint union of path and a complete bipartite graph. Also, we construct ODCs of by a disjoint union of complete bipartite graphs. Furthermore, we present the recursive construction of ODC of the complete bipartite graph.
In chapter three, we investigate the orthogonal double covers (ODCs) of Cayley graphs as a generalization of the complete graphs, construct ODCs of Cayley graphs by for certain infinite classes of graphs such as ODCs of cayley graph by a complete bipartite graph, a complete tripartite graph, caterpillar, and a connected union of a cycle and a star whose center vertex belongs to that cycle. Moreover, we prove the existence of cyclic orthogonal double covers (CODCs) of circulant graphs for many classes of . In addition, we introduce a new a approach that use CODCs of circulant graphs of lower degrees to construct CODCs of circulant graphs of higher degrees.
Finally, the three chapters are followed by a general conclusion extracted from the thesis.