NP-completeness of some problems of partitioning and covering in graphs. (English) Zbl 0541.05048

Péroche, B.

Discrete Appl. Math. 8, 195-208 (1984).

The author proves that the following problems are NP-complete: 1) Given a non-symmetric digraph G such that \(d^+(x)=d^-(x)=2\) for all \(x\in V(G)\), can A(X) be partitioned into two Hamilton circuits? 2) Given a digraph G such that \(d^+(x)=d^-(x)=2\) for all \(x\in V(G)\), can A(X) be partitioned into two anti-directed Hamilton circuits? 3) Let G be a graph with maximum degree 4. Can E(G) be partitioned into two paths? Can E(G) be covered by two paths? 4) Let G be a digraph such that \(d^+(x)\leq 2\) and \(d^-(x)\leq 2\) for all \(x\in V(G)\). Can A(X) be partitioned into two paths? Can A(X) be partitioned into two anti- directed paths? Can A(X) be covered by two paths?

Reviewer: B.Alspach

MSC:

05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C45	Eulerian and Hamiltonian graphs
68Q25	Analysis of algorithms and problem complexity
05C20	Directed graphs (digraphs), tournaments

Keywords:

NP-complete; Hamilton decompositions; path decompositions; path coverings

References:

[1]	Alspach, B.; Pullman, N. J., Path decompositions of digraphs, Bull. Austral. Math. Soc., 10, 421-427 (1974) · Zbl 0273.05117
[2]	Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029
[3]	G. Chaty and M. Chein, Bases de chemins et indices de recouvrements dans les graphes sans circuit, Colloque sur la Théorie des Graphes, Cahiers Centre Études Rech. Opér. 15 (3) 287-307.; G. Chaty and M. Chein, Bases de chemins et indices de recouvrements dans les graphes sans circuit, Colloque sur la Théorie des Graphes, Cahiers Centre Études Rech. Opér. 15 (3) 287-307. · Zbl 0273.05116
[4]	Frye, W.; Laskar, R., Some results on path-numbers of some digraphs, Proc. 10th S.E. Conf. on Combinatorics, Graph Theory and Computing, 651-666 (1979) · Zbl 0433.05031
[5]	Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[6]	Harary, F., Covering and packing in graphs, I, Ann. N.Y. Acad. Sci., 175, 198-205 (1970) · Zbl 0226.05119
[7]	Harary, F.; Schwenk, J., Covering and Packing in graphs II, (Read, R. C., Graph Theory and Computing (1972), Academic Press: Academic Press New York) · Zbl 0256.05115
[8]	O’Brien, R. C., An upper bound on the path-number of a digraph, Proc. 6th S.E. Conf. on Combinatorics, Graph theory and Computing (1975)
[9]	Péroche, B., The path-numbers of some multi-partite graphs, Annals Discrete Maths., 9, 195-197 (1980) · Zbl 0446.05030
[10]	Puech, C., Thèse 3eme cycle, VI (1977), Paris
[11]	Stanton, R.; Cowan, D. D.; James, L. O., Some results on path-numbers, Proc. of the Louisiana Conf. on Combinatorics, Graph Theory and Computing, 112-135 (1970) · Zbl 0223.05120