On Longest Cycles in Essentially 4-Connected Planar Graphs
A planar 3-connected graph G is essentially 4-connected if, for any 3-separator S of G, one component of the graph obtained from G by removing S is a single vertex. Jackson and Wormald proved that an essentially 4-connected planar graph on n vertices contains a cycle C such that . For a cubic essent...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2016-08-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1875 |
| _version_ | 1797717989836980224 |
|---|---|
| author | Fabrici Igor Harant Jochen Jendroľ Stanislav |
| author_facet | Fabrici Igor Harant Jochen Jendroľ Stanislav |
| author_sort | Fabrici Igor |
| collection | DOAJ |
| description | A planar 3-connected graph G is essentially 4-connected if, for any 3-separator S of G, one component of the graph obtained from G by removing S is a single vertex. Jackson and Wormald proved that an essentially 4-connected planar graph on n vertices contains a cycle C such that . For a cubic essentially 4-connected planar graph G, Grünbaum with Malkevitch, and Zhang showed that G has a cycle on at least ¾ n vertices. In the present paper the result of Jackson and Wormald is improved. Moreover, new lower bounds on the length of a longest cycle of G are presented if G is an essentially 4-connected planar graph of maximum degree 4 or G is an essentially 4-connected maximal planar graph. |
| first_indexed | 2024-03-12T08:44:28Z |
| format | Article |
| id | doaj.art-00c53a1b75f6495ca1f93b22bcedef76 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T08:44:28Z |
| publishDate | 2016-08-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-00c53a1b75f6495ca1f93b22bcedef762023-09-02T16:29:58ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922016-08-0136356557510.7151/dmgt.1875dmgt.1875On Longest Cycles in Essentially 4-Connected Planar GraphsFabrici Igor0Harant Jochen1Jendroľ Stanislav2Institute of Mathematics P.J. Šafárik University in Košice, SlovakiaInstitute of Mathematics Ilmenau University of Technology, GermanyInstitute of Mathematics P.J. Šafárik University in Košice, SlovakiaA planar 3-connected graph G is essentially 4-connected if, for any 3-separator S of G, one component of the graph obtained from G by removing S is a single vertex. Jackson and Wormald proved that an essentially 4-connected planar graph on n vertices contains a cycle C such that . For a cubic essentially 4-connected planar graph G, Grünbaum with Malkevitch, and Zhang showed that G has a cycle on at least ¾ n vertices. In the present paper the result of Jackson and Wormald is improved. Moreover, new lower bounds on the length of a longest cycle of G are presented if G is an essentially 4-connected planar graph of maximum degree 4 or G is an essentially 4-connected maximal planar graph.https://doi.org/10.7151/dmgt.1875planar graphlongest cycle |
| spellingShingle | Fabrici Igor Harant Jochen Jendroľ Stanislav On Longest Cycles in Essentially 4-Connected Planar Graphs Discussiones Mathematicae Graph Theory planar graph longest cycle |
| title | On Longest Cycles in Essentially 4-Connected Planar Graphs |
| title_full | On Longest Cycles in Essentially 4-Connected Planar Graphs |
| title_fullStr | On Longest Cycles in Essentially 4-Connected Planar Graphs |
| title_full_unstemmed | On Longest Cycles in Essentially 4-Connected Planar Graphs |
| title_short | On Longest Cycles in Essentially 4-Connected Planar Graphs |
| title_sort | on longest cycles in essentially 4 connected planar graphs |
| topic | planar graph longest cycle |
| url | https://doi.org/10.7151/dmgt.1875 |
| work_keys_str_mv | AT fabriciigor onlongestcyclesinessentially4connectedplanargraphs AT harantjochen onlongestcyclesinessentially4connectedplanargraphs AT jendrolstanislav onlongestcyclesinessentially4connectedplanargraphs |