Equations relating factors in decompositions into factors of some family of plane triangulations, and applications (with an appendix by Andrzej Schinzel)
Volume 138 / 2015
Abstract
Let $\mathcal {P}$ be the family of all $2$-connected plane triangulations with vertices of degree three or six. Grünbaum and Motzkin proved (in dual terms) that every graph $P \in \mathcal {P}$ has a decomposition into factors $P_0$, $P_1$, $P_2$ (indexed by elements of the cyclic group $Q = \{0,1,2\}$) such that every factor $P_q$ consists of two induced paths of the same length $M(q)$, and $K(q)-1$ induced cycles of the same length $2M(q)$. For $q \in Q$, we define an integer $S^+(q)$ such that the vector $(K(q), M(q), S^+(q))$ determines the graph $P$ (if $P$ is simple) uniquely up to orientation-preserving isomorphism. We establish arithmetic equations that will allow calculating $(K(q+1), M(q+1), S^+(q+1))$ from $(K(q), M(q), S^+(q))$, $q \in Q$. We present some applications of these equations. The set $\{(K(q), M(q), S^+(q)): q \in Q\}$ is called the orbit of $P$. If $P$ has a one-point orbit, then there is an orientation-preserving automorphism $\sigma $ such that $\sigma (P_i) = P_{i+1}$ for every $i \in Q$ (where $P_3 = P_0$). We characterize one-point orbits of graphs in $\mathcal {P}$. It is known that every graph in $\mathcal {P}$ has an even order. We prove that if $P$ is of order $4n +2$, $n \in \mathbb {N}$, then it has two disjoint induced trees of the same order, which are equitable 2-colorable and together cover all vertices of $P$.
