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 vertical bar V(C)vertical bar >= 2n+4/5 For a cubic essentially 4-connected planar graph G, Grunbaum with Malkevitch, and Zhang showed that G has a cycle on at least 3/4 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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.7151/dmgt.1875 | DISCUSSIONES MATHEMATICAE GRAPH THEORY |
Keywords | Field | DocType |
planar graph,longest cycle | Longest cycle,Discrete mathematics,Combinatorics,Cycle basis,Chordal graph,Pancyclic graph,Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
36 | 3 | 1234-3099 |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Igor Fabrici | 1 | 101 | 14.64 |
| Jochen Harant | 2 | 217 | 30.62 |
| Stanislav Jendrol' | 3 | 283 | 38.72 |