Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
3-vertices with fewest 2-neighbors in plane graphs with no long paths of 2-vertices - MaRDI portal

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
    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

    Identifiers