Circuit decompositions and shortest circuit coverings of hypergraphs. (English) Zbl 1392.05084
It is one of fundamental theorems in graph theory that every even graph has a circuit decomposition. This classical result for ordinary graphs is extended in this paper for uniform bridgeless hypergraphs if the degree of every vertex is even.
One of the major open problems for the shortest circuit cover was a conjecture proposed by A. Itai and M. Rodeh [Lect. Notes Comput. Sci. 62, 289–299 (1978; Zbl 0386.05047)] that every bridgeless graph \(G=(V,E)\) has a circuit cover of total length at most \(|E|+|V|-1\). This conjecture was solved by E. G. Fan and H. Q. Zhang [Acta Phys. Sin. 47, No. 3, 353–362 (1998; Zbl 1202.35187)] for ordinary graphs. In this paper, the authors extend this result for bridgeless hypergraphs. They prove that if \(\mathcal{H} = (\mathcal{V}, \mathcal{E})\) is a bridgeless hypergraph, then \(\mathcal{H}\) has a circuit cover with total length at most \(|\mathcal{E}|+|\mathcal{V}|-1\).
One of the major open problems for the shortest circuit cover was a conjecture proposed by A. Itai and M. Rodeh [Lect. Notes Comput. Sci. 62, 289–299 (1978; Zbl 0386.05047)] that every bridgeless graph \(G=(V,E)\) has a circuit cover of total length at most \(|E|+|V|-1\). This conjecture was solved by E. G. Fan and H. Q. Zhang [Acta Phys. Sin. 47, No. 3, 353–362 (1998; Zbl 1202.35187)] for ordinary graphs. In this paper, the authors extend this result for bridgeless hypergraphs. They prove that if \(\mathcal{H} = (\mathcal{V}, \mathcal{E})\) is a bridgeless hypergraph, then \(\mathcal{H}\) has a circuit cover with total length at most \(|\mathcal{E}|+|\mathcal{V}|-1\).
Reviewer: Xiaogang Liu (Xi’an)
MSC:
| 05C65 | Hypergraphs |
| 05C45 | Eulerian and Hamiltonian graphs |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05B07 | Triple systems |
References:
| [1] | Alon, N., Tarsi, M.: Covering multigraphs by simple circuits. SIAM J. Algebraic Discrete Methods 6, 345-350 (1985) · Zbl 0581.05046 · doi:10.1137/0606035 |
| [2] | Bahmanian, M.A., Šajna, M.: Quasi-Eulerian Hypergraphs. Electron. J. Comb. 24(3), 3-30 (2017) · Zbl 1369.05153 |
| [3] | Berge, C.: Graphs and Hypergraphs. North-Holland, Amsterdam, London (1973) · Zbl 0254.05101 |
| [4] | Bermond, J.C., Jackson, B., Jaeger, F.: Shortest covering of graphs with cycles. J. Combin. Theory Ser. B 35, 297-308 (1983) · Zbl 0559.05037 · doi:10.1016/0095-8956(83)90056-4 |
| [5] | Bollobas, B., Saito, A., Wormald, N.C.: Regular factors of regular graphs. J. Graph Theory 9, 97-103 (1985) · Zbl 0612.05049 · doi:10.1002/jgt.3190090107 |
| [6] | Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, New York (2008) · Zbl 1134.05001 · doi:10.1007/978-1-84628-970-5 |
| [7] | Fan, G.-H.: Integer flows and cycle covers. J. Combin. Theory Ser. B 54, 113-122 (1992) · Zbl 0776.05084 · doi:10.1016/0095-8956(92)90069-A |
| [8] | Fan, G.-H.: Covering graphs by cycles. SIAM J. Discrete Math. 5, 491-496 (1992) · Zbl 0777.05087 · doi:10.1137/0405039 |
| [9] | Fan, G.-H.: Short cycle covers of cubic graphs. J. Graph Theory 18, 131-141 (1994) · Zbl 0831.05053 · doi:10.1002/jgt.3190180204 |
| [10] | Fan, G.-H., Raspaud, A.: Fulkerson’s conjecture and circuits covers. J. Combin. Theory Ser. B 61, 133-138 (1994) · Zbl 0811.05053 · doi:10.1006/jctb.1994.1039 |
| [11] | Fan, G.-H.: Proofs of two minimum circuit cover conjectures. J. Combin. Theory Ser. B 74, 353-367 (1998) · Zbl 1024.05074 · doi:10.1006/jctb.1998.1854 |
| [12] | Fleischner, H.: Eine gemeinsame Basis für die Theorie der eulerschen Graphen und den Satz von Petersen. Monatsh. Math. 81, 267-278 (1976) · Zbl 0347.05109 · doi:10.1007/BF01387754 |
| [13] | Itai, A., Rodeh, M.: Covering a graph by circuits. In: “Automata, Languages and Programming,” Lecture Notes in Computer Science, Vol. 62, pp. 289-299. Springer, Berlin (1978) · Zbl 0386.05047 |
| [14] | Jaeger, F.: Flows and generalized coloring theorems in graphs. J. Combin. Theory Ser. B 26, 205-216 (1979) · Zbl 0422.05028 · doi:10.1016/0095-8956(79)90057-1 |
| [15] | Jamshy, U., Raspaud, A., Tarsi, M.: Short circuit covers for regular matroids with nowhere-zero \[55\]-flow. J. Combin. Theory Ser. B 43, 354-357 (1987) · Zbl 0659.05038 · doi:10.1016/0095-8956(87)90011-6 |
| [16] | Lonc, Z., Naroski, P.: On tours that contain all edges of a hypergraph. Electron. J. Comb. 17(R144), 1 (2010) · Zbl 1204.05064 |
| [17] | Máčajová, E., Raspaud, A., Tarsi, M., Zhu, X.-D.: Short cycle covers of graphs and nowhere-zero flows. J. Graph Theory 68, 340-348 (2011) · Zbl 1234.05138 · doi:10.1002/jgt.20563 |
| [18] | Máčajová, E., Raspaud, A., Rollová, E., Škoviera, M.: Circuit covers of signed graphs. J. Graph Theory 81, 120-133 (2016) · Zbl 1332.05066 · doi:10.1002/jgt.21866 |
| [19] | Petersen, J.: Die Theorie der regulären Graphs. Acta Math. 15, 193-220 (1891) · JFM 23.0115.03 · doi:10.1007/BF02392606 |
| [20] | Sajna, M.: Eulerian-type properties of hypregraphs (slides) presented at Contributed Minisymposia “Hypergraphs(CM22)”. CanaDAM 2013—Canadian Mathematical Society (2013) · Zbl 0777.05087 |
| [21] | Seymour, P.D.: On multi-colorings of cubic graphs and the conjecture of Fulkerson and Tutte. Proc. Lond. Math. Soc. s3-38, 423-460 (1979) · Zbl 0411.05037 · doi:10.1112/plms/s3-38.3.423 |
| [22] | Szekeres, G.: Polyhedral decompositions of cubic graphs. Bull. Austr. Math. Soc. 8, 367-387 (1973) · Zbl 0249.05111 · doi:10.1017/S0004972700042660 |
| [23] | Tutte, W.T.: Personal correspondence with H. Fleischner (July 22nd, 1987) · Zbl 0347.05109 |
| [24] | West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall, Upper Saddle River (2001) |
| [25] | Zhang, C.-Q.: Circular flows of nearly eulerian graphs and vertex splitting. J. Graph Theory 40, 147-161 (2002) · Zbl 1004.05039 · doi:10.1002/jgt.10040 |
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.
