International audience

The Minimum Semitotal Dominating Set (MSTDS) problem is a classical variant of the Minimum Dominating Set (MDS) problem. Given a graph G = ( V , E ) , the goal is to compute a minimum-cardinality vertex subset D ⊆ V such that (i) D is a dominating set, and (ii) for every vertex u in D has a partner v ∈ D within distance two (the semitotal property ), i.e, dist G ( u , v ) ≤ 2 . While the problem is NP-complete in general graphs, recent work has studied approximation algorithms in special graph classes, including unit disk graphs (UDGs). In this paper, we present a deterministic approximation algorithm for the MSTDS problem on UDGs in the graph-based input model, where the graph is provided explicitly without geometric coordinates. Our algorithm achieves a 5.75-approximation factor, improving upon the previous best 6-approximation due to Rout and Das (2024). The core of our algorithm is a multi-stage strategy that starts with a Maximal Independent Set (MIS) and iteratively satisfies the semitotal property through cost-effective vertex swaps and additions of new vertices to the MIS.

Abstract. The transversal number [Formula: see text] of a hypergraph [Formula: see text] is the minimum number of vertices that intersect every edge of [Formula: see text]. A 6-uniform hypergraph has all edges of size 6. On 10 November 2000 Tuza and Vestergaard [ Discuss. Math. Graph Theory, 22 (2002), pp. 199–210] conjectured that if [Formula: see text] is a 3-regular 6-uniform hypergraph of order [Formula: see text], then [Formula: see text]. In this paper we prove this conjecture, which has become known as the Tuza–Vestergaard conjecture.

The metric dimension of a graph is the minimum size of a set of vertices such that each vertex is uniquely determined by the distances to the vertices of that set. Our aim is to upper-bound the order $n$ of a graph in terms of its diameter $d$ and metric dimension $k$. In general, the bound $n\leq d^k+k$ is known to hold. We prove a bound of the form $n=\mathcal{O}(kd^2)$ for trees and outerplanar graphs (for trees we determine the best possible bound and the corresponding extremal examples). More generally, for graphs having a tree decomposition of width $w$ and length $\ell$, we obtain a bound of the form $n=\mathcal{O}(kd^2(2\ell+1)^{3w+1})$. This implies in particular that $n=\mathcal{O}(kd^{\mathcal{O}(1)})$ for graphs of constant treewidth and $n=\mathcal{O}(f(k)d^2)$ for chordal graphs, where $f$ is a doubly exponential function. Using the notion of distance-VC dimension (introduced in 2014 by Bousquet and Thomassé) as a tool, we prove the bounds $n\leq (dk+1)^{t-1}+1$ for $K_t$-minor-free graphs and $n\leq (dk+1)^{d(3\cdot 2^{r}+2)}+1$ for graphs of rankwidth at most $r$.

The $\frac{3}{4}$-Game Total Domination Conjecture posed by Henning, Klavžar, and Rall [Combinatorica, (2016)] states that if $G$ is a graph on $n$ vertices in which every component contains at least three vertices, then $\gamma_{tg}(G) \le \frac{3}{4}n$, where $\gamma_{tg}(G)$ denotes the game total domination number of $G$. Motivated by this conjecture, we raise the problem to a higher level by introducing a transversal game in hypergraphs. We define the game transversal number, $\tau_g(H)$, of a hypergraph $H$, and prove that if every edge of $H$ has size at least 2, and $H \ncong C_4$, then $\tau_g(H) \le \frac{4}{11}(n_{_H}+m_{_H})$, where $n_{_H}$ and $m_{_H}$ denote the number of vertices and edges, respectively, in $H$. Further, we characterize the hypergraphs achieving equality in this bound. As an application of this result, we prove that if $G$ is a graph on $n$ vertices with minimum degree at least 2, then $\gamma_{{tg}}(G) < \frac{8}{11} n$. As a consequence of this result, the $\frac{3}{4}$-Game Total Domination Conjecture is true over the class of graphs with minimum degree at least 2.

In the domination game on a graph $G$, the players Dominator and Staller alternately select vertices of $G$. Each vertex chosen must strictly increase the number of vertices dominated. This process eventually produces a dominating set of $G$; Dominator aims to minimize the size of this set, while Staller aims to maximize it. The size of the dominating set produced under optimal play is the game domination number of $G$, denoted by $\gamma_g (G)$. In this paper, we prove that $\gamma_g(G) \le 2n/3$ for every $n$-vertex isolate-free graph $G$. When $G$ has minimum degree at least $2$, we prove the stronger bound $\gamma_g(G) \le 3n/5$; this resolves a special case of a conjecture due to Kinnersley, West, and Zamani [SIAM J. Discrete Math., 27 (2013), pp. 2090--2107]. Finally, we prove that if $G$ is an $n$-vertex isolate-free graph with $\ell$ vertices of degree 1, then $\gamma_g(G) \le 3n/5 + \left \lceil \ell/2 \right \rceil + 1$; in the course of establishing this result, we answer a question of Brešar et al. [Discrete Math., 330 (2014), pp. 1--10].

Let $H = (V,E)$ be a hypergraph with vertex set $V$ and edge set $E$ of order ${n_{_H}} = |V|$ and size ${m_{_H}} = |E|$. The hypergraph $H$ is $k$-uniform if every edge of $H$ has size $k$. Two vertices in $H$ are adjacent if they belong to a common edge in $H$. A transversal in $H$ is a subset of vertices in $H$ that has a nonempty intersection with every edge of $H$. A total transversal in $H$ is a transversal $T$ in $H$ with the additional property that every vertex in $T$ is adjacent to some other vertex of $T$. The total transversal number $\tau_t(H)$ of $H$ is the minimum cardinality of a total transversal in $H$. For $k \ge 2$, let $b_k = \sup_{H \in {\cal H}_k} \, {\tau_t}(H) / ({n_{_H}} + {m_{_H}})$, where ${\cal H}_k$ denotes the class of all $k$-uniform hypergraphs containing no isolated vertices or isolated edges or multiple edges. It is known that $b_2 = 2/5$, $b_3 = 1/3$, $b_4 \le 1/3$, and $b_5 \le 2/7$. In this paper, we show that $b_4 = 2/7$ and $b_6 \le 1/4$. Further, for $k \ge 7$, we show that $b_7 \le 2/9$. These results on total transversals have applications in total domination in hypergraphs. A total dominating set in $H$ is a subset of vertices $D \subseteq V$ such that every vertex in $H$ is adjacent to some vertex in $D$. The total domination number $\gamma_t(H)$ is the minimum cardinality of a total dominating set in $H$. The following relationship between the total transversal number and the total domination number of uniform hypergraphs is known: For $k \ge 3$ and $H \in {\cal H}_k$, we have ${\gamma_t}(H) \le ( \max \{ \frac{2 }{k+1}, b_{k-1} \} ) \times {n_{_H}}$. As a consequence of our results on the total transversal number, for $k \in \{2,3,4,5,6,7,8\}$ and a hypergraph $H \in {\cal H}_k$, we have ${\gamma_t}(H) \le 2{n_{_H}}/(k+1)$.

In this paper, we continue the study of power domination in graphs (see [T. W. Haynes et al., SIAM J. Discrete Math., 15 (2002), pp. 519--529; P. Dorbec et al., SIAM J. Discrete Math., 22 (2008), pp. 554--567; A. Aazami et al., SIAM J. Discrete Math., 23 (2009), pp. 1382--1399]). Power domination in graphs was birthed from the problem of monitoring an electric power system by placing as few measurement devices in the system as possible. A set of vertices is defined to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set following a set of rules (according to Kirschoff laws) for power system monitoring. The minimum cardinality of a power dominating set of a graph is its power domination number. We show that the power domination of a connected cubic graph on $n$ vertices different from $K_{3,3}$ is at most $n/4$ and this bound is tight. More generally, we show that for $k \ge 1$, the $k$-power domination number of a connected $(k+2)$-regular graph on $n$ vertices different from $K_{k+2,k+2}$ is at most $n/(k+3)$, where the $1$-power domination number is the ordinary power domination number. We show that these bounds are tight.

Thomassen [Combinatorica, 3 (1983), pp. 393–396] proved that every digraph with minimum out-degree at least three has two vertex disjoint cycles. There are examples of 3-regular digraphs where all pairs of vertex disjoint cycles have the same length. In this paper we raise the conjectures that all 3-regular bipartite digraphs and all digraphs with minimum degree at least four have two vertex disjoint cycles of different length. We give support for our conjectures by proving that all 4-regular digraphs do indeed have two vertex disjoint cycles of different length. We furthermore discuss consequences of our results and conjectures as well as arc-weighted versions of our conjecture.

Let H be a 3-uniform hypergraph of order n and size m, and let T be a subset of vertices of H. The set T is a strong transversal in H if T contains at least two vertices from every edge of H. The strong transversal number $\tau_s(H)$ of H is the minimum size of a strong transversal in H. We show that $7\tau_s(H)\leq4n+2m$, and we characterize the hypergraphs that achieve equality in this bound. In particular, we show that the Fano plane is the only connected 3-uniform hypergraph H of order $n\geq6$ and size m that achieves equality in this bound. A set S of vertices in a graph G is a double total dominating set of G if every vertex of G is adjacent to at least two vertices in S. The minimum cardinality of a double total dominating set of G is the double total domination number $\gamma_{\times2,t}(G)$ of G. Let G be a connected graph of order n with minimum degree at least three. As an application of our hypergraph results, we show that $\gamma_{\times2,t}(G)\leq6n/7$ with equality if and only if G is the Heawood graph (equivalently, the incidence bipartite graph of the Fano plane). Further if G is not the Heawood graph, we show that $\gamma_{\times2,t}(G)\leq11n/13$, while if G is a cubic graph different from the Heawood graph, we show that $\gamma_{\times2,t}(G)\leq5n/6$, and this bound is sharp.

The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known vertex covering and dominating set problems in graphs. We consider the graph theoretical representation of this problem as a variation of the dominating set problem and define a set S to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S (following a set of rules for power system monitoring). The minimum cardinality of a power dominating set of a graph G is the power domination number $\gamma_P(G)$. We show that the power dominating set (PDS) problem is NP-complete even when restricted to bipartite graphs or chordal graphs. On the other hand, we give a linear algorithm to solve the PDS for trees. In addition, we investigate theoretical properties of $\gamma_P(T)$ in trees T.

For a vertex v and a (k − 1)-element subset P of vertices of a graph, one can define the distance from v to P in various ways, including the minimum, average, and maximum distance from v to P. Associated with each of these distances, one can define the k-eccentricity of the vertex v as the maximum distance over all P and the k-eccentricity of the set P as the maximum distance over all v. If k = 2, one is back with the normal eccentricity. We study here the properties of these eccentricity measures, especially bounds on the associated radius (minimum k-eccentricity) and diameter (maximum k-eccentricity). © 1999 John Wiley & Sons, Inc. Networks 34: 312–319, 1999