×

zbMATH — the first resource for mathematics

Strongly 2-connected orientations of graphs. (English) Zbl 1302.05096
Summary: We prove that a graph admits a strongly 2-connected orientation if and only if it is 4-edge-connected, and every vertex-deleted subgraph is 2-edge-connected. In particular, every 4-connected graph has such an orientation while no cubic 3-connected graph has such an orientation.

MSC:
05C40 Connectivity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bárat, J.; Kriesell, M., What is on his mind?, Discrete Math., 310, 2573-2583, (2010) · Zbl 1208.05003
[2] Berg, A. R.; Jordán, T., Two-connected orientations of Eulerian graphs, J. Graph Theory, 52, 230-242, (2006) · Zbl 1099.05051
[3] Bondy, J. A.; Murty, U. S.R., Graph theory with applications, (1976), The MacMillan Press Ltd. · Zbl 1226.05083
[4] Cheriyan, J.; Durand de Gevigney, O.; Szigeti, Z., Packing of rigid spanning subgraphs and spanning trees, J. Combin. Theory Ser. B, 105, 17-25, (2014) · Zbl 1300.05247
[5] Durand de Gevigney, O., On Frank’s conjecture on k-connected orientations, (Dec. 2012)
[6] Frank, A., Connectivity and network flows, (Handbook of Combinatorics, vol. 1, (1995), Elsevier), 111-177 · Zbl 0846.05055
[7] Gerards, A. M.H., On 2-vertex connected orientations, reference accessed on June 22, 2014
[8] Jordán, T., On the existence of k edge-disjoint 2-connected spanning subgraphs, J. Combin. Theory Ser. B, 95, 257-262, (2005) · Zbl 1075.05050
[9] Lovász, L., On some connectivity properties of Eulerian graphs, Acta Math. Acad. Sci. Hung., 28, 129-138, (1976) · Zbl 0337.05124
[10] Mader, W., A reduction method for edge-connectivity in graphs, Ann. Discrete Math., 3, 145-164, (1978) · Zbl 0389.05042
[11] Mohar, B.; Thomassen, C., Graphs on surfaces, (2001), Johns Hopkins University Press · Zbl 0979.05002
[12] Nash-Williams, C. St. J.A., On orientations, connectivity and odd-vertex-pairings in finite graphs, Canad. J. Math., 12, 555-567, (1960) · Zbl 0096.38002
[13] Robbins, H. E., Questions, discussions, and notes: a theorem on graphs, with an application to a problem of traffic control, Amer. Math. Monthly, 46, 281-283, (1939) · Zbl 0021.35703
[14] Thomassen, C., Configurations in graphs of large minimum degree, connectivity, or chromatic number, (Combinatorial Mathematics: Proceedings of the Third International Conference, New York, 1985, Ann. New York Acad. Sci., vol. 555, (1989)), 402-412
[15] Thomassen, C., The weak 3-flow conjecture and the weak circular flow conjecture, J. Combin. Theory Ser. B, 102, 521-529, (2012) · Zbl 1239.05083
[16] Thomassen, C., Orientations of infinite graphs with prescribed edge-connectivity, Combinatorica, (2014), in press
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.