Decomposing Kn ∪ P into triangles

機構典藏 > College of Sciences > Graduate Institute & Department of Mathematics > Journal Article > Item 987654321/41221

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/41221

Title:	Decomposing Kn ∪ P into triangles
Authors:	高金美;Kau, Chin-mei;Fu, Hung-lin;Rodger, C. A.
Contributors:	淡江大學數學學系
Keywords:	Triple system;Covering;Forest
Date:	2004-06-06
Issue Date:	2010-01-28 06:59:41 (UTC+8)
Publisher:	Elsevier
Abstract:	In this paper, we extend the work on minimum coverings of Kn with triangles. We prove that when P is any forest on n vertices the multigraph G=Kn∪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.
Relation:	Discrete Mathematics 284(1-3), pp.131-136
DOI:	10.1016/j.disc.2003.04.003
Appears in Collections:	[Graduate Institute & Department of Mathematics] Journal Article

Files in This Item:

File	Size	Format
	0Kb	Unknown	324	View/Open
Decomposing Kn ∪ P into triangles.pdf	212Kb	Adobe PDF	1	View/Open
index.html	0Kb	HTML	148	View/Open
index.html	0Kb	HTML	64	View/Open