Efficient edge domination in regular graphs. (English) Zbl 1210.05094
Summary: An induced matching of a graph \(G\) is a matching having no two edges joined by an edge. An efficient edge dominating set of \(G\) is an induced matching \(M\) such that every other edge of \(G\) is adjacent to some edge in \(M\). We relate maximum induced matchings and efficient edge dominating sets, showing that efficient edge dominating sets are maximum induced matchings, and that maximum induced matchings on regular graphs with efficient edge dominating sets are efficient edge dominating sets. A necessary condition for the existence of efficient edge dominating sets in terms of spectra of graphs is established. We also prove that, for arbitrary fixed \(p\geq 3\), deciding on the existence of efficient edge dominating sets on \(p\)-regular graphs is NP-complete.
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
Keywords:
induced matchings; domination in graphs; regular graphs; spectra of graphs; NP-completenessReferences:
| [1] | Cameron, K., Induced matchings, Discrete Appl. Math., 24, 97-102 (1989) · Zbl 0687.05033 |
| [2] | Cameron, K., Induced matchings in intersection graphs, Discrete Math., 278, 1-9 (2004) · Zbl 1033.05080 |
| [3] | Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of Graphs - Theory and Application (1979), Academic Press: Academic Press New York |
| [4] | Duckworth, W.; Manlove, D.; Zito, M., On the approximability of the maximum induced matching problem, J. Discrete Algorithms, 3, 79-91 (2005) · Zbl 1075.68063 |
| [5] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP Completeness (1979), W.H. Freeman & Company: W.H. Freeman & Company San Francisco · Zbl 0411.68039 |
| [6] | Golumbic, M. C.; Lewenstein, M., New results on induced matchings, Discrete Appl. Math., 101, 157-165 (2000) · Zbl 0951.68104 |
| [7] | Gregory, D. A.; Watts, V. L.; Shader, B. L., Biclique decompositions and Hermitian rank, Linear Algebra Appl., 292, 267-280 (1999) · Zbl 0929.05056 |
| [8] | Grinstead, D. L.; Slater, P. J.; Sherwani, N. A.; Holmes, N. D., Efficient edge domination problems in graphs, Inform. Process. Lett., 48, 221-228 (1993) · Zbl 0797.05076 |
| [9] | (Gross, J. L.; Yellen, J., Handbook of Graph Theory (2004), CRC Press: CRC Press Boca Raton) · Zbl 1036.05001 |
| [10] | Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of Domination in Graphs (1998), Marcel Dekker: Marcel Dekker New York · Zbl 0890.05002 |
| [11] | Kratochvíl, J., Regular codes in regular graphs are difficult, Discrete Math., 133, 191-205 (1994) · Zbl 0821.68096 |
| [12] | C.W. Ko, F.B. Shepherd, Adding an identity to a totally unimodular matrix, LSE Operations Research Working Paper LSEOR.94.12, 1994; C.W. Ko, F.B. Shepherd, Adding an identity to a totally unimodular matrix, LSE Operations Research Working Paper LSEOR.94.12, 1994 |
| [13] | Kobler, D.; Rotics, U., Finding maximum induced matching in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size, Algorithmica, 37, 327-346 (2003) · Zbl 1082.68592 |
| [14] | Lu, C. L.; Ko, M-T.; Tang, C. Y., Perfect edge domination and efficient edge domination in graphs, Discrete Appl. Math., 119, 227-250 (2002) · Zbl 0995.05108 |
| [15] | Lu, C. L.; Tang, C. Y., Solving the weighted efficient edge domination problem on bipartite permutation graphs, Discrete Appl. Math., 87, 203-211 (1998) · Zbl 0911.05039 |
| [16] | Read, R. C.; Wilson, R. J., An Atlas of Graphs (2005), Oxford University Press |
| [17] | Stockmeyer, L. J.; Vazirani, V. V., NP-completeness of some generalizations of the maximum matching problem, Inform. Process. Lett., 15, 14-19 (1982) · Zbl 0493.68039 |
| [18] | Thompson, D. M., Eigengraphs: Constructing strongly regular graphs with block designs, Utilitas Math., 20, 83-115 (1981) · Zbl 0494.05043 |
| [19] | Zito, M., Induced matchings in regular graphs and trees, (Proceedings of the 25th International Workshop on Graph Theoretic Concepts in Computer Science. Proceedings of the 25th International Workshop on Graph Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 1665 (1999), Springer: Springer Berlin), 89-100 · Zbl 0941.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. 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.
