Hybrid triple systems and cubic feedback sets期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Hybrid triple systems and cubic feedback sets

Authors:	Charles J Colbourn William R Pulleyblank Alexander Rosa

Institution:	(1) Department of Computer Science, University of Waterloo, N2L 3G1 Waterloo, Ontario, Canada;(2) Department of Combinatorics, Optimization University of Waterloo, N2L 3G1 Waterloo, Ontario, Canada;(3) Department of Mathematics, Statistics McMaster University, L8S 4K1 Hamilton, Ontario, Canada

Abstract:	Ac-hybrid triple system of orderv is a decomposition of the completev-vertex digraph intoc cyclic tournaments of order 3 and $\frac{{v(v - 1)}}{3} - c$ transitive tournaments of order 3. Hybrid triple systems generalize directed triple systems (c = 0) and Mendelsohn triple systems (c = v(v – 1)/3); omitting directions yields an underlying twofold triple system. The spectrum ofv andc for which ac-hybrid triple system of orderv exists is completely determined in this paper. Using (cubic) block intersection graphs, we then show that every twofold triple system of order $v\left( {having b_v = \frac{{v(v - 1)}}{3}blocks} \right)$ underlies ac-hybrid triple system with $c \geqslant \frac{{2b_v }}{3}$ . Examples are constructed for all sufficiently largev, for which this maximum is at most $\left( {\frac{7}{{10}} + \varepsilon } \right)b_v$ . The lower bound here is proved by establishing bounds onF _i(n, r), the size of minimum cardinality vertex feedback sets inn-vertexi-connected cubic multigraphs havingr repeated edges. We establish that $F_0 (n,r) \leqslant \frac{n}{2},$ , $F_1 (n,r) \leqslant \frac{{3n}}{8} + \frac{r}{4} + \frac{1}{2}, and F_2 (n,r) \leqslant \frac{{(n + r)}}{3}for n > 8$ . These bounds are all tight, and the latter is used to derive the lower bound in the design theoretic problem.

Keywords:
本文献已被 SpringerLink 等数据库收录！

设为首页 | 免责声明 | 关于勤云 | 加入收藏