Bounding the size of square-free subgraphs of the hypercube

DOI10.1016/j.disc.2008.02.015zbMath1179.05059OpenAlexW2026067207MaRDI QIDQ1024494

Peter Wagner, Andrew G. Thomason

Publication date: 17 June 2009

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

Full work available at URL: https://doi.org/10.1016/j.disc.2008.02.015

zbMATH Keywords

hypercube\(n\)-cube\(4\)-cyclemaximum size of a subgraph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Related Items (17)

Extremal numbers for cycles in a hypercube ⋮ Random polynomial graphs for random Turán problems ⋮ Pairing strategies for the maker-breaker game on the hypercube with subcubes as winning sets ⋮ Bounding the size of the subgraph induced by \(m\) vertices and extra edge-connectivity of hypercubes ⋮ On even-cycle-free subgraphs of the hypercube ⋮ On even-cycle-free subgraphs of the hypercube ⋮ On a covering problem in the hypercube ⋮ On 14-Cycle-Free Subgraphs of the Hypercube ⋮ Maximum density of vertex-induced perfect cycles and paths in the hypercube ⋮ On even-cycle-free subgraphs of the doubled Johnson graphs ⋮ Extremal even-cycle-free subgraphs of the complete transposition graphs ⋮ Vertex Turán problems in the hypercube ⋮ Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube ⋮ Component Edge Connectivity of Hypercubes ⋮ The vertex Turán density in 3-ary \(n\)-cubes ⋮ Some Turán type results on the hypercube ⋮ Hypercube 1-factorizations from extended Hamming codes

Cites Work

• Unnamed Item
• Unnamed Item
• Largest induced subgraphs of the n-cube that contain no 4-cycles
• A Ramsey-type result for the hypercube
• Subgraphs of a hypercube containing no small even cycles
• On the maximum number of edges in a c₄‐free subgraph of q_n
• On quadrilaterals in layers of the cube and extremal problems for directed and oriented graphs

This page was built for publication: Bounding the size of square-free subgraphs of the hypercube