On the number of cycles in 3-connected cubic graphs

DOI10.1006/JCTB.1997.1771MaRDI QIDQ1386478zbMATH OpenOpenAlexFDO

Authors R. E. L. Aldred, Carsten Thomassen

Publication date 10 August 1998

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jctb.1997.1771

zbMATH Keywords

cubic graphnumber of cycles

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Paths and cycles (05C38)

Review text

Let \(f(n)\) denote the minimum number of cycles in a 3-connected cubic graph. The authors show that \(f(n)\) is superpolynomial, by showing that for \(n\) sufficiently large, \(2^{n^{0.17}}<f(n)<2^{n^{0.95}}\). This confirms a conjecture by \textit{C. A. Barefoot}, \textit{L. Clark} and \textit{R. Entringer} [Congr. Nummerantium 53, 49-62 (1986; Zbl 0623.05033)].

Recommendations

• scientific article; zbMATH DE number 4010555
• scientific article; zbMATH DE number 3906529
• On the number of cycles in a graph
• scientific article; zbMATH DE number 3963871
• Small cycle covers of 3-connected cubic graphs

Cites work

• scientific article; zbMATH DE number 4010555 (Why is no real title available?)
• scientific article; zbMATH DE number 863469 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• Longest Cycles in 3-Connected 3-Regular Graphs
• Longest cycles in 3-connected cubic graphs

Cited in

(22)

• The numbers of spanning trees of the cubic cycle \(C_ n^ 3\) and the quadruple cycle \(C_ n^ 4\)
• On cycles in 3-connected graphs
• \(D_ \lambda\)-cycles in 3-cyclable graphs
• Cycles in 5-connected triangulations
• The minimum number of minimal codewords in an \([n, k]\)-code and in graphic codes
• A family of efficient six-regular circulants representable as a Kronecker product
• Enumeration of the degree sequences of 3-connected graphs and cactus graphs.
• scientific article; zbMATH DE number 4154474 (Why is no real title available?)
• scientific article; zbMATH DE number 4010555 (Why is no real title available?)
• scientific article; zbMATH DE number 4079454 (Why is no real title available?)
• An 11-vertex theorem for 3-connected cubic graphs
• Cyclability of 3-connected graphs
• Graphs with cyclomatic number three having panconnected square
• On the number of cycles in a graph
• scientific article; zbMATH DE number 1916558 (Why is no real title available?)
• Regular graphs with few longest cycles
• HOW MANY n-CYCLES DOES PERIOD 3 IMPLY? AN ELEMENTARY APPROACH
• Combinatorial Geometry and Graph Theory
• Small cycle covers of 3-connected cubic graphs
• On the pagenumber of the cube-connected cycles
• Triangle-free graphs with the maximum number of cycles
• Edge reductions in cyclically \(k\)-connected cubic graphs

This page was built for publication: On the number of cycles in 3-connected cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1386478)