On arcs in path designs of block size four (Q1377787): Difference between revisions

Let \(G\) be a subgraph of \(K_v\), the complete undirected graph on \(v\) vertices. A \(G\)-design of \(K_v\) is a pair \((V,{\mathcal B})\), where \(V\) is the vertex set of \(K_v\) and \({\mathcal B}\) is an edge-disjoint decomposition of \(K_v\) into copies of the graph \(G\). Usually we say that \(b\) is a block of the \(G\)-design if \(b\in{\mathcal B}\). \({\mathcal B}\) is called the block set. Given a block \(b\) we use the same symbol \(b\) to denote its vertex set. Let \(L\) be a set of edges of \(K_v\). A partial \(G\)-design is the decomposition of \(K_v/L\) into copies of the graph \( G\). The edge set \(L\) is called the leave of the partial \(G\)-design. A path design \(P(v,k,1)\) [see \textit{P. Hell} and \textit{A. Rosa}, Discrete Math. 2, 229-252 (1972; Zbl 0251.05015)] is a \(P_k\)-design of \(K_v\), where \(P_k\) is the simple path with \(k-1\) edges \((k\) vertices). The condition \(v(v-1)\equiv 0\pmod {2(k-1)}\), \(v\geq k\), is obviously necessary for the existence of a \(P(v,k,1)\). This condition was proved to be sufficient by \textit{M. Tarsi} [J. Comb. Theory, Ser. A 34, 60-70 (1983; Zbl 0511.05024)]. Therefore a \(P(v,3,1)\) exists if and only if \(v\equiv 0\) or \(1\pmod 4\), and a \(P(v,4,1)\) exists if and only if \(v\equiv 0\) or \(1\pmod 3\). A balanced \(G\)-design (see \textit{P. Hell} and \textit{R. Rosa} [op. cit.] and \textit{S. H. Y. Hung} and \textit{N. S. Mendelsohn} [Discrete Math. 18, 23-33 (1977; Zbl 0354.05016)]) is a \(G\)-design such that each vertex belongs to exactly \(r\) copies of \(G\). Obviously not every \(G\)-design is balanced. A (balanced) \(G\)-design of \(K_v\) is also called a (balanced) \(G\)-design of order \(v\). A handcuffed design \(H(v,k,1)\) is a balanced path design. Let \((V,{\mathcal B})\) be a path design \(P(v,k,1)\) with point set \(V\) and block set \({\mathcal B}\), and let \(\Omega\) be a subset of \(V\). A block \(b\in {\mathcal B}\) is called secant, tangent or exterior to \(\Omega\) if \(|b\cap \Omega |=2\), 1 or 0, respectively. The spanned set \({\mathcal S}(\Omega)\) is the set of all \(x\in V \setminus \Omega\) such that there is at least one secant block to \(\Omega\) on \(x\). The subset \(\Omega\) of \(V\) is a spanning set if \(x\in{\mathcal S} (\Omega)\), for every \(x\in V\setminus \Omega\). An arc in \((V,{\mathcal B})\) is a set \(\Omega\) of points of \(V\) no three of which are on a block. If \(\Omega\) is an arc in \((V,{\mathcal B})\), then any block is either secant or tangent or exterior to \(\Omega\). An arc \(\Omega\) is said to be complete if it is maximal with respect to set inclusion, i.e., if \(\Omega\cup \{x\}\) is not an arc for each \(x\in V\setminus\Omega\). A scattering set \(\Omega\subseteq V\) is an arc for which every \(x\in V\setminus \Omega\) has the property that \(x\) appears in at most one secant block to \(\Omega\). Clearly a \(P(4,4,1)\) cannot contain a scattering set. It is straightforward to verify that every complete arc is a spanning set, but the converse need not hold. The definitions of spanning and scattering sets and resulting problems can be found in [\textit{C. J. Colbourn}, \textit{J. H. Dinitz}, and \textit{D. R. Stinson}, J. Comb. Theory, Ser. A 57, No. 1, 46-59 (1991; Zbl 0765.05016)], where these notions are introduced for Steiner triple systems. There Colbourn et al. exhibit, for every admissible \(v\), a Steiner triple system \(\text{STS} (v)\) with a spanning set of minimum cardinality and an \(\text{STS} (v)\) with a scattering set of maximum cardinality. In this process, they also establish the existence of Steiner triple systems with complete arcs of minimum possible cardinality. The analogous problems for handcuffed designs \(H(v,3,1)\) and path designs \(P(v,3,1)\) are completely solved in [\textit{G. Quattrocchi}, Spanning sets and scattering sets in handcuffed designs of order \(v\) and block size 3, preprint] and [\textit{S. Milici}, Geom. Dedicata 47, No. 1, 49-56 (1993; Zbl 0783.51004)], respectively. In this paper the author exhibits, for each \(v\equiv 0,1 \pmod 3\), a \(P(v,4,1)\) with a spanning set of minimum cardinality and a \(P(v,4,1)\) with a scattering set of maximum cardinality.