Defining sets in combinatorics: a survey
Diane M. Donovan, E. S. Mahmoodian, Colin M. Ramsay, Anne Street · Cambridge University Press eBooks · 2003
In a given class of combinatorial structures there may be many distinct objects with the same parameters. Two questions arise naturally. Given two such objects, where and how do they differ? How much of an individual object is needed to identify it uniquely? These questions are obviously related, the first leading to the concept of a trade , and the second to that of a defining set . This survey deals with denning sets in block designs, graphs and some related structures. The corresponding trades in each structure are also discussed briefly. Introduction We start with a simple example. A graph G = ( V, E ) consists of a finite set V of elements called vertices , and a set E of unordered pairs of vertices, called edges . The complete graph on v vertices, K v , is a graph in which all pairs of distinct vertices constitute edges, so that any graph on v or fewer vertices may be considered as a subgraph of K v . If v = 2 n , then a one-factor of K v is a set of n unordered pairs which between them contain each element of V precisely once. A defining set of a one-factor is a subset of its edges which uniquely identifies it. More generally, a perfect matching in a graph G on 2 n vertices is a set of n edges incident with each vertex of V .