Affiliations: [a] Department of Technical Physics and Applied Mathematics, Gdansk University of Technology, ul. Narutowicza 11/12 80-233 Gdansk, Poland. [email protected] | [b] Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Av. Països Catalans 26, 43007 Tarragona, Spain. [email protected] | [c] Interdisciplinary Centre for Security, Reliability and Trust (SnT), University of Luxembourg, Luxemburg. [email protected]
Correspondence:
[*]
Address for correspondence: Department of Technical Physics and Applied Mathematics, Gdansk University of Technology, ul. Narutowicza 11/12 80-233 Gdansk, Poland.
Abstract: 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]w = (N[D], Ew) weakly induced by D, is connected, where Ew is the set of all edges having at least one vertex in D. The weakly connected domination number γw(G) of G is the minimum cardinality among all weakly connected dominating sets of G. In this article we characterize the graphs where γw(G) = τ(G). In particular, we focus our attention on bipartite graphs, regular graphs, unicyclic graphs, block graphs and corona graphs.
Keywords: Vertex cover number, weakly connected domination number
