Equations relating factors in decompositions into factors of some family of plane triangulations, and applications (with an appendix by Andrzej Schinzel)

Jan Florek¹

¹ Institute of Mathematics and Cybernetics University of Economics Komandorska 118/120 53-345 Wrocław, Poland

Colloquium Mathematicum, Tome 138 (2015) no. 1, pp. 23-42.

Résumé

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$.

Détail

DOI : 10.4064/cm138-1-2

Keywords: mathcal family connected plane triangulations vertices degree three six nbaum motzkin proved dual terms every graph mathcal has decomposition factors indexed elements cyclic group every factor consists induced paths length induced cycles length define integer vector determines graph simple uniquely orientation preserving isomorphism establish arithmetic equations allow calculating present applications these equations set called orbit nbsp has one point orbit there orientation preserving automorphism sigma sigma every where characterize one point orbits graphs mathcal known every graph nbsp mathcal has even order prove order mathbb has disjoint induced trees order which equitable colorable together cover vertices