Graphs whose every transitive orientation contains almost every relation

Given a graph G on n vertices and a total ordering \(\prec\) of V(G), the transitive orientations of G associated with \(\prec\), denoted P(G;\(\prec)\), is the partial order on V(G) defined by setting \(x<y\) in P(G;\(\prec)\) if there is a path \(x=x_ 1x_ 2...x_ r=y\) in G such that \(x_ 1\prec x_ j\) for \(1\leq i<j\leq r\). We investigate graphs G such that every transitive orientation of G contains \(\left( \begin{matrix} n\\ 2\end{matrix} \right)-o(n^ 2)\) relations. We prove that almost every \(G_{n,p}\) satisfies this requirement if \[ \frac{pn \log \log \log n}{\log n \log \log n}\to \infty, \] but almost no \(G_{n,p}\) satisfies the condition if (pn log log log n)/(log n log log n) is bounded. We also show that every graph G with n vertices and at most cn log n edges has some transitive orientation with fewer than \(\left( \begin{matrix} n\\ 2\end{matrix} \right)-\delta (c)n^ 2\) relations.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Graphs whose every transitive orientation contains almost every relation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q581415)