Loose cover of graphs. (English) Zbl 1205.05219
Summary: This paper introduces a new definition of embedding a local structure to a given network, called loose cover of graphs. We derive several basic properties on the notion of loose cover, which includes transitivity, maximality, and the computational complexity of finding a loose cover by paths and cycles. In particular, we show that the decision problem is in P if the given local structure is a path with three or less vertices, while it is NP-complete for paths consisting of six or more vertices.
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C38 | Paths and cycles |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
References:
| [1] | Bertossi A.A.: On the domatic number of interval graphs. Inf. Process. Lett. 28(6), 275–280 (1988) · Zbl 0658.68077 · doi:10.1016/0020-0190(88)90173-1 |
| [2] | Bonuccelli M.A.: Dominating sets and domatic number of circular arc graphs. Discret. Appl. Math. 12, 203–213 (1985) · Zbl 0579.05051 · doi:10.1016/0166-218X(85)90025-3 |
| [3] | Fujita S., Yamashita M., Kameda T.: A study of r-configurations–a resource assignment problem on graphs. SIAM J. Discret. Math. 13(2), 227–254 (2000) · Zbl 0941.05050 · doi:10.1137/S0895480196311328 |
| [4] | Haynes T.W., Hedetniemi S.T., Slater P.J.: Fundamentals of Domination in Graphs. Marcel Dekker, Inc., New York (1998) · Zbl 0890.05002 |
| [5] | Haynes T.W., Hedetniemi S.T., Slater P.J.: Domination in Graphs: Advanced Topics. Marcel Dekker, Inc., New York (1998) · Zbl 0883.00011 |
| [6] | Kratochvil J., Proskurowski A., Telle J.: Covering regular graphs. J. Comb. Theory B 71(1), 1–16 (1997) · Zbl 0895.05049 · doi:10.1006/jctb.1996.1743 |
| [7] | Kratochvil J., Proskurowski A., Telle J.: Complexity of graph covering problems. Nord. J. Comput. 5(3), 173–195 (1998) · Zbl 0911.68076 |
| [8] | Lu T.L., Ho P.H., Chang G.J.: The domatic number problem in interval graphs. SIAM J. Discret. Math. 3, 531–536 (1990) · Zbl 0718.05046 · doi:10.1137/0403045 |
| [9] | Manacher G.K., Mankus T.A.: Finding a domatic partition of an interval graph in time O(n). SIAM J. Discret. Math. 9(2), 167–172 (1996) · Zbl 0846.68048 · doi:10.1137/0409015 |
| [10] | Peng S.L., Chang M.S.: A simple linear time algorithm for the domatic partition problem on strongly chordal graphs. Inf. Process. Lett. 43, 297–300 (1992) · Zbl 0768.68169 · doi:10.1016/0020-0190(92)90115-C |
| [11] | Srinivasa Rao A., Rangan C.P.: Linear algorithm for domatic number problem on interval graphs. Inf. Process. Lett. 33(1), 29–33 (1989) · Zbl 0685.68062 · doi:10.1016/0020-0190(89)90184-1 |
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.
