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

@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 -