All Tight Descriptions of 3-Stars in 3-Polytopes with Girth 5

• Autorzy: Oleg V. Borodin , Anna O. Ivanova
• Języki publikacji: EN

Abstrakty

EN

Lebesgue (1940) proved that every 3-polytope P5 of girth 5 has a path of three vertices of degree 3. Madaras (2004) refined this by showing that every P5 has a 3-vertex with two 3-neighbors and the third neighbor of degree at most 4. This description of 3-stars in P5s is tight in the sense that no its parameter can be strengthened due to the dodecahedron combined with the existence of a P5 in which every 3-vertex has a 4-neighbor. We give another tight description of 3-stars in P5s: there is a vertex of degree at most 4 having three 3-neighbors. Furthermore, we show that there are only these two tight descriptions of 3-stars in P5s. Also, we give a tight description of stars with at least three rays in P5s and pose a problem of describing all such descriptions. Finally, we prove a structural theorem about P5s that might be useful in further research.

Słowa kluczowe

EN

3-polytope; planar graph; structure properties; k-star

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 1
• Strony: 5-12

Daty

wydano

2017-02-01

otrzymano

2015-06-22

poprawiono

2016-01-16

zaakceptowano

2016-01-16

online

2017-01-13

Twórcy

autor

Oleg V. Borodin

• Institute of Mathematics Siberian Branch, Russian Academy of Sciences, Novosibirsk, 630090,

autor

Anna O. Ivanova

• Ammosov North-Eastern Federal University, Yakutsk, 677000,

Identyfikatory

DOI

10.7151/dmgt.1905