Cycle-maximal triangle-free graphs

DOI10.1016/j.disc.2014.10.002zbMath1303.05091arXiv1310.5172OpenAlexW2017923854MaRDI QIDQ472981

Matthew Skala, Stephane Durocher, (Ben) P. C. Li, David S. Gundersson

Publication date: 20 November 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1310.5172

zbMATH Keywords

cycleregular graphtriangle-freeextremal graph theory\(\#\mathrm P\)-completematrix permanent

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Triangle-free graphs with the maximum number of cycles ⋮ Maximising the number of cycles in graphs with forbidden subgraphs

Cites Work

• The complexity of computing the permanent
• On a theorem of Rademacher-Turán
• How to make a graph bipartite
• Graphs whose every independent set has a common neighbour
• A note on a paper by D. Seinsche
• The number of cycles in a Hamilton graph
• Estimations for the number of cycles in a graph
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• Triangle-free four-chromatic graphs
• Bounding the locality of distributed routing algorithms
• On a property of the class of n-colorable graphs
• On the maximum number of cycles in a Hamiltonian graph
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• ECLⁱPS^e – From LP to CLP
• Easy problems for tree-decomposable graphs
• On the Number of Cycles in Planar Graphs
• Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems
• ODD Cycles of Specified Length in Non-Bipartite Graphs
• On the Structure of Dense Triangle-Free Graphs
• Triangle-Free Graphs with High Minimal Degrees
• The Parameterized Complexity of Counting Problems
• Linear-time computation of optimal subgraphs of decomposable graphs
• Graphentheoretische Extremalprobleme
• On the maximum number of cycles in a planar graph
• On the maximum number of cycles in outerplanar and series-parallel graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item