Search

Let d-claw (or d-star) stand for K 1 , d , the complete bipartite graph with 1 and d ≥ 1 vertices on each part. The d-claw vertex deletion problem, d -claw-vd, asks for a given graph G and an integer k if one can delete at most k vertices from G such that the resulting graph has no d-claw as an induced subgraph. Thus, 1 -claw-vd and 2 -claw-vd are just the famous vertex cover problem and the cluster vertex deletion problem, respectively. In this paper, we strengthen a hardness result recently proved in Jena and Subramani (in: Du, Du, Wu, and Zhu (eds) Theory and applications of models of computation - 17th annual conference, TAMC 2022, Tianjin, China, September 16–18, 2022, Proceedings, 2022), by showing that cluster vertex deletion remains NP -complete even when restricted to planar bipartite graphs of maximum degree 3 and arbitrary large girth. Moreover, for every d ≥ 3 , we show that d -claw-vd is NP -complete even when restricted to planar bipartite graphs of maximum degree d. These hardness results are optimal with respect to degree constraint. By extending the hardness result in Bonomo-Braberman et al (in: Computing and combinatorics - 26th international conference, COCOON 2020, Proceedings, Lecture Notes in Computer Science, vol 12273, Springer, 2020, pp 14–26, 2020), we show that, for every d ≥ 3 , d -claw-vd is NP -complete even when restricted to split graphs without (d + 1) -claws, and split graphs of diameter 2. On the positive side, we prove that d -claw-vd is polynomially solvable on what we call d-block graphs, a class properly contains all block graphs. This result extends the polynomial-time algorithm in Cao et al (Theor Comput Sci, 2018) for 2 -claw-vd on block graphs to d -claw-vd for all d ≥ 2 and improves the polynomial-time algorithm proposed by Bonomo-Brabeman et al. for (unweighted) 3 -claw-vd on block graphs to 3-block graphs. [ABSTRACT FROM AUTHOR]

In a graph, a matching cut is an edge cut that is a matching. Matching Cut is the problem of deciding whether or not a given graph has a matching cut, which is known to be NP -complete. While Matching Cut is trivial for graphs with minimum degree at most one, it is NP -complete on graphs with minimum degree two. In this paper, we show that, for any given constant c > 1 , Matching Cut is NP -complete in the class of graphs with minimum degree c and this restriction of Matching Cut has no subexponential-time algorithm in the number of vertices unless the Exponential-Time Hypothesis fails. We also show that, for any given constant ϵ > 0 , Matching Cut remains NP -complete in the class of n-vertex (bipartite) graphs with unbounded minimum degree δ > n 1 - ϵ . We give an exact branching algorithm to solve Matching Cut for graphs with minimum degree δ ≥ 3 in O ∗ (λ n) time, where λ is the positive root of the polynomial x δ + 1 - x δ - 1 . Despite the hardness results, this is a very fast exact exponential-time algorithm for Matching Cut on graphs with large minimum degree; for instance, the running time is O ∗ (1. 0099 n) on graphs with minimum degree δ ≥ 469 . Complementing our hardness results, we show that, for any two fixed constants 1 < c < 4 and c ′ ≥ 0 , Matching Cut is solvable in polynomial time for graphs with large minimum degree δ ≥ 1 c n - c ′ . [ABSTRACT FROM AUTHOR]

Abstract: For a given graph , the interval completion problem of G is to find an edge set F such that the supergraph of G is an interval graph and is minimum. It has been shown that it is equivalent to the minimum sum cut problem, the profile minimization problem and a kind of graph searching problems. Furthermore, it has applications in computational biology, archaeology, and clone fingerprinting. In this paper, we show that it is NP-complete on split graphs and propose an efficient algorithm on primitive starlike graphs. [Copyright &y& Elsevier]

Abstract: Given a class of graphs , a graph is a probe graph of if its vertices can be partitioned into two sets, , the probes, and an independent set , the nonprobes, such that can be embedded into a graph of by adding edges between certain vertices of . If the partition of the vertices into probes and nonprobes is part of the input, then we call the graph a partitioned probe graph of . In this paper, we provide a recognition algorithm for partitioned probe permutation graphs with time complexity , where is the number of vertices of the input graph. We show that a probe permutation graph has at most minimal separators. As a consequence, for probe permutation graphs there exist polynomial-time algorithms solving problems like treewidth and minimum fill-in. We also characterize those graphs for which the probe graphs must be weakly chordal. [Copyright &y& Elsevier]

Abstract: A Roman dominating function of a graph is a function such that every vertex with is adjacent to at least one vertex with . The weight of a Roman dominating function is defined to be , and the minimum weight of a Roman dominating function on a graph is called the Roman domination number of . In this paper we first answer an open question mentioned in [E.J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi, S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11–22] by showing that the Roman domination number of an interval graph can be computed in linear time. We then show that the Roman domination number of a cograph (and a graph with bounded cliquewidth) can be computed in linear time. As a by-product, we give a characterization of Roman cographs. It leads to a linear-time algorithm for recognizing Roman cographs. Finally, we show that there are polynomial-time algorithms for computing the Roman domination numbers of -free graphs and graphs with a -octopus. [Copyright &y& Elsevier]