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

arXiv1206.5383MaRDI QIDQ6233904FDOQ6233904

Authors: Jan Florek 

Publication date: 23 June 2012

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

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)

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)