Representing graphs in Steiner triple systems

Archdeacon, Dan; Griggs, Terry and Psomas, Costas (2014). Representing graphs in Steiner triple systems. Graphs and Combinatorics, 30 pp. 255–266.

DOI: https://doi.org/10.1007/s00373-012-1279-3

Abstract

Let G = (V, E) be a simple graph and let T = (P, B) be a Steiner triple system. Let φ be a one-to-one function from V to P. Any edge e = {u, v} has its image {φ(u), φ(v)} in a unique block in B. We also denote this induced function from edges to blocks by φ. We say that T represents G if there exists a one-to-one function φ : V → P such that the induced function φ : E → B is also one-to-one; that is, if we can represent vertices of the graph by points of the triple system such that no two edges are represented by the same block. In this paper we examine when a graph can be represented by an STS. First, we find a bound which ensures that every graph of order n is represented in some STS of order f(n). Second, we find a bound which ensures that every graph of order n is represented in every STS of order g(n). Both of these answers are related to finding an independent set in an STS. Our question is a generalization of finding such independent sets. We next examine which graphs can be represented in STS’s of small orders. Finally, we give bounds on the orders of STS’s that are guaranteed to embed all graphs of a given maximum degree.

Viewing alternatives

Metrics

Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions

Export

About

Recommendations