Embedding path designs in 4-cycle systems
type: Item
instance of: scholarly article
title: Embedding path designs in 4-cycle systems
zbMATH Open document ID: 1007.05035
DOI: 10.1016/S0012-365X(01)00410-1
author: Gaetano Quattrocchi
published in: Discrete Mathematics
publication date: 2002-12-02T00:00:00Z
review text: A \(G\)-design of order \(n\) is an edge-disjoint decomposition of \(K_n\) into copies of the graph \(G\). A path design \(P(n,s,1)\) is a \(P_s\)-design of order \(n\), where \(P_s\) is the path with \(s\) vertices (and length \(s-1\)). An \(m\)-cycle system is a \(C_m\)-design, where \(C_m\) is the cycle of length \(m\). We say that a path design \(P(v,s,1)\) defined on the vertex set \(\Omega\) is embedded in an \(m\)-cycle system defined on the vertex set \(W\), with \(\Omega \subseteq W\), if the decomposition induced by the vertex set \(\Omega\) starting from the \(m\)-cycle system gives the path design (and isolated vertices). In the current work, for each admissible \(n\), all integers \(v \geq 3\) are determined such that there exists a \(P(v,3,1)\) embedded in a \(4\)-cycle system of order \(n\). This extends earlier results by \textit{S. Milici} and the author [Discrete Math. 208/209, 443-449 (1999; Zbl 0930.05009)], where the additional requirement that the path design be a handcuffed design---meaning that each vertex must belong to the same number of paths---was imposed.
Mathematics Subject Classification ID: 05B30
Mathematics Subject Classification ID: 05B05
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1838903
zbMATH Keywords: cycle
zbMATH Keywords: decomposition
zbMATH Keywords: embedding
zbMATH Keywords: graph design
zbMATH Keywords: path
reviewed by: Patric R. J. Östergård
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00410-1
OpenAlex ID: W2090479423
Recommended article: Embedding handcuffed designs with block size 2 or 3 in 4-cycle systems
Recommended article: Q3565862
Recommended article: Q3011824
Recommended article: Q3105541
Recommended article: Minimum embedding of balanced \(P_{4}\)-designs into 5-cycle systems.
Recommended article: Q4243808
Recommended article: Small embedding of an \(S_3(2,4,u)\) into an \(S_\lambda (2,4,u+w)\)
Recommended article: Q5419866
Recommended article: Q4853756
Recommended article: Q4858151
description: scientific article; zbMATH DE number 1838903