Back to search

The Open University

Combinatorial Embeddings and Representations

Abstract

dc:description.abstract

Topological embeddings of complete graphs and complete multipartite graphs give rise to combinatorial designs when the faces of the embeddings are triangles. In this case, the blocks of the design correspond to the triangular faces of the embedding. These designs include Steiner, twofold and Mendelsohn triple systems, as well as Latin squares. We look at construction methods, structural properties and other problems concerning these cases. In addition, we look at graph representations by Steiner triple systems and by combinatorial embeddings. This is closely related to finding independent sets in triple systems. We examine which graphs can be represented in Steiner triple systems and combinatorial embeddings of small orders and give several bounds including a bound on the order of Steiner triple systems that are guaranteed to represent all graphs of a given maximum degree. Finally, we provide an enumeration of graphs of up to six edges representable by Steiner triple systems.

Degree

thesis:*
Name dc:type.qualificationname
phd
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
The Open University
Year dc:date.issued
2012

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Psomas, Constantinos

Rights

Language dc:language
en

Chain of custody

source
Harvested from
The Open University
Base URL
oro.open.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Psomas, Constantinos. Combinatorial Embeddings and Representations. doctoral thesis, The Open University, 2012.