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

Tom 138 / 2015

Jan Florek Colloquium Mathematicum 138 (2015), 23-42 MSC: Primary 05C10, 05C70, 05C75, 05C05, 05C15, 05C45, 11D09. DOI: 10.4064/cm138-1-2


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


  • Jan FlorekInstitute of Mathematics and Cybernetics
    University of Economics
    Komandorska 118/120
    53-345 Wrocław, Poland

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek