×

Spanning Eulerian subdigraphs avoiding \(k\) prescribed arcs in tournaments. (English) Zbl 1448.05083

Summary: N. Lichiardopol [ibid. 313, No. 14, 1540–1542 (2013; Zbl 1408.05101)] proved that every \((k+1)\)-strong tournament has a Hamiltonian cycle which avoids any prescribed set of \(k\) arcs. The first and the third author [“Spanning Eulerian subdigraphs in semicomplete digraphs”, Preprint, arXiv:1905.11019] showed that a number of results concerning vertex-connectivity and Hamiltonian cycles in tournaments have analogues when we replace vertex connectivity by arc-connectivity and Hamiltonian cycles by spanning Eulerian subdigraphs. They proved the existence of a smallest function \(f(k)\) with the property that every \(f(k)\)-arc-strong semicomplete digraph has a spanning Eulerian subdigraph which avoids any prescribed set of \(k\) arcs by showing that \(f(k)\leq\frac{(k+1)^2+4}{4}\). They conjectured that every \((k+1)\)-arc-strong semicomplete digraph has a spanning Eulerian subdigraph which avoids any prescribed set of \(k\) arcs and verified this for \(k=2,3\). In this paper we prove that \(f(k)\leq\lceil\frac{6k+1}{5}\rceil\). In particular, the conjecture holds for \(k\leq 4\)

MSC:

05C20 Directed graphs (digraphs), tournaments

Citations:

Zbl 1408.05101
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alsatami, K. A.; Zhang, X.; Liu, J.; Lai, H.-J., On a class of supereulerian digraphs, Appl. Math., 7, 320-326 (2016)
[2] Bang-Jensen, J.; Gutin, G., Digraphs: Theory, Algorithms and Applications (2009), Springer-Verlag: Springer-Verlag London · Zbl 1170.05002
[3] Bang-Jensen, J.; Havet, F., Tournaments and semicomplete digraphs, (Bang-Jensen, J.; Gutin, G., Classes of Directed Graphs (2018), Springer Verlag: Springer Verlag London), 35-124, (Chapter 2) · Zbl 1407.05102
[4] J. Bang-Jensen, F. Havet, A. Yeo, Spanning eulerian subdigraphs in semicomplete digraphs, 2019, submitted for publication, preprint available on ArXiv: https://arxiv.org/abs/1905.11019.
[5] Bang-Jensen, J.; Maddaloni, A., Sufficient conditions for a digraph to be supereulerian, J. Graph Theory, 79, 1, 8-20 (2015) · Zbl 1312.05060
[6] Camion, Paul, Chemins et circuits hamiltoniens des graphes complets, C. R. Acad. Sci., Paris, 249, 2151-2152 (1959) · Zbl 0092.15801
[7] Fraisse, P.; Thomassen, C., Hamiltonian dicycles avoiding prescribed arcs in tournaments, Graphs Combin., 3, 3, 239-250 (1987) · Zbl 0622.05028
[8] Kúhn, D.; Otshus, D., A survey on Hamilton cycles in directed graphs, European J. Combin., 33, 750-756 (2012)
[9] Lei, L.; Li, X.-M.; Wang, B., On (s,t)-supereulerian locally connected graphs, (ICCS2007. ICCS2007, Lecture Notes in Computer Science, vol. 4489 (2007)), 384-388
[10] Lei, L.; Li, X.-M.; Wang, B.; Lai, H.-J., On (s,t)-supereulerian graphs in locally highly connected graphs, Discrete Math., 310, 4, 929-934 (2010) · Zbl 1216.05070
[11] Luo, W.; Chen, Z.-H.; Chen, W.-G., Spanning trails containing given edges, Discrete Math., 306, 1, 87-98 (2006) · Zbl 1086.05045
[12] Meyniel, H., Une condition suffisante d’existence d’un circuit hamiltonien dans un graphe orienté, J. Combin. Theory Ser. B, 14, 137-147 (1973) · Zbl 0259.05114
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.