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

Jan Florek. "Equations relating factors in decompositions into factors of some family of plane triangulations, and applications (with an appendix by Andrzej Schinzel)." Colloquium Mathematicae 138.1 (2015): 23-42. <http://eudml.org/doc/286555>.

@article{JanFlorek2015,
abstract = {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.},
author = {Jan Florek},
journal = {Colloquium Mathematicae},
keywords = {plane triangulation; decomposition into factors; billiards; induced tree; 2-equitable coloring; Hamilton cycle; Diophantine equation},
language = {eng},
number = {1},
pages = {23-42},
title = {Equations relating factors in decompositions into factors of some family of plane triangulations, and applications (with an appendix by Andrzej Schinzel)},
url = {http://eudml.org/doc/286555},
volume = {138},
year = {2015},
}

TY - JOUR
AU - Jan Florek
TI - Equations relating factors in decompositions into factors of some family of plane triangulations, and applications (with an appendix by Andrzej Schinzel)
JO - Colloquium Mathematicae
PY - 2015
VL - 138
IS - 1
SP - 23
EP - 42
AB - 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.
LA - eng
KW - plane triangulation; decomposition into factors; billiards; induced tree; 2-equitable coloring; Hamilton cycle; Diophantine equation
UR - http://eudml.org/doc/286555
ER -