Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646847 | Discrete Mathematics | 2015 | 8 Pages |
Abstract
A digraph DD is point determining if for any two distinct vertices u,vu,v there exists a vertex ww which has an arc to (or from) exactly one of u,vu,v. We prove that every point-determining digraph DD contains a vertex vv such that D−vD−v is also point determining. We apply this result to show that for any {0,1}{0,1}-matrix MM, with kk diagonal zeros and ℓℓ diagonal ones, the size of a minimal MM-obstruction is at most (k+1)(ℓ+1)(k+1)(ℓ+1). This is a best possible bound, and it extends the results of Sumner, and of Feder and Hell, from undirected graphs and symmetric matrices to digraphs and general matrices.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Pavol Hell, César Hernández-Cruz,