ABSTRACT. Let $G=(V,E)$ be a graph. A set $D \subseteq V$ is a dominating set if every vertex in $V \setminus D$ has a neighbor in $D$. The domination number $\gamma(G)$ is the minimum cardinality of a dominating set. The \emph{bondage number} of a graph $G$ is the minimum number of edges whose removal increases $\gamma(G)$, while the \emph{reinforcement number} is the minimum number of edges whose addition decreases $\gamma(G)$. Hu and Xu initiated the complexity study of the \textsc{Bondage} and \textsc{Reinforcement} problems, establishing NP-hardness for general graphs (J.\ Complexity, 2012). Subsequently, Hu and Sohn strengthened these NP-hardness results for bipartite graphs (Theoret.\ Comput.\ Sci., 2014). The complexity of these problems on chordal graphs has remained unexplored. Hu and Xu asked whether these problems belong to NP and whether they admit polynomial-time approximation algorithms with small performance ratios.\\~ \quad In this paper, we prove that the \textsc{Bondage} and \textsc{Reinforcement} problems are NP-hard and coNP-hard for $k = 1$, even when restricted to split graphs, a well-known subclass of chordal graphs. Consequently, unless $\mathrm{NP} = \mathrm{coNP}$, none of these problems is in NP, answering the first question. Furthermore, these hardness results rule out any polynomial-time approximation algorithm with performance ratio better than~$2$, unless $\mathrm{P} = \mathrm{NP}$, thereby answering second question.

ABSTRACT. A monitoring edge-geodetic set (or meg-set for short) of a graph is a set of vertices M such that if any edge is removed, then the distance between some two vertices of M increases. This notion was introduced by Foucaud et al. in 2023 as a way to monitor networks for communication failures. As computing a minimal meg-set is hard in general, recent works aimed to find polynomial-time algorithms to compute minimal meg-sets when the input belongs to a restricted class of graphs. Most of these results are based on the property of some classes of graphs to admit a unique minimum meg-set, which is then easy to compute. In this work, we prove that chordal graphs also admit a unique minimal meg-set, answering a standing open question of Foucaud et al.

ABSTRACT. The Maximum Matching realization problem requires, for a sequence $d$ of $n$ positive integers, to compute a realizing graph (whose degree sequence corresponds to $d$) with the largest possible matching. We present a polynomial time algorithm for this problem.

ABSTRACT. Vertex splitting is a graph modification operation in which a vertex is replaced by multiple vertices such that the union of their neighborhoods equals the neighborhood of the original vertex. We study vertex splitting as a graph modification operation for transforming graphs into interval graphs. Given a graph G and an integer k, we consider the problem of deciding whether G can be transformed into an interval graph using at most k vertex splits. We prove that this problem is NP-hard. We further observe that vertex splitting differs fundamentally from vertex deletion as a graph modification operation. On the positive side, we identify tractable cases. We give polynomial-time algorithms for transforming graphs into trees using vertex splitting and show that deciding whether a graph can be split into a disjoint union of paths is also solvable in polynomial time.

ABSTRACT. We study a natural generalization of the classical \textsc{Dominating Set} problem, called \textsc{Dominating Set with Quotas} (DSQ). In this problem, we are given a graph \( G \), an integer \( k \), and for each vertex \( v \in V(G) \), a lower quota \( \mathrm{lo}_v \) and an upper quota \( \mathrm{up}_v \). The goal is to determine whether there exists a set \( S \subseteq V(G) \) of size at most \( k \) such that for every vertex \( v \in V(G) \), the number of vertices in its closed neighborhood that belong to \( S \), i.e., \( |N[v] \cap S| \), lies within the range \( [\mathrm{lo}_v, \mathrm{up}_v] \). This richer model captures a variety of practical settings where both under- and over-coverage must be avoided—such as in fault-tolerant infrastructure, load-balanced facility placement, or constrained communication networks.

While DS is already known to be computationally hard, we show that the added expressiveness of per-vertex quotas in DSQ introduces additional algorithmic challenges. In particular, we prove that DSQ becomes \W[1]-hard even on structurally sparse graphs—such as those with degeneracy 2, or excluding \( K_{3,3} \) as a subgraph—despite these classes admitting FPT algorithms for DS. On the positive side, we show that DSQ is fixed-parameter tractable when parameterized by solution size and treewidth, and more generally, on nowhere dense graph classes. Furthermore, we design a subexponential-time algorithm for DSQ on apex-minor-free graphs using the bidimensionality framework. These results collectively offer a refined view of the algorithmic landscape of DSQ, revealing a sharp contrast with the classical DS problem and identifying the key structural properties that govern tractability.

ABSTRACT. Graph convexities have been widely investigated through combinatorial parameters that capture different aspects of convexity-related structures. In the cycle convexity, the interval $\icc(S)$ of a subset $S$ of vertices of a graph $G=(V,E)$ is the set of all vertices in $S$ union the vertices with two neighbors in a same connected component of $G[S]$. The hull of $S$ is the closure $\h(S)=\icc^{*}(S)$. The general position number of $G$ is the maximum size of a set $S$ such that $v \notin \icc(S \setminus \{v\})$ for every $v \in S\subseteq V(G)$, and the rank of $G$ is the maximum size of a set $S$ such that $v \notin \h(S \setminus \{v\})$ for every $v \in S\subseteq V(G)$.

Here, we first show that the general position number of $G$ equals the maximum order of an induced forest in $G$. Then, we focus on the computational complexity of computing the rank of $G$. We show that it is $\NP$-hard, even if the input graph is known to be bipartite, and $\W[1]$-hard parameterized by the size of the solution. Then, we prove that it is polynomial-time computable in various graph classes such as forests, cycles, complete graphs, complete bipartite graphs, cographs, Cartesian grids, chordal graphs, starlike graphs, and~$(q,q-4)$-graphs. Surprisingly, the cases of the classes of Cartesian grids and of not 2-connected chordal graphs are quite involved. We conclude by presenting fixed-parameter tractable algorithms for computing the rank of a given graph when parameterized by the neighborhood diversity, by vertex cover, or by the treewidth of the input graph.

ABSTRACT. Given a graph $G = (V, E)$, a signed dominating function is a function $f: V \rightarrow \{-1, 1\}$ such that for every vertex $u \in V$, $\sum\limits_{v \in N[u]} f(v) \geq 1$. The weight of $f$ is defined as $\sum\limits_{u \in V} f(u)$. The objective of the \sd{} problem is to compute a signed dominating function $f$ of minimum weight. The problem is known to be NP-complete even when restricted to bipartite, chordal, and planar graphs. In this paper, we extend the known complexity results for the \sd{} problem. Since the problem is NP-complete on chordal graphs, we study its complexity on split graphs, a subclass of chordal graphs, and show that it remains NP-complete. Moreover, as the problem is W[2]-hard parameterized by weight, we investigate its parameterized complexity with respect to structural parameters. We prove that the problem is W[1]-hard when parameterized by feedback vertex set number (and hence by treewidth and clique-width). Motivated by this hardness result, we consider a more restrictive parameter, neighbourhood diversity, and present an FPT algorithm.