Premium
Retracts of box products with odd‐angulated factors
Author(s) -
Che Zhongyuan,
Collins Karen L.
Publication year - 2007
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.20191
Subject(s) - retract , combinatorics , mathematics , cartesian product , graph , connectivity , girth (graph theory) , path (computing) , product (mathematics) , discrete mathematics , geometry , computer science , pure mathematics , programming language
Let G be a connected graph with odd girth 2κ+1. Then G is a (2κ+1)‐angulated graph if every two vertices of G are connected by a path such that each edge of the path is in some (2κ+1)‐cycle. We prove that if G is (2κ+1)‐angulated, and H is connected with odd girth at least 2κ+3, then any retract of the box (or Cartesian) product G □ H is S □ T where S is a retract of G and T is a connected subgraph of H . A graph G is strongly (2κ+1)‐angulated if any two vertices of G are connected by a sequence of (2κ+1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2κ+1)‐angulated, and H is connected with odd girth at least 2κ+1, then any retract of G □ H is S □ T where S is a retract of G and T is a connected subgraph of H or | V ( S )|=1 and T is a retract of H . These two results improve theorems on weakly and strongly triangulated graphs by Nowakowski and Rival [Disc Math 70 (1988), 169–184]. As a corollary, we get that the core of the box product of two strongly (2κ+1)‐angulated cores must be either one of the factors or the box product itself. Furthermore, if G is a strongly (2κ+1)‐angulated core, then either G n is a core for all positive integers n , or the core of G n is G for all positive integers n . In the latter case, G is homomorphically equivalent to a normal Cayley graph [Larose, Laviolette, Tardiff, European J Combin 19 (1998), 867–881]. In particular, let G be a strongly (2κ+1)‐angulated core such that either G is not vertex‐transitive, or G is vertex‐transitive and any two maximum independent sets have non‐empty intersection. Then G n is a core for any positive integer n . On the other hand, let G i be a (2κ i +1)‐angulated core for 1 ≤ i ≤ n where κ 1 < κ 2 < … < κ n . If G i has a vertex that is fixed under any automorphism for 1 ≤ i ≤ n ‐1, or G i is vertex‐transitive such that any two maximum independent sets have non‐empty intersection for 1 ≤ i ≤ n ‐1, then □ i =1 n G i is a core. We then apply the results to construct cores that are box products with Mycielski construction factors or with odd graph factors. We also show that K ( r ,2 r +1) □ C 2 l +1 is a core for any integers l ≥ r ≥ 2. It is open whether K ( r ,2 r +1) □ C 2 l +1 is a core for r > l ≥ 2. © 2006 Wiley Periodicals, Inc. J Graph Theory