Premium
Disjoint circuits in the cartesian product of two directed cycles
Author(s) -
Curran Stephen
Publication year - 1994
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190180213
Subject(s) - cartesian product , mathematics , digraph , combinatorics , knot (papermaking) , disjoint sets , cayley graph , abelian group , discrete mathematics , graph , chemical engineering , engineering
We show that the Cartesian product of two directed cycles Z a X Z b has r disjointly embedded circuits C 1 , C 2 , ⃛, C r with specified knot classes knot (C i ) = (m i , n i ) , for i = 1, 2, ⃛, r , if and only if there exist relatively prime non‐negative integers m and n such that knot (C i ) = (m, n) , for i = 1, 2, ⃛, r , and r(am + bn) ≦ ab. We generalize this result to the Cayley digraph on a finite abelian group with a two‐element generating set.