Journal article icon

Journal article

Separating systems and oriented graphs of diameter two

Abstract:
We prove results on the size of weakly and strongly separating set systems and matrices, and on cross-intersecting systems. As a consequence, we improve on a result of Katona and Szemerédi [G. Katona, E. Szemerédi, On a problem of graph theory, Studia Sci. Math. Hungar. 2 (1967) 23-28], who proved that the minimal number of edges in an oriented graph of order n with diameter 2 is at least (n / 2) log2 (n / 2). We show that the minimum is (1 + o (1)) n log2 n. © 2006 Elsevier Inc. All rights reserved.
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1016/j.jctb.2006.04.007

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Role:
Author
More from this funder
Name:
National Science Foundation
Grant:
DMS-0505550
Publisher:
Elsevier
Journal:
Journal of Combinatorial Theory. Series B More from this journal
Volume:
97
Issue:
2
Pages:
193-203
Publication date:
2007-01-01
DOI:
EISSN:
1096-0902
ISSN:
0095-8956
Language:
English
Keywords:
UUID:
uuid:8be6ae53-f4e4-453b-beea-4ee0ccfbe9ab
Local pid:
pubs:199403
Source identifiers:
199403
Deposit date:
2012-12-19

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP