Given a positive integer @math , a @math -dominating set in a graph @math is a set of vertices such that every vertex not in the set has at least @math neighbors in the set. A total @math -dominating set, also known as a @math -tuple total dominating set, is a set of vertices such that every vertex of the graph has at least @math neighbors in the set. The problems of finding the minimum size of a @math -dominating, resp. total @math -dominating set, in a given graph, are referred to as @math -domination, resp. total @math -domination. These generalizations of the classical domination and total domination problems are known to be NP-hard in the class of chordal graphs, and, more specifically, even in the classes of split graphs (both problems) and undirected path graphs (in the case of total @math -domination). On the other hand, it follows from recent work by (2017) that these two families of problems are solvable in time @math in the class of interval graphs. In this work, we develop faster algorithms for @math -domination and total @math -domination in the class of proper interval graphs. The algorithms run in time @math for each fixed @math and are also applicable to the weighted case.
The works of Liao and Chang @cite_41 and of Lee and Chang @cite_7 consider various domination problems in the class of strongly chordal graphs (and, in the case of @cite_41 , also dually chordal graphs). While the class of strongly chordal graphs generalizes the class of interval graphs, the domination problems studied in @cite_41 @cite_7 all deal with closed neighborhoods, and for those cases structural properties of strongly chordal and dually chordal graphs are helpful for the design of linear-time algorithms. In contrast, @math -domination and total @math -domination are defined via open neighborhoods and results of @cite_41 @cite_7 do not seem to be applicable or easily adaptable to our setting.
@cite_41 @cite_7
2963271448 70941519 2068218174 2065410741
In 2013 Belmonte and Vatshelle used mim-width, a graph parameter bounded on interval graphs and permutation graphs that strictly generalizes clique-width, to explain existing algorithms for many domination-type problems, known as LC-VSVP problems. We focus on chordal graphs and co-comparability graphs, that strictly contain interval graphs and permutation graphs respectively. First, we show that mim-width is unbounded on these classes, thereby settling an open problem from 2012. Then, we introduce two graphs (K_t K_t ) and (K_t S_t ) to restrict these graph classes, obtained from the disjoint union of two cliques of size t, and one clique of size t and one independent set of size t respectively, by adding a perfect matching. We prove that ((K_t S_t) )-free chordal graphs have mim-width at most (t-1 ), and ((K_t K_t) )-free co-comparability graphs have mim-width at most (t-1 ). From this, we obtain several algorithmic consequences, for instance, while Dominating Set is NP-complete on chordal graphs, it can be solved in time ( O (n^ t ) ) on chordal graphs where t is the maximum among induced subgraphs (K_t S_t ) in the given graph. We also show that classes restricted in this way have unbounded rank-width which validates our approach. Introduction (S.T. Hedetniemi, R.C. Laskar). Theoretical. Chessboard Domination Problems (E.J. Cockayne). On the Queen Domination Problem (C.M. Grinstead, B. Hahne, D. Van Stone). Recent Problems and Results About Kernels in Directed Graphs (C. Berge, P. Duchet). Critical Concepts in Domination (D.P. Summer). The Bondage Number of a Graph (J.F. ). Chordal Graphs and Upper Irredundance, Upper Domination and Independence (M.S. Jacobson and K. Peters). Regular Totally Domatically Full Graphs (B. Zelinka). Domatically Critical and Domatically Full Graphs (D. Rall). On Generalised Minimal Domination Parameters for Paths (B. Bollobas, E.J. Cockayne, C.M. Mynhardt). New Models. Dominating Cliques in Graphs (M.B. Cozzens, L.L. Kelleher). Covering all Cliques of Graph (Z. Tuza). Factor Domination in Graphs (R.C. Brigham, R. Dutton). The Least Point Covering and Domination Numbers of a Graph (E. Sampathkumar). Algorithmic. Dominating Sets in Perfect Graphs (D.G. Corneil, L.K. Stewart). Unit Disk Graphs (B.N. Clark, C.J. Colbourn, D.S. Johnson). Permutation Graphs: Connected Domination and Steiner Trees (C.J. Colbourn, L.K. Stewart). The Discipline Number of a Graph (V. Chvatal, W.J. Cook). Best Location of Service Centers in a Tree-Like Network under Budget Constraints (J. McHugh, Y. Perl). Dominating Cycles in Halin Graphs (M. Skowronska, M.M. Syslo). Finding Dominating Cliques Efficiently, in Strongly Chordal Graphs and Undirected Path Graphs (D. Kratsch). On Minimum Dominating Sets with Minimum Intersection (D.L. Grinstead, P.J. Slater). Bibliography. Bibliography on Domination in Graphs and Some Basic Definitions of Domination Parameters (S.T. Hedetniemi, R.C. Laskar). Let Y be a subset of real numbers. A Y-dominating function of a graph G=(V,E) is a function f:V->Y such that @?"u"@?"N"""G"["v"]f(u)>=1 for all vertices [email protected]?V, where N"G[v]= v @? u|(u,v)@?E . Let f(S)[email protected]?"u"@?"Sf(u) for any subset S of V and let f(V) be the weight of f. The Y-domination problem is to find a Y-dominating function of minimum weight for a graph G=(V,E). In this paper, we study the variations of Y-domination such as k -domination, k-tuple domination, signed domination, and minus domination for some classes of graphs. We give formulas to compute the k -domination, k-tuple domination, signed domination, and minus domination numbers of paths, cycles, n-fans, n-wheels, n-pans, and n-suns. Besides, we present a unified approach to these four problems on strongly chordal graphs. Notice that trees, block graphs, interval graphs, and directed path graphs are subclasses of strongly chordal graphs. This paper also gives complexity results for the problems on doubly chordal graphs, dually chordal graphs, bipartite planar graphs, chordal bipartite graphs, and planar graphs. Chordal graphs are graphs with the property that each cycle of length greater than 3 has two non-consecutive vertices that are joined by an edge. An important subclass of chordal graphs are strongly chordal graphs (Farber, 1983). Chordal graphs appear for example in the design of acyclic data base schemes (, 1983). In this paper we study the computational complexity (both sequential and parallel) of the maximum matching problem for chordal and strongly chordal graphs. We show that there is a linear-time greedy algorithm for a maximum matching in a strongly chordal graph provided a strongly perfect elimination ordering is known. This algorithm can also be turned into a parallel algorithm. The technique used can also be extended to the perfect multidimensional matching for chordal and strongly chordal graphs yielding the first polynomial time algorithms for these classes of graphs (the multidimensional matching is NP-complete in general).