Intrinsic linking in directed graphs. (English) Zbl 1337.57016

This work extends the notion of intrinsic linking to directed graphs. A directed graph \(G\) is called intrinsically linked if it contains a nontrivial link consisting of a pair of consistently oriented directed cycles in every spatial embedding. The double directed version of a graph \(G\), denoted \(\overline{D(G)}\), is obtained by replacing each edge \(e\) of \(G\) by a pair of directed edges with opposite orientations joining the same pair of vertices as \(e\). The main result of this paper is that the double directed version of a graph \(G\) is intrinsically linked if and only if \(G\) is intrinsically linked.
As a corollary to this result it is shown that the complete symmetric directed graph on six vertices, \(\overline {J_6}\), is intrinsically linked, thus extending the work of Conway, Gordon and Sachs [J. H. Conway and C. McA. Gordon, J. Graph Theory 7, 445–453 (1983; Zbl 0524.05028)], [H. Sachs, in: Finite and infinite sets, 6th Hung. Combin. Colloq., Eger/Hung. 1981, Vol. II, Colloq. Math. Soc. János Bolyai 37, 649–662 (1984; Zbl 0568.05026)]. Several other results are shown for \(\overline {J_6}\) including the number of allowable edges that can be deleted to make the subgraph intrinsically linked or not.


57M25 Knots and links in the \(3\)-sphere (MSC2010)
57M15 Relations of low-dimensional topology with graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: Euclid


[1] J. Bang-Jensen and G. Gutin: Digraphs, second edition, Springer Monographs in Mathematics, Springer, London, 2009.
[2] C. Binucci, W. Didimo and F. Giordano: Maximum upward planar subgraphs of embedded planar digraphs , Comput. Geom. 41 (2008), 230-246. · Zbl 1152.05319 · doi:10.1016/j.comgeo.2008.02.001
[3] G. Bowlin and J. Foisy: Some new intrinsically 3-linked graphs , J. Knot Theory Ramifications 13 (2004), 1021-1027. · Zbl 1071.57003 · doi:10.1142/S0218216504003652
[4] J.H. Conway and C.McA. Gordon: Knots and links in spatial graphs , J. Graph Theory 7 (1983), 445-453. · Zbl 0524.05028 · doi:10.1002/jgt.3190070410
[5] E. Flapan, R. Naimi and J. Pommersheim: Intrinsically triple linked complete graphs , Topology Appl. 115 (2001), 239-246. · Zbl 0988.57003 · doi:10.1016/S0166-8641(00)00064-X
[6] P.P. Howards, E.F. Schisterman, C. Poole, J.S. Kaufman and C.R. Weinberg: “Toward a clearer definition of confounding” revisited with directed acyclic graphs , American Journal of Epidemiology 176 (2012), 506-511.
[7] R. Motwani, A. Raghunathan and H. Saran: Constructive results from graph minors: lintless embeddings ; in 29th Annual Symposium on Foundations of Computer Science (White Plains, NY, 1988), IEEE, 1988, 398-409.
[8] N. Robertson and P.D. Seymour: Graph minors . XX. Wagner’s conjecture , J. Combin. Theory Ser. B 92 (2004), 325-357. · Zbl 1061.05088 · doi:10.1016/j.jctb.2004.08.001
[9] N. Robertson, P.D. Seymour and R. Thomas: Sachs’ linkless embedding conjecture , J. Combin. Theory Ser. B 64 (1995), 185-227. · Zbl 0832.05032 · doi:10.1006/jctb.1995.1032
[10] H. Sachs: On spatial representations of finite graphs ; in Finite and Infinite Sets, I, II (Eger, 1981), Colloq. Math. Soc. János Bolyai 37 , North-Holland, Amsterdam, 1984, 649-662.
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.