Orbits and Hamilton bonds in a family of plane triangulations with vertices of degree three or six

MaRDI QIDQ6233904zbMATH OpenFDO

Authors Jan Florek

Publication date 23 June 2012

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)

Abstract: Let $calP$ be the family of all 2-connected plane triangulations with vertices of degree three or six. Gr"{u}nbaum and Motzkin proved (in the dual terms) that every graph $PincalP$ is factorable 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 with the same length $M(q)$, and $K(q)-1$ induced cycles with the same length $2M(q)$. For $qinQ$, 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 calculate the vector $(K(q+1),M(q+1),S^{+}(q+1))$ by the vector $(K(q),M(q),S^{+}(q))$, $qinQ$. We present some applications of the equations. The set $(K(q),M(q),S^{+}(q)):qinQ$ is called the orbit of $P$. We characterize one point orbits of graphs in $calP$. We prove that if $P$ is of order $4n+2$, $ninmathbbN$, than it has a Hamilton bond such that the end-trees of the bond are equitable 2-colorable and have the same order. We prove that if $M(q)$ is odd and $K(q)geqslantfracM(q)3$, then there are two disjoint induced paths of the same order, which vertices together span all of $P$.

This page was built for publication: Orbits and Hamilton bonds in a family of plane triangulations with vertices of degree three or six

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6233904)