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

• Autorzy: Jan Florek
• Języki publikacji: EN

Abstrakty

EN

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.

Kategorie tematyczne

• 05C05: Trees
• 05C15: Coloring of graphs and hypergraphs
• 05C70: Factorization, matching, partitioning, covering and packing
• 05C45: Eulerian and Hamiltonian graphs
• 05C10: Planar graphs; geometric and topological aspects of graph theory
• 05C75: Structural characterization of families of graphs
• 11D09: Quadratic and bilinear equations

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Colloquium Mathematicum
• Rocznik: 2015
• Tom: 138
• Numer: 1
• Strony: 23-42

Daty

wydano

2015

Twórcy

autor

Jan Florek

• Institute of Mathematics and Cybernetics, University of Economics, Komandorska 118/120, 53-345 Wrocław, Poland

Identyfikatory

DOI

10.4064/cm138-1-2