Charles Darwin University

CDU eSpace
Institutional Repository

CDU Staff and Student only

Completely separating systems of k-sets

Ramsay, C, Roberts, IT and Ruskey, F (1998). Completely separating systems of k-sets. Discrete Mathematics,183(1-3):265-2275.

Document type: Journal Article
Citation counts:
Google Scholar Search Google Scholar

Title Completely separating systems of k-sets
Author Ramsay, C
Roberts, IT
Ruskey, F
Journal Name Discrete Mathematics
Publication Date 1998
Volume Number 183
Issue Number 1-3
ISSN 0012-365X   (check CDU catalogue open catalogue search in new window)
Start Page 265
End Page 2275
Place of Publication netherlands
Publisher Elsevier
HERDC Category C1 - Journal Article (DEST)
Abstract Dickson [On a problem concerning separating systems of a finite set, Journal of Combinatorial Theory, 7 (1969), 191--196.] introduced the notion of a completely separating set system. We study such systems with the additional constraint that each set in the system has the same size. Let T denote an n-set. We say that a subset S of T separates i from j if i 2 S and j 62 S. A collection of k-sets C is called a (n; k)-separator if, for each ordered pair (i; j) 2 T \Theta T with i 6 = j, there is a set S 2 C which separates i from j. Let R(n; k) denote the size of a smallest (n; k)-separator. For n k(k- 1) we show that R(n; k) = d2n=ke. We also show that R(2 m
DOI   (check subscription with CDU E-Gateway service for CDU Staff and Students  check subscription with CDU E-Gateway in new window)
Version Filter Type
Access Statistics: 115 Abstract Views  -  Detailed Statistics
Created: Fri, 12 Sep 2008, 08:35:25 CST by Administrator