Similarities and Differences Between the Vertex Cover Number and the Weakly Connected Domination Number of a Graph

• Autorzy: Lemańska M. , Rodríguez-Velázquez J. A. , Trujillo-Rasua R.

Identyfikatory

DOI

10.3233/FI-2017-1520

• Języki publikacji: EN

Abstrakty

EN

A vertex cover of a graph G = (V, E) is a set X ⊂ V such that each edge of G is incident to at least one vertex of X. The vertex cover number τ(G) is the minimum cardinality of a vertex cover of G. A dominating set D ⊆ V is a weakly connected dominating set of G if the subgraph G[D]_ω = (N[D], E_ω) weakly induced by D, is connected, where E_ω is the set of all edges having at least one vertex in D. The weakly connected domination number γ_ω(G) of G is the minimum cardinality among all weakly connected dominating sets of G. In this article we characterize the graphs where γ_ω(G) = τ(G). In particular, we focus our attention on bipartite graphs, regular graphs, unicyclic graphs, block graphs and corona graphs.

Słowa kluczowe

EN

vertex cover number; weakly connected domination number

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 152, nr 3
• Strony: 273--287
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Lemańska M.

• Department of Technical Physics and Applied Mathematics, Gdansk University of Technology, ul. Narutowicza 11/12, 80-233 Gdansk, Poland

autor

Rodríguez-Velázquez J. A.

• Departament d'Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Av. Països Catalans 26, 43007 Tarragona, Spain

autor

Trujillo-Rasua R.

• Interdisciplinary Centre for Security, Reliability and Trust (SnT), University of Luxembourg, Luxemburg

Bibliografia

• [1] Chen YZ, Liestman AL. Approximating minimum size weakly connected dominating sets for clustering mobile ad hoc networks, Proceedings of the Third ACM International Symposium on MobileAd Hoc Networking and Computing (MobiHoc’2002), 2002, pp. 157–164. doi:10.1145/513800.513821.
• [2] Dunbar J, Grossman J, Hattingh J, Hedetniemi ST, McRae A. On weakly connected domination in graphs, Discrete Mathematics, 1997;167-168:261–269. URL http://dx.doi.org/10.1016/S0012-365X(96)00233-6.
• [3] Downey RG, and Fellows MR. Fixed parameter tractability and completeness II: completeness for W[1], Theoretical Computer Science, 1995;141(1-2):109–131. URL http://dx.doi.org/10.1016/0304-3975(94)00097-3.
• [4] Harary F, Hayes JP, and Wu H. A survey of the theory of hypercube graphs. Computers &Mathematics with Applications, 1988;15(4):277–289. URL http://dx.doi.org/10.1016/0898-1221(88)90213-1.
• [5] Levitin A. Introduction to the Design and Analysis of Algorithms. Addison Wesley, 2006. ISBN:0321358287.
• [6] Pirzada S, Dharwadker A. Applications of Graph Theory, Journal of the Korean Society for industrial and applied mathematics, 2007;11(4):19–38. doi:10.1002/pamm.200700981.
• [7] Rajaraman R. Topology control and routing in ad hoc networks: a survey, SIGACT News, 2002;33(2):60–73. doi:10.1145/564585.564602.
• [8] Wu J, Li H. On calculating connected dominating set for efficient routing in ad hoc wireless networks, Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, ACM, 1999, pp. 7–14. doi:10.1145/313239.313261.
• [9] Wu J. Extended Dominating-Set-Based Routing in Ad Hoc Wireless Networks with Unidirectional Links, IEEE Trans. Parallel and Distributed Systems, 2002;13(9):866–881. doi:10.1109/TPDS.2002.1036062.
• [10] Wu J, Dai F. An Extended Localized Algorithm for Connected Dominating Set Formation in Ad Hoc Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, 2004;15(10):908–920. doi:10.1109/TPDS.2004.48.
• [11] Xu X, and Ma J. An efficient simulated annealing algorithm for the minimum vertex cover problem, Neurocomputing, 2006;69(7-9):913–916. URL http://dx.doi.org/10.1016/j.neucom.2005.12.016.