✦ LIBER ✦

On the Decomposition of Cayley Color Graphs into Isomorphic Oriented Trees

✍ Scribed by J.F. Fink

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 579 KB
Volume: 61
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1994.1031

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that if (\Delta) is a minimal generating set for a nontrivial group (\Gamma) and (T) is an oriented tree having (|\Delta|) edges, then the Cayley color graph (D_{\Delta}(\Gamma)) can be decomposed into (|\Gamma|) edge-disjoint subgraphs, each of which is isomorphic to (T); we say that (D_{\Delta}(\Gamma)) is (T)-decomposable. This result is extended to obtain a result concerning (H)-decompositions of Cayley graphs for weakly connected oriented graphs (H). The first result is then used to derive several theorems concerning decompositions of Cayley color graphs into prescribed families of oriented trees. Applications of some of these theorems to the verification of statements about decompositions of the (n)-dimensional hypercube (Q_{n}) are also discussed. O 1994 Academic Press, Inc.

📜 SIMILAR VOLUMES

On the decomposition of n-cubes into iso

On the decomposition of n-cubes into isomorphic trees

✍ John Frederick Fink 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 324 KB

## Abstract We prove that if T is any tree having __n__ edges (__n__ ≥ 1), then the __n__‐cube Q~n~ can be decomposed into 2^n‐1^ edge‐disjoint induced subgraphs, each of which is isomorphic to T. We use this statement to obtain two results concerning decompositions of Q~n~ into subgraphs isomorphi

Isomorphic factorization of the complete

Isomorphic factorization of the complete graph into Cayley digraphs

✍ G. L. Chia; Poh-Hwa Ong 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 151 KB

## Abstract Let __Z__~__p__~ denote the cyclic group of order __p__ where __p__ is a prime number. Let __X__ = __X__(__Z__~__p__~, __H__) denote the Cayley digraph of __Z__~__p__~ with respect to the symbol __H__. We obtain a necessary and sufficient condition on __H__ so that the complete graph on

On the Isomorphisms of Cayley Graphs of

On the Isomorphisms of Cayley Graphs of Abelian Groups

✍ Yan-Quan Feng; Yan-Pei Liu; Ming-Yao Xu 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 190 KB

Let G be a finite group, S a subset of G=f1g; and let Cay ðG; SÞ denote the Cayley digraph of G with respect to S: If, for any subset T of G=f1g; CayðG; SÞ ffi CayðG; T Þ implies that S a ¼ T for some a 2 AutðGÞ; then S is called a CI-subset. The group G is called a CIM-group if for any minimal gene

On the Isomorphism Problem for Finite Ca

On the Isomorphism Problem for Finite Cayley Graphs of Bounded Valency

✍ C.H. Li; C.E. Praeger 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 187 KB

For a subset S of a group G such that 1 / ∈ S and S = S -1 , the associated Cayley graph Cay(G, S) is the graph with vertex set G such that {x, y} is an edge if and only if yx -1 ∈ S. Each σ ∈ Aut(G) induces an isomorphism from Cay(G, S) to the Cayley graph Cay(G, S σ ). For a positive integer m, th

Remarks on the placeability of isomorphi

Remarks on the placeability of isomorphic trees in a complete graph

✍ Hasunuma, Toru; Shibata, Yukio 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 99 KB 👁 3 views

Let Tp be any tree of order p and A ( T p ) stand for the maximum degree of the vertices of Tp. We prove the following theorem. "If A(Tp) 5 pi, where p > 2i, then Tp is i-placeable in Kp" is true if and only if i = 1, 2, and 3. 0 1996 John Wiley & Sons, Inc. Suppose G is a graph and V ( G ) , E ( G

On the decomposition of kn into complete

On the decomposition of kn into complete bipartite graphs

✍ H. Tverberg 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 76 KB 👁 1 views

## Abstract A short proof is given of the impossibility of decomposing the complete graph on __n__ vertices into __n__‐2 or fewer complete bipartite graphs.