Odd‐angulated graphs and cancelling factors in box products |
| |
Authors: | Zhongyuan Che Karen L. Collins Claude Tardif |
| |
Affiliation: | 1. Department of Mathematics Penn State University Beaver Campus, Monaca, Pennsylvania 15061‐2799;2. Department of Mathematics and Computer Science, Wesleyan University, Middletown, Connecticut 06459‐0128;3. Department of Mathematics and Computer Science, Royal Military College of Canada, P. O. Box 17000, Station “FORCES” Kingston, Ontario, Canada K7K 7B4 |
| |
Abstract: | Under what conditions is it true that if there is a graph homomorphism G □ H → G □ T, then there is a graph homomorphism H→ T? Let G be a connected graph of odd girth 2k + 1. We say that G is (2k + 1)‐angulated if every two vertices of G are joined by a path each of whose edges lies on some (2k + 1)‐cycle. We call G strongly (2k + 1)‐angulated if every two vertices are connected by a sequence of (2k + 1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2k + 1)‐angulated, H is any graph, S, T are graphs with odd girth at least 2k + 1, and ?: G□ H→S□T is a graph homomorphism, then either ? maps G□{h} to S□{th} for all h∈V(H) where th∈V(T) depends on h; or ? maps G□{h} to {sh}□ T for all h∈V(H) where sh∈V(S) depends on h. This theorem allows us to prove several sufficient conditions for a cancelation law of a graph homomorphism between two box products with a common factor. We conclude the article with some open questions. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:221‐238, 2008 |
| |
Keywords: | box product Cartesian product Cayley graph circulant core, graph homomorphism hom‐idempotent odd‐angulated graph retract strongly odd‐angulated graph |
|
|