3-vertices with fewest 2-neighbors in plane graphs with no long paths of 2-vertices (Q2142641)

From MaRDI portal
scientific article
Language Label Description Also known as
English
3-vertices with fewest 2-neighbors in plane graphs with no long paths of 2-vertices
scientific article

    Statements

    3-vertices with fewest 2-neighbors in plane graphs with no long paths of 2-vertices (English)
    0 references
    0 references
    0 references
    27 May 2022
    0 references
    For a plane graph, the degree of a vertex is the number of edges incident with it and a \(p\)-vertex is a vertex having degree equal to \(p\). Let \(g(k,t)\) be the minimum integer such that every plane graph with girth at least \(g(k,t)\), minimum degree \(\delta\) = 2 and no (\(k\)+1)-paths consisting of vertices of degree 2, where \(k\geq\) 1, has a 3-vertex with at least \(t\) neighbors of degree 2, where 1\( \leq t \leq\) 3. In this paper, the authors prove that \(g(k, 1) =3k + 4\), \(g(k, 2) = 3k + 5\), and \(g(k, 3) = 3k + 8\) whenever \(k \geq 2\).
    0 references
    0 references
    0 references
    0 references
    0 references
    plane graph
    0 references
    structure properties
    0 references
    girth
    0 references
    minimum degree
    0 references
    tight description
    0 references
    3-path
    0 references
    0 references
    0 references