✦ LIBER ✦

Kronecker products of paths and cycles: Decomposition, factorization and bi-pancyclicity

✍ Scribed by Pranava K. Jha

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 690 KB
Volume: 182
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(97)00138-6

No coin nor oath required. For personal study only.

✦ Synopsis

Let G x H denote the Kronecker product of graphs G and H. Principal results are as follows: (a) If m is even and n-0 (mod 4), then one component of P,.+l x P,+1, and each component of each of CA x Pn+l, Pm+l x (7, and Cm x C, are edge decomposable into cycles of uniform length rs, where r and s are suitable divisors of m and n, respectively, (b) if m and n are both even, then each component of each of Cm X P,+I, P,.+l X C, and C,. × C. is edge-decomposable into cycles of uniform length ms, where s is a suitable divisor of n, (c) C2i+1 × C2j+l is factorizable into shortest odd cycles, (d) each component C4i x C4j is factorizable into four-cycles, and (e) each component of Cmx C4j admits of a bi-pancyclic ordering.

📜 SIMILAR VOLUMES

Optimal orientations of products of path

Optimal orientations of products of paths and cycles

✍ K.M. Koh; E.G. Tay 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 656 KB

For a graph G, let 9(G) be the family of strong orientations of G, d(G) = min{d(D) / D t 9' (G)} and p(G) = d(G) -d(G), where d(G) and d(D) are the diameters of G and D respectively. In this paper we show that p(G) = 0 if G is a Cartesian product of (I ) paths, and (2) paths and cycles, which satis

Decompositions of digraphs into paths an

Decompositions of digraphs into paths and cycles

✍ Malaz Maamoun 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 226 KB

On optimal orientations of Cartesian pro

On optimal orientations of Cartesian products of even cycles and paths

✍ Koh, K. M.; Tay, E. G. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB

For a graph G , let D ( G ) be the family of strong orientations of G , and define d ៝ ( G ) Å min{d(D)ÉD √ D(G)}, where d(D) is the diameter of the digraph D. In this paper, we evaluate the values of d ៝ (C 2n 1

Small Cycle Double Covers of Products II

Small Cycle Double Covers of Products II: Categorical and Strong Products with Paths and Cycles

✍ R. J. Nowakowski; K. Seyffarth 📂 Article 📅 2009 🏛 Springer Japan 🌐 English ⚖ 423 KB

A note on path and cycle decompositions

A note on path and cycle decompositions of graphs

✍ Dom Decaen 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB 👁 1 views

## Abstract In the study of decompositions of graphs into paths and cycles, the following questions have arisen: Is it true that every graph __G__ has a smallest path (resp. path‐cycle) decomposition __P__ such that every odd vertex of __G__ is the endpoint of exactly one path of __P__? This note g

Small cycle double covers of products I:

Small cycle double covers of products I: Lexicographic product with paths and cycles

✍ R. J. Nowakowski; K. Seyffarth 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 243 KB

## Abstract Bondy conjectured that every simple bridgeless graph has a small cycle double cover (SCDC). We show that this is the case for the lexicographic products of certain graphs and along the way for the Cartesian product as well. Specifically, if __G__ does not have an isolated vertex then __