Name
Abstract | ||
|---|---|---|
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 |V(C)|≥2n+45. For a cubic essentially 4-connected planar graph G, Grünbaum with Malkevitch, and Zhang showed that G has a cycle on at least 34n 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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.endm.2016.10.036 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
planar graph,longest cycle | Discrete mathematics,Wheel graph,Combinatorics,Bound graph,Graph power,Polyhedral graph,Cycle graph,Degree (graph theory),Graph bandwidth,Mathematics,Planar graph | Journal |
Volume | ISSN | Citations |
55 | 1571-0653 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jochen Harant | 1 | 217 | 30.62 |
| Igor Fabrici | 2 | 101 | 14.64 |
| Stanislav Jendrol' | 3 | 283 | 38.72 |