Premium
Biembedding a Steiner Triple System With a Hamilton Cycle Decomposition of a Complete Graph
Author(s) -
McCourt Thomas A.
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21774
Subject(s) - mathematics , combinatorics , embedding , graph , complete graph , hamiltonian path , petersen graph , discrete mathematics , voltage graph , computer science , artificial intelligence , line graph
We construct a face two‐colourable, blue and green say, embedding of the complete graph K n in a nonorientable surface in which there are ( n − 1 ) / 2 blue faces each of which have a hamilton cycle as their facial walk and n ( n − 1 ) / 6 green faces each of which have a triangle as their facial walk; equivalently a biembedding of a Steiner triple system of order n with a hamilton cycle decomposition of K n , for all n ≡ 3 ( mod 36 ) and n ≠ 3 . Using a variant of this construction, we establish the minimum genus of nonorientable embeddings of the graphK 36 k + 3 + K m ¯ , for m = 18 k + 1 + 6 s where k ≥ 1 and 0 ≤ s ≤ k − 1 .