Hostname: page-component-745bb68f8f-s22k5 Total loading time: 0 Render date: 2025-02-11T07:09:29.775Z Has data issue: false hasContentIssue false
  • English
  • Français

On 14-Cycle-Free Subgraphs of the Hypercube

Published online by Cambridge University Press:  01 September 2009

ZOLTÁN FÜREDI  and
LALE ÖZKAHYA
ZOLTÁN FÜREDI
Affiliation:
Rényi Institute of the Hungarian Academy, Budapest, P.O. Box 127, Hungary, H-1364 and Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA (e-mail: furedi@renyi.hu, z-furedi@math.uiuc.edu)
LALE ÖZKAHYA
Affiliation:
Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA (e-mail: ozkahya@illinois.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

It is shown that the size of a subgraph of Qn without a cycle of length 14 is of order o(|E(Qn)|).

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 18 , Issue 5: New Directions in Algorithms, Combinatorics and Optimization , September 2009 , pp. 725 - 729
Copyright
Copyright © Cambridge University Press 2009

References

[1]Alon, N., Krech, A. and Szabó, T. (2007) Turán's theorem in the hypercube. SIAM J. Discrete Math. 21 66–72.CrossRefGoogle Scholar
[2]Alon, N., Radoičic, R., Sudakov, B. and Vondrák, J. (2006) A Ramsey-type result for the hypercube. J. Graph Theory 53 196–208.CrossRefGoogle Scholar
[3]Axenovich, M. and Martin, R. (2006) A note on short cycles in a hypercube. Discrete Math. 306 2212–2218.CrossRefGoogle Scholar
[4]Bialostocki, A. (1983) Some Ramsey type results regarding the graph of the n-cube. Ars Combin. 16 A 39–48.Google Scholar
[5]Bondy, J. and Simonovits, M. (1974) Cycles of even lengths in graphs. J. Combin. Theory Ser. B 16 97–105.CrossRefGoogle Scholar
[6]Brass, P., Harborth, H. and Nienborg, H. (1995) On the maximum number of edges in a C 4-free subgraph of Q n. J. Graph Theory 19 17–23.CrossRefGoogle Scholar
[7]Chung, F. (1992) Subgraphs of a hypercube containing no small even cycles. J. Graph Theory 16 273–286.CrossRefGoogle Scholar
[8]Conder, M. (1993) Hexagon-free subgraphs of hypercubes. J. Graph Theory 17 477–479.CrossRefGoogle Scholar
[9]Erdős, P. (1984) On some problems in graph theory, combinatorial analysis and combinatorial number theory. Graph Theory Combin. 1–17.Google Scholar
[10]Erdős, P. and Simonovits, M. (1970) Some extremal problems in graph theory. In Combinatorial Theory and its Applications I (Proc. Colloq. Balatonfüred 1969), pp. 377–390.Google Scholar
[11]Harborth, H. and Nienborg, H. (1994) Maximum number of edges in a six-cube without four cycles. Bull. Inst. Combin. Appl. 12 55–60.Google Scholar
[12]Johnson, K. A. and Entringer, R. (1989) Largest induced subgraphs of the n-cube that contain no 4-cycles. J. Combin. Theory Ser. B 46 346–355.CrossRefGoogle Scholar
[13]Kostochka, E. A. (1976) Piercing the edges of the n-dimensional unit cube (in Russian). Diskret. Analiz Vyp. 28 55–64.Google Scholar
[14]Lu, L. Hexagon-free subgraphs in hypercube Q n. Private communication.Google Scholar
[15]Offner, D. (2008) Polychromatic colorings of the hypercube. SIAM J. Discrete Math. 22 450–454.CrossRefGoogle Scholar
[16]Schelp, R. H. and Thomason, A. (2000) On quadrilaterals in layers of the cube and extremal problems for directed and oriented graphs. J. Graph Theory 33 66–82.3.0.CO;2-L>CrossRefGoogle Scholar
[17]Thomason, A. and Wagner, P. (2009) Bounding the size of square-free subgraphs of the hypercube. Discrete Math. 309 1730–1735.CrossRefGoogle Scholar