Premium
On the maximum number of cycles in a planar graph
Author(s) -
Aldred R. E. L.,
Thomassen Carsten
Publication year - 2008
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20290
Subject(s) - combinatorics , mathematics , cartesian product , planar graph , graph , planar , wheel graph , path graph , path (computing) , prism , discrete mathematics , graph power , line graph , computer science , physics , optics , computer graphics (images) , programming language
Let G be a graph on p vertices with q edges and let r = q − p = 1. We show that G has at most ${15\over 16} 2^{r}$ cycles. We also show that if G is planar, then G has at most 2 r − 1 = o (2 r − 1 ) cycles. The planar result is best possible in the sense that any prism, that is, the Cartesian product of a cycle and a path with one edge, has more than 2 r − 1 cycles. © Wiley Periodicals, Inc. J. Graph Theory 57: 255–264, 2008
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom