اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدFinding Efficient Domination for $(P_9,S_{1,1,6},S_{1,2,5}$-Free Chordal Bipartite Graphs in Polynomial Time
403
0
0.0
(
0
)
تأليف
Andreas Brandstadt
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A vertex set $D$ in a finite undirected graph $G$ is an {em efficient dominating set} (emph{e.d.s.} for short) of $G$ if every vertex of $G$ is dominated by exactly one vertex of $D$. The emph{Efficient Domination} (ED) problem, which asks for the existence of an e.d.s. in $G$, is known to be NP-complete for $P_7$-free graphs, and even for very restricted $H$-free bipartite graph classes such as for $K_{1,4}$-free bipartite graphs as well as for $C_4$-free bipartite graphs while it is solvable in polynomial time for $P_8$-free bipartite graphs as well as for $S_{1,3,3}$-free bipartite graphs and for $S_{1,1,5}$-free bipartite graphs. Here we show that ED can be solved in polynomial time for $(P_9,S_{1,1,6},S_{1,2,5})$-free chordal bipartite graphs.
قيم البحث
اقرأ أيضاً
Given two independent sets $I, J$ of a graph $G$, and imagine that a token (coin) is placed at each vertex of $I$. The Sliding Token problem asks if one could transform $I$ to $J$ via a sequence of elementary steps, where each step requires sliding a
token from one vertex to one of its neighbors so that the resulting set of vertices where tokens are placed remains independent. This problem is $mathsf{PSPACE}$-complete even for planar graphs of maximum degree $3$ and bounded-treewidth. In this paper, we show that Sliding Token can be solved efficiently for cactus graphs and block graphs, and give upper bounds on the length of a transformation sequence between any two independent sets of these graph classes. Our algorithms are designed based on two main observations. First, all structures that forbid the existence of a sequence of token slidings between $I$ and $J$, if exist, can be found in polynomial time. A sufficient condition for determining no-instances can be easily derived using this characterization. Second, without such forbidden structures, a sequence of token slidings between $I$ and $J$ does exist. In this case, one can indeed transform $I$ to $J$ (and vice versa) using a polynomial number of token-slides.
A vertex subset $S$ of a graph $G=(V,E)$ is a $[1,2]$-dominating set if each vertex of $Vbackslash S$ is adjacent to either one or two vertices in $S$. The minimum cardinality of a $[1,2]$-dominating set of $G$, denoted by $gamma_{[1,2]}(G)$, is call
ed the $[1,2]$-domination number of $G$. In this paper the $[1,2]$-domination and the $[1,2]$-total domination numbers of the generalized Petersen graphs $P(n,2)$ are determined.
Power domination in graphs emerged from the problem of monitoring an electrical system by placing as few measurement devices in the system as possible. It corresponds to a variant of domination that includes the possibility of propagation. For measur
ement devices placed on a set S of vertices of a graph G, the set of monitored vertices is initially the set S together with all its neighbors. Then iteratively, whenever some monitored vertex v has a single neighbor u not yet monitored, u gets monitored. A set S is said to be a power dominating set of the graph G if all vertices of G eventually are monitored. The power domination number of a graph is the minimum size of a power dominating set. In this paper, we prove that any maximal planar graph of order n $ge$ 6 admits a power dominating set of size at most (n--2)/4 .
A graph is called $P_t$-free if it does not contain the path on $t$ vertices as an induced subgraph. Let $H$ be a multigraph with the property that any two distinct vertices share at most one common neighbour. We show that the generating function for
(list) graph homomorphisms from $G$ to $H$ can be calculated in subexponential time $2^{Oleft(sqrt{tnlog(n)}right)}$ for $n=|V(G)|$ in the class of $P_t$-free graphs $G$. As a corollary, we show that the number of 3-colourings of a $P_t$-free graph $G$ can be found in subexponential time. On the other hand, no subexponential time algorithm exists for 4-colourability of $P_t$-free graphs assuming the Exponential Time Hypothesis. Along the way, we prove that $P_t$-free graphs have pathwidth that is linear in their maximum degree.
In a recent paper, Beniamini and Nisan gave a closed-form formula for the unique multilinear polynomial for the Boolean function determining whether a given bipartite graph $G subseteq K_{n,n}$ has a perfect matching, together with an efficient algor
ithm for computing the coefficients of the monomials of this polynomial. We give the following generalization: Given an arbitrary non-negative weight function $w$ on the edges of $K_{n,n}$, consider its set of minimum weight perfect matchings. We give the real multilinear polynomial for the Boolean function which determines if a graph $G subseteq K_{n,n}$ contains one of these minimum weight perfect matchings.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
