Bounding the size of square-free subgraphs of the hypercube

DOI10.1016/J.DISC.2008.02.015MaRDI QIDQ1024494zbMATH OpenOpenAlexFDO

Authors Peter Wagner, Andrew 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)

Recommendations

• Minimum critical squarefree subgraph of a hypercube
• scientific article; zbMATH DE number 434690
• On the maximum number of edges in a c₄‐free subgraph of q_n
• An extremal theorem in the hypercube
• scientific article; zbMATH DE number 19183

Cites work

• scientific article; zbMATH DE number 3869331 (Why is no real title available?)
• scientific article; zbMATH DE number 790416 (Why is no real title available?)
• A Ramsey-type result for the hypercube
• Largest induced subgraphs of the n-cube that contain no 4-cycles
• On quadrilaterals in layers of the cube and extremal problems for directed and oriented graphs
• On the maximum number of edges in a c₄‐free subgraph of q_n
• Subgraphs of a hypercube containing no small even cycles

Cited in

(30)

• Component edge connectivity of hypercubes
• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
• scientific article; zbMATH DE number 434690 (Why is no real title available?)
• scientific article; zbMATH DE number 5778712 (Why is no real title available?)
• Random polynomial graphs for random Turán problems
• Pairing strategies for the maker-breaker game on the hypercube with subcubes as winning sets
• Eigenvalues of subgraphs of the cube
• The outercoarseness of the \(n\)-cube
• Long geodesics in subgraphs of the cube
• On even-cycle-free subgraphs of the doubled Johnson graphs
• Minimum critical squarefree subgraph of a hypercube
• Saturated subgraphs of the hypercube
• The vertex Turán density in 3-ary \(n\)-cubes
• Subgraphs of a hypercube containing no small even cycles
• On the maximum number of edges in a c₄‐free subgraph of q_n
• Some Turán type results on the hypercube
• A class of graphs of zero Turán density in a hypercube
• Extremal numbers for cycles in a hypercube
• The Complexity of Approximately Counting Retractions to Square-free Graphs
• Extremal even-cycle-free subgraphs of the complete transposition graphs
• On 14-Cycle-Free Subgraphs of the Hypercube
• On graphs embeddable in a layer of a hypercube and their extremal numbers
• On a covering problem in the hypercube
• On even-cycle-free subgraphs of the hypercube
• On even-cycle-free subgraphs of the hypercube
• Hypercube 1-factorizations from extended Hamming codes
• Bounding the size of the subgraph induced by \(m\) vertices and extra edge-connectivity of hypercubes
• Improved lower bounds for multiplicative square-free sequences
• Vertex Turán problems in the hypercube
• Maximum density of vertex-induced perfect cycles and paths in the hypercube

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

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