×

zbMATH — the first resource for mathematics

Even cycles in directed graphs. (English) Zbl 0606.05039
In this article the author shows that given an edge e in a digraph G it is NP-complete to decide if D has an odd cycle through e and it is NP- complete to decide if D has an even cycle through e. Contiuing his investigation of even cycles in digraphs, he shows that for every natural number k, there exists a digraph \(D_ k\) with no even cycle such that every vertex of \(D_ k\) has outdegree k (settling problems of Lovasz and Seymour). Furthermore, he proves that a digraph of order n and minimum outdegree \([\log_ 2n]+1\) contains, for each edge set E, a cycle containing an even number of edges of E, and this bound is best possible.
Reviewer: L.Lesniak

MSC:
05C38 Paths and cycles
05C20 Directed graphs (digraphs), tournaments
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Behzad, M.; Chartrand, G.; Wall, C.E., On minimal regular digraphs with given girth, Fund. math., 69, 227-231, (1970) · Zbl 0203.26502
[2] Bermond, J.C.; Thomassen, C., Cycles in digraphs-a survey, J. graph theory, 5, 1-43, (1981) · Zbl 0458.05035
[3] Edmonds, J., Paths, Trees, and flowers, canad. J. math., 17, 449-467, (1965) · Zbl 0132.20903
[4] Fortune, S.; Hopcroft, J.; Wyllie, J., The directed subgraph homeomorphism problem, Theoretical computer sci., 10, 111-121, (1980) · Zbl 0419.05028
[5] Hamidoune, Y.O., An application of connectivity theory in graphs to factorizations of elements in groups, Europ. J. combinatorics, 2, 349-355, (1981) · Zbl 0473.05032
[6] Harary, F.; Norman, R.Z.; Cartwright, D., Structural models, an introduction to the theory of directed graphs, (1965), John Wiley New York · Zbl 0139.41503
[7] Jung, H.A., Eine verallgemeinerung des n-fachen zusammenhangs fur graphen, Math. ann., 187, 95-103, (1970) · Zbl 0184.27601
[8] Koh, K.M., Even circuits in directed graphs and lovasz’ conjecture, Bull. Malaysian math. soc., 7, 47-52, (1976)
[9] V. Klee, R. Ladner, R. Manber: Signsolvability revisited, J. Linear Algebra and Applications (to appear). · Zbl 0543.15016
[10] Larman, D.G.; Mani, P., On the existence on certain configurations within graphs and the 1-skeletons of polytopes, Proc. London math. soc., 20, 144-160, (1970) · Zbl 0201.56801
[11] Lovasz, L., Problem 2, (), 1975
[12] Lovasz, L., Coverings and colorings in hypergraphs, (), 3-12
[13] Mader, W., Homomorphieeigenschaften and mittlere kantendichte von graphen, Math. ann., 174, 265-268, (1967) · Zbl 0171.22405
[14] Mader, W., Grad and lokal zusammenhang in endlichen graphen, Math. ann., 205, 9-11, (1973) · Zbl 0245.05119
[15] Seymour, P.D., Dissertation, (1973), University of Oxford
[16] Seymour, P.D., On the two-colouring of hypergraphs, Quart. J. math. Oxford, 25, 303-312, (1974) · Zbl 0299.05122
[17] Thomassen, C., Graph decomposition with applications to subdivisions and path systems modulo k, J. graph theory, 7, 261-271, (1983) · Zbl 0515.05052
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.