Artykuły w formacie PDF dostępne są dla subskrybentów, którzy zapłacili za dostęp online, po podpisaniu licencji Licencja użytkownika instytucjonalnego. Czasopisma do 2009 są ogólnodostępne (bezpłatnie).

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

Tom 138 / 2015

Jan Florek Colloquium Mathematicum 138 (2015), 23-42 MSC: Primary 05C10, 05C70, 05C75, 05C05, 05C15, 05C45, 11D09. DOI: 10.4064/cm138-1-2

Streszczenie

Let $\mathcal {P}$ 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 \in \mathcal {P}$ has a decomposition 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 of the same length $M(q)$, and $K(q)-1$ induced cycles of the same length $2M(q)$. For $q \in 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 \in Q$. We present some applications of these equations. The set $\{(K(q), M(q), S^+(q)): q \in Q\}$ is called the orbit of $P$. If $P$ has a one-point orbit, then there is an orientation-preserving automorphism $\sigma $ such that $\sigma (P_i) = P_{i+1}$ for every $i \in Q$ (where $P_3 = P_0$). We characterize one-point orbits of graphs in $\mathcal {P}$. It is known that every graph in  $\mathcal {P}$ has an even order. We prove that if $P$ is of order $4n +2$, $n \in \mathbb {N}$, then it has two disjoint induced trees of the same order, which are equitable 2-colorable and together cover all vertices of $P$.

Autorzy

  • Jan FlorekInstitute of Mathematics and Cybernetics
    University of Economics
    Komandorska 118/120
    53-345 Wrocław, Poland
    e-mail

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek