×

Point determining digraphs, \(\{ 0,1 \}\)-matrix partitions, and dualities in full homomorphisms. (English) Zbl 1315.05066

Summary: A digraph \(D\) is point determining if for any two distinct vertices \(u, v\) there exists a vertex \(w\) which has an arc to (or from) exactly one of \(u, v\). We prove that every point-determining digraph \(D\) contains a vertex \(v\) such that \(D - v\) is also point determining. We apply this result to show that for any \(\{0, 1 \}\)-matrix \(M\), with \(k\) diagonal zeros and \(\ell\) diagonal ones, the size of a minimal \(M\)-obstruction is at most \((k + 1)(\ell + 1)\). This is a best possible bound, and it extends the results of D. P. Sumner [ibid. 5, 179–187 (1973; Zbl 0265.05124)], and of T. Feder and P. Hell [ibid. 308, No. 9, 1639–1652 (2008; Zbl 1135.05042)], from undirected graphs and symmetric matrices to digraphs and general matrices.

MSC:

05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ball, R. N.; Nešetřil, J.; Pultr, A., Dualities in full homomorphisms, European J. Combin., 31, 106-119 (2010) · Zbl 1219.05092
[2] Feder, T.; Hell, P., On realizations of point determining graphs and obstructions to full homomorphisms, Discrete Math., 308, 1639-1652 (2008) · Zbl 1135.05042
[3] Feder, T.; Hell, P.; Klein, S.; Motwani, R., List partitions, SIAM J. Discrete Math., 16, 449-478 (2003) · Zbl 1029.05143
[4] Hell, P., Graph partitions with prescribed patterns, European J. Combin., 35, 335-353 (2014) · Zbl 1292.05214
[6] Hell, P.; Nešetřil, J., Graphs and Homomorphisms (2004), Oxford University Press · Zbl 1062.05139
[7] Pultr, A.; Trnková, V., Combinatorial, Algebraic and Topological Representations of Groups, Semigroups and Categories (1980), North-Holland · Zbl 0418.18004
[8] Sumner, D., Point determination in graphs, Discrete Math., 5, 179-187 (1973) · Zbl 0265.05124
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.