3-Vertices with fewest 2-neighbors in plane graphs with no long paths of 2-vertices Full article
| Journal |
Discrete Mathematics
ISSN: 0012-365X , E-ISSN: 1872-681X |
||||
|---|---|---|---|---|---|
| Output data | Year: 2022, Volume: 345, Number: 8, Article number : 112904, Pages count : 5 DOI: 10.1016/j.disc.2022.112904 | ||||
| Tags | 3-Path; Girth; Minimum degree; Plane graph; Structure properties; Tight description | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (2)
| 1 | Министерство науки и высшего образования РФ | FSRG-2020-0006 |
| 2 |
Министерство науки и высшего образования РФ Mathematical Center in Akademgorodok |
075-15-2019-1613, 075-15-2022-281 |
Abstract:
Let g(k,t) be the minimum integer such that every plane graph with girth g at least g(k,t), minimum degree δ=2 and no (k+1)-paths consisting of vertices of degree 2, where k≥1, has a 3-vertex with at least t neighbors of degree 2, where 1≤t≤3. In 2015, Jendrol' and Maceková proved g(1,1)≤7. Later on, Hudák et al. established g(1,3)=10, Jendrol', Maceková, Montassier, and Soták proved g(1,1)≥7, g(1,2)=8 and g(2,2)≥11, and we recently proved that g(2,2)=11 and g(2,3)=14. Thus g(k,t) is already known for k=1 and all t. In this paper, we prove that g(k,1)=3k+4, g(k,2)=3k+5, and g(k,3)=3k+8 whenever k≥2.
Cite:
Borodin O.V.
, Ivanova A.O.
3-Vertices with fewest 2-neighbors in plane graphs with no long paths of 2-vertices
Discrete Mathematics. 2022. V.345. N8. 112904 :1-5. DOI: 10.1016/j.disc.2022.112904 WOS Scopus РИНЦ OpenAlex
3-Vertices with fewest 2-neighbors in plane graphs with no long paths of 2-vertices
Discrete Mathematics. 2022. V.345. N8. 112904 :1-5. DOI: 10.1016/j.disc.2022.112904 WOS Scopus РИНЦ OpenAlex
Dates:
| Submitted: | Sep 30, 2020 |
| Accepted: | Mar 18, 2022 |
| Published online: | Mar 30, 2022 |
Identifiers:
| Web of science: | WOS:000792690200009 |
| Scopus: | 2-s2.0-85127331871 |
| Elibrary: | 48423435 |
| OpenAlex: | W4220943406 |