標題: Decomposing K-n UP into triangles
作者: Fu, CM
Fu, HL
Rodger, CA
應用數學系
Department of Applied Mathematics
關鍵字: triple system;covering;forest
公開日期: 6-Jul-2004
摘要: In this paper, we extend the work on minimum coverings of K-n with triangles. We prove that when P is any forest on n vertices the multigraph G = K-n boolean OR P can be decomposed into triangles if and only if three trivial necessary conditions are satisfied: (i) each vertex in G has even degree, (ii) each vertex in P has odd degree, and (iii) the number of edges in G is a multiple of 3. This result is of particular interest because the corresponding packing problem where the leave is any forest is yet to be solved. We also consider some other families of packings, and provide a variation on a proof by Colbourn and Rosa which settled the packing problem when P is any 2-regular graph on at most n vertices. (C) 2004 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.disc.2003.04.003
http://hdl.handle.net/11536/26572
ISSN: 0012-365X
DOI: 10.1016/j.disc.2003.04.003
期刊: DISCRETE MATHEMATICS
Volume: 284
Issue: 1-3
起始頁: 131
結束頁: 136
Appears in Collections:Articles


Files in This Item:

  1. 000222553900013.pdf