Реферат: A k-star Sk(v) in a plane graph G consists of a central vertex v and k its neighbor vertices. The height h(Sk(v)) and weight w(Sk(v)) of Sk(v) is the maximum degree and degree-sum of its vertices, respectively. The height hk(G) and weight wk(G) of G is the maximum height and weight of its k-stars. Lebesgue (1940) proved that every 3-polytope of girth g at least 5 has a 2-star (a path of three vertices) with h2 = 3 and w2 = 9. Madaras (2004) refined this by showing that there is a 3-star with h3 = 4 and w3 = 13, which is tight. In 2015, we gave another tight description of 3-stars for girth g = 5 in terms of degree of their vertices and showed that there are only these two tight descriptions of 3-stars. In 2013, we gave a tight description of 3-stars in arbitrary plane graphs with minimum degree δ at least 3 and g ≥ 3, which extends or strengthens several previously known results by Balogh, Jendrol', Harant, Kochol, Madaras, Van den Heuvel, Yu and others and disproves a conjecture by Harant and Jendrol' posed in 2007. There exist many tight results on the height, weight and structure of 2-stars when δ = 2. In 2016, Hudák, Maceková, Madaras, and Široczki considered the class of plane graphs with δ = 2 in which no two vertices of degree 2 are adjacent. They proved that h3 = w3 = ∞ if g ≤ 6, h3 = 5 if g = 7, h3 = 3 if g ≥ 8, w3 = 10 if g = 8 and w3 = 3 if g ≥ 9. For g = 7, Hudák et al. proved 11 ≤ w3 ≤ 20. The purpose of our paper is to prove that every plane graph with δ = 2, g = 7 and no adjacent vertices of degree 2 has w3 = 12. © 2018 Borodin O.V., Ivanova A.O.

Библиографическая ссылка: Borodin O.V. , Ivanova A.O.
Light 3-stars in sparse plane graphs
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2018. V.15. P.1344-1352. DOI: 10.17377/semi.2018.15.110 WOS Scopus

Идентификаторы БД:

Web of science:	WOS:000454860200052
Scopus:	2-s2.0-85060977282

Цитирование в БД:

БД	Цитирований
Scopus	2
Web of science	2

Альметрики: