Completing partial commutative quasigroups constructed from partial Steiner triple systems is NP-complete

Bryant, D. (2009) Completing partial commutative quasigroups constructed from partial Steiner triple systems is NP-complete. Discrete Mathematics, 309 14: 4700-4704. doi:10.1016/j.disc.2008.05.037


Author Bryant, D.
Title Completing partial commutative quasigroups constructed from partial Steiner triple systems is NP-complete
Journal name Discrete Mathematics   Check publisher's open access policy
ISSN 0012-365X
Publication date 2009-07-01
Sub-type Article (original research)
DOI 10.1016/j.disc.2008.05.037
Volume 309
Issue 14
Start page 4700
End page 4704
Total pages 5
Editor D. B. West
Place of publication Netherlands
Publisher Elsevier B.V.
Language eng
Subject C1
970101 Expanding Knowledge in the Mathematical Sciences
010104 Combinatorics and Discrete Mathematics (excl. Physical Combinatorics)
Abstract Deciding whether an arbitrary partial commutative quasigroup can be completed is known to be NP-complete. Here, we prove that it remains NP-complete even if the partial quasigroup is constructed, in the standard way, from a partial Steiner triple system. This answers a question raised by Rosa in [A. Rosa, On a class of completable partial edge-colourings, Discrete Appl. Math. 35 (1992) 293–299]. To obtain this result, we prove necessary and sufficient conditions for the existence of a partial Steiner triple system of odd order having a leave L such that E(L)=E(G) where G is any given graph.
Formatted abstract
Deciding whether an arbitrary partial commutative quasigroup can be completed is known to be NP-complete. Here, we prove that it remains NP-complete even if the partial quasigroup is constructed, in the standard way, from a partial Steiner triple system. This answers a question raised by Rosa in [A. Rosa, On a class of completable partial edge-colourings, Discrete Appl. Math. 35 (1992) 293–299]. To obtain this result, we prove necessary and sufficient conditions for the existence of a partial Steiner triple system of odd order having a leave L such that E(L)=E(G) where G is any given graph.
Keyword Partial Steiner triple system
Commutative quasigroup
Triple system
Quasigroup
Q-Index Code C1
Q-Index Status Confirmed Code

Document type: Journal Article
Sub-type: Article (original research)
Collections: School of Mathematics and Physics
2010 Higher Education Research Data Collection
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 1 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 1 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Sat, 22 Aug 2009, 01:29:39 EST by Marie Grove on behalf of School of Mathematics & Physics