Sparseness of 4-cycle systems

Yuichiro Fujiwara*, Shung Liang Wu, Hung-Lin Fu

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

An avoidance problem of configurations in 4-cycle systems is investigated by generalizing the notion of sparseness, which is originally from Erdos' r-sparse conjecture on Steiner triple systems. A 4-cycle system of order v, 4CS(v), is said to be r-sparse if for every integer j satisfying 2 ≤ j ≤ r it contains no configurations consisting of j 4-cycles whose union contains precisely j + 3 vertices. If an r-sparse 4CS(v) is also free from copies of a configuration on two 4-cycles sharing a diagonal, called the double-diamond, we say it is strictly r-sparse. In this paper, we show that for every admissible order v there exists a strictly 4-sparse 4CS(v). We also prove that for any positive integer r ≥ 2 and sufficiently large integer v there exists a constant number c such that there exists a strictly r-sparse 4-cycle packing of order v with c · v2 4-cycles.

Original languageEnglish
Pages (from-to)175-185
Number of pages11
JournalJournal of Combinatorial Mathematics and Combinatorial Computing
Volume75
StatePublished - 1 Nov 2010

Keywords

  • 4-Cycle system
  • Avoidance
  • Configuration
  • R-sparse

Fingerprint Dive into the research topics of 'Sparseness of 4-cycle systems'. Together they form a unique fingerprint.

  • Cite this