![]() | Only 14 pages are availabe for public view |
Abstract The major aim of the thesis is handelling a special class of graph decompositions called orthogonal double covers (ODCs) of complete bipartite graphs and of circulant graphs. For a survey on the topic, the reader should read the book of Bosák [1]. Several results for graph decompositions are found in [2]. There is a strong relation betweeen the graph decompositions and the combinatorial and algebraic structures. The orthogonal double covers (ODCs) of any graph H containing n -vertices can be defined as follows. Let = {G0,G1,…,Gn-1 }be a collection of n- isomorphic spanning subgraphs of H is called an ODC of H if there exists a bijective mapping φ : V(H) → such that: (1) Every edge of H is contained in exactly two of the graphs G0,G1,…,Gn-1 , (2) For every choice of different vertices a,b of H, 1 if {,}(),|(())(())|0 otherwise. The results in the thesis can be summurized as follows. By using the symmetric starter tool, we construct the ODCs of Kn,n by infinite classes of disjoint unions of certain complete bipartite spanning subgraphs. Also we introduce a recursive method to construct the ODCs of Kn,n (cartesian products of symmetric vectors), and we construct the ODCs of circulant graphs by using infinite graph classes by using a recursive method (orthogonal labelling) |