Search

An efficiently total dominating set of a graph G is a subset of its vertices such that each vertex of G is adjacent to exactly one vertex of the subset. If there is such a subset, then G is an efficiently total dominable graph (G is etd).In this paper, we prove NP-completeness of the etd decision problem on the class of planar bipartite graphs of maximum degree 3. Furthermore, we give an efficient decision algorithm for T3-free chordal graphs. A T3-free graph is a graph that does not contain as induced subgraph a claw, every edge of which is subdivided exactly twice. In the main part, we present three graph classes on which the weighted etd problem is polynomially solvable: claw-free graphs, odd-sun-free chordal graphs (including strongly chordal graphs) and graphs which only induce cycles of length divisible by four (including chordal bipartite graphs). In addition, claw-free etd graphs are shown to be perfect.

XSAT and NAE-SAT are important variants of the propositional satisfiability problem (SAT). XSAT contains all CNF formulas that can be satisfied by setting exactly one literal in each clause to 1, whereas NAE-SAT requires satisfying truth assignments not setting all literals equally in any clause. Both variants are studied here regarding their computational complexity of linear CNF formulas, whose clauses are allowed to have at most one variable in common. We prove that both variants remain NP-complete for (monotone) linear formulas, yielding the conclusion that also bicolorability of linear hypergraphs is NP-complete. The reduction used gives rise to the complexity investigations of several monotone linear subclasses of both variants that are parameterized by the size of clauses, or by the number of occurrences of variables. For particular values of those parameters, we are able to show the NP-completeness of XSAT and NAE-SAT, though we cannot provide a complete treatment. Finally, we focus on exact linear formulas, where clauses intersect pairwise, and for which SAT is known to be polynomial-time solvable. Here, we prove NP-completeness of XSAT for exact linear formulas. If in addition the clauses are required to be of uniform length, we show that both XSAT and NAE-SAT are decidable in polynomial time, what even holds for their counting versions.

Recently, Bacsó and Tuza gave a full characterization of the graphs for which every connected induced subgraph has a connected dominating subgraph satisfying an arbitrary prescribed hereditary property. Using their result, we derive a similar characterization of the graphs for which any isolate-free induced subgraph has a total dominating subgraph that satisfies a prescribed additive hereditary property. In particular, we give a characterization for the case where the total dominating subgraphs are a disjoint union of complete graphs. This yields a characterization of the graphs for which every isolate-free induced subgraph has a vertex-dominating induced matching, a so-called induced paired-dominating set.

A dominating set of a graph G is a vertex subset that any vertex of G either belongs to or is adjacent to. A total dominating set is a dominating set whose induced subgraph does not contain isolated vertices. The minimal size of a total dominating set, the total domination number, is denoted by gamma_t . The maximal size of an inclusionwise minimal total dominating set, the upper total domination number, is denoted by Gamma_t . A paired dominating set is a dominating set whose induced subgraph has a perfect matching. The minimal size of a paired dominating set, the paired domination number, is denoted by gamma_p . The maximal size of an inclusionwise minimal paired dominating set, the upper paired domination number, is denoted by Gamma_p . In this paper we prove several results on the ratio of these four parameters: For each r ge 2 we prove the sharp bound gamma_p/gamma_t le 2 - 2/r for K_{1,r} -free graphs. As a consequence, we obtain the sharp bound gamma_p/gamma_t le 2 - 2/(Delta+1) , where Delta is the maximum degree. We also show for each r ge 2 that {C_5,T_r} -free graphs fulfill the sharp bound gamma_p/gamma_t le 2 - 2/r , where T_r is obtained from K_{1,r} by subdividing each edge exactly once. We show that all of these bounds also hold for the ratio Gamma_p / Gamma_t . Further, we prove that a graph hereditarily has an induced paired dominating set iff gamma_p le Gamma_t holds for any induced subgraph. We also give a finite forbidden subgraph characterization for this condition. We exactly determine the maximal value of the ratio gamma_p / Gamma_t taken over the induced subgraphs of a graph. As a consequence, we prove for each r ge 3 the sharp bound gamma_p/Gamma_t le 2 - 2/r for graphs that do not contain the corona of K_{1,r} as subgraph. In particular, we obtain the sharp bound gamma_p/Gamma_t le 2 - 2/Delta .

Using formally matched asymptotic expansions we identify the sharp interface asymptotic limit of an Allen-Cahn/Cahn-Hilliard system using a novel approach which enables us to handle the case of variational inequalities.

The problem of finding a two-connected planar spanning subgraph of maximum weight in a complete edge-weighted graph is important in automatic graph drawing. We investigate the problem from a polyhedral point of view.

Since it is unlikely that any NP-complete problem will ever be efficiently solvable, one is interested in identifying those special cases that can be solved in polynomial time. We deal with the special case of Boolean formulas where the logical implication a is the only operator and any variable (except one) occurs at most twice. For these formulas we show that an infinite hierarchy S_1subseteq S_2cdots exists such that we can test any formula from S_i for falsifiability in time O(n i ), where n is the number of variables in the formula. We describe an algorithm that finds a falsifying assignment, if one exists. Furthermore we show that the falsifiability problem for igcup_{i=1}^infty S_i is NP-complete by reducing the SAT-Problem. In contrast to the hierarchy described by Gallo and Scutella for Boolean formulas in CNF, where the test for membership in the k-th level of the hierarchy needs time O(n k ), our hierarchy permits a linear time membership test. Finally we show that S_1 is neither a sub- nor a superset of some commonly known classes of Boolean formulas, for which the SAT-Problem has linear time complexity (Horn formulas, 2-SAT, nested satisfiability).

Let K be a cone in R n , K ∗ the polar cone. A n × n -matrix A is called quasimonotone with respect to K , if x ϵ K ⇒ ∃ϕ ϵ K ∗ , ϕ ≠ 0, (ϕ, x ) = 0, (ϕ, Ax ) ⩾ 0. It is shown, that several properties are equivalent with this, especially the monotonicity of exp( tA ) for all t ⩾ 0. This was already shown by Schneider-Vidyasagar, here we give a new approach by considering the differential equation x ′( t ) = Ax ( t ), x (0) ϵ K . Two open questions in [5] are settled. We then consider irreducible quasimonotone matrices and show that most of the usual properties of irreducible monotone matrices hold also for this class. In the last section it is shown, that the connections between A quasimonotone and exp( tA ) monotone are special cases of differential inequalities for initial value problems in partially ordered topological vector spaces. The concept “quasimonotone,” introduced here in a similar manner as by Volkmann, is not only sufficient, but proves also to be essentially necessary for inequalities of this type.