Loading...
Please wait, while we are loading the content...
Similar Documents
On the Number of Simple Cycles in Planar Graphs
| Content Provider | Scilit |
|---|---|
| Author | Alt, Helmut Fuchs, Ulrich Kriegel, Klaus |
| Copyright Year | 1999 |
| Description | Let C(G) denote the number of simple cycles of a graph G and let C(n) be the maximum of C(G) over all planar graphs with n nodes. We present a lower bound on C(n), constructing graphs with at least $2.28^{n}$ cycles. Applying some probabilistic arguments we prove an upper bound of $3.37^{n}$.We also discuss this question restricted to the subclasses of grid graphs, bipartite graphs, and 3-colourable triangulated graphs. |
| Related Links | https://refubium.fu-berlin.de/bitstream/fub188/19357/1/tr-b-97-08.pdf https://www.cambridge.org/core/services/aop-cambridge-core/content/view/DF07C39D77A289BCEBFC1A6C695E9E65/S0963548399003995a.pdf/div-class-title-on-the-number-of-simple-cycles-in-planar-graphs-div.pdf |
| Ending Page | 405 |
| Page Count | 9 |
| Starting Page | 397 |
| ISSN | 09635483 |
| e-ISSN | 14692163 |
| DOI | 10.1017/s0963548399003995 |
| Journal | Combinatorics, Probability and Computing |
| Issue Number | 5 |
| Volume Number | 8 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 1999-09-01 |
| Access Restriction | Open |
| Subject Keyword | Combinatorics, Probability and Computing |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics |
