Longer Cycles in Essentially 4-Connected Planar Graphs
A planar 3-connected graph G is called essentially 4-connected if, for every 3-separator S, at least one of the two components of G − S is an isolated vertex. Jackson and Wormald proved that the length circ(G) of a longest cycle of any essentially 4-connected planar graph G on n vertices is at least...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2020-02-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2133 |
| _version_ | 1827832795377958912 |
|---|---|
| author | Fabrici Igor Harant Jochen Mohr Samuel Schmidt Jens M. |
| author_facet | Fabrici Igor Harant Jochen Mohr Samuel Schmidt Jens M. |
| author_sort | Fabrici Igor |
| collection | DOAJ |
| description | A planar 3-connected graph G is called essentially 4-connected if, for every 3-separator S, at least one of the two components of G − S is an isolated vertex. Jackson and Wormald proved that the length circ(G) of a longest cycle of any essentially 4-connected planar graph G on n vertices is at least
2n+45{{2n + 4} \over 5}
and Fabrici, Harant and Jendrol’ improved this result to
circ(G)≥12(n+4){\rm{circ}} ( G ) \ge {1 \over 2} ( {n + 4} )
. In the present paper, we prove that an essentially 4-connected planar graph on n vertices contains a cycle of length at least
35(n+2){3 \over 5} ( {n + 2} )
and that such a cycle can be found in time O(n2). |
| first_indexed | 2024-03-12T05:19:50Z |
| format | Article |
| id | doaj.art-84232c70660d4d9eae66c14880a3f055 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T05:19:50Z |
| publishDate | 2020-02-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-84232c70660d4d9eae66c14880a3f0552023-09-03T07:47:21ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922020-02-0140126927710.7151/dmgt.2133dmgt.2133Longer Cycles in Essentially 4-Connected Planar GraphsFabrici IgorHarant JochenMohr SamuelSchmidt Jens M.A planar 3-connected graph G is called essentially 4-connected if, for every 3-separator S, at least one of the two components of G − S is an isolated vertex. Jackson and Wormald proved that the length circ(G) of a longest cycle of any essentially 4-connected planar graph G on n vertices is at least 2n+45{{2n + 4} \over 5} and Fabrici, Harant and Jendrol’ improved this result to circ(G)≥12(n+4){\rm{circ}} ( G ) \ge {1 \over 2} ( {n + 4} ) . In the present paper, we prove that an essentially 4-connected planar graph on n vertices contains a cycle of length at least 35(n+2){3 \over 5} ( {n + 2} ) and that such a cycle can be found in time O(n2).https://doi.org/10.7151/dmgt.2133essentially 4-connected planar graphlongest cyclecircumferenceshortness coefficient05c3805c10 |
| spellingShingle | Fabrici Igor Harant Jochen Mohr Samuel Schmidt Jens M. Longer Cycles in Essentially 4-Connected Planar Graphs Discussiones Mathematicae Graph Theory essentially 4-connected planar graph longest cycle circumference shortness coefficient 05c38 05c10 |
| title | Longer Cycles in Essentially 4-Connected Planar Graphs |
| title_full | Longer Cycles in Essentially 4-Connected Planar Graphs |
| title_fullStr | Longer Cycles in Essentially 4-Connected Planar Graphs |
| title_full_unstemmed | Longer Cycles in Essentially 4-Connected Planar Graphs |
| title_short | Longer Cycles in Essentially 4-Connected Planar Graphs |
| title_sort | longer cycles in essentially 4 connected planar graphs |
| topic | essentially 4-connected planar graph longest cycle circumference shortness coefficient 05c38 05c10 |
| url | https://doi.org/10.7151/dmgt.2133 |
| work_keys_str_mv | AT fabriciigor longercyclesinessentially4connectedplanargraphs AT harantjochen longercyclesinessentially4connectedplanargraphs AT mohrsamuel longercyclesinessentially4connectedplanargraphs AT schmidtjensm longercyclesinessentially4connectedplanargraphs |