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

Jan Florek

Colloquium Mathematicae, Tome 139 (2015), p. 23-42 / Harvested from The Polish Digital Mathematics Library

Résumé

Let 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 ∈ has a decomposition into factors P₀, P₁, P₂ (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 ∈ 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 ∈ Q. We present some applications of these equations. The set (K(q),M(q),S⁺(q)): q ∈ Q is called the orbit of P. If P has a one-point orbit, then there is an orientation-preserving automorphism σ such that $σ(P_{i}) = P_{i+1}$ for every i ∈ Q (where P₃ = P₀). We characterize one-point orbits of graphs in . It is known that every graph in has an even order. We prove that if P is of order 4n + 2, 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

Publié le : 2015-01-01

Zbl 1308.05037

EUDML-ID : urn:eudml:doc:286555