Zobrazeno 1 - 10
of 25
pro vyhledávání: '"Bouquet, Valentin"'
A set $S\subseteq V$ of a graph $G=(V,E)$ is a dominating set if each vertex has a neighbor in $S$ or belongs to $S$. Dominating Set is the problem of deciding, given a graph $G$ and an integer $k\geq 1$, if $G$ has a dominating set of size at most $
Externí odkaz:
http://arxiv.org/abs/2304.09701
Autor:
Bouquet, Valentin
A set $S\subseteq V(G)$ of a graph $G$ is a dominating set if each vertex has a neighbor in $S$ or belongs to $S$. Let $\gamma(G)$ be the cardinality of a minimum dominating set in $G$. The bondage number $b(G)$ of a graph $G$ is the smallest cardina
Externí odkaz:
http://arxiv.org/abs/2203.09256
Publikováno v:
In Theoretical Computer Science 27 June 2024 1001
Autor:
Bouquet, Valentin
A set $S\subseteq V(G)$ of a graph $G$ is a dominating set if each vertex has a neighbor in $S$ or belongs to $S$. Let $\gamma(G)$ be the cardinality of a minimum dominating set in $G$. The bondage number $b(G)$ of a graph $G$ is the smallest cardina
Externí odkaz:
http://arxiv.org/abs/2107.11216
Perfect Matching-Cut is the problem of deciding whether a graph has a perfect matching that contains an edge-cut. We show that this problem is NP-complete for planar graphs with maximum degree four, for planar graphs with girth five, for bipartite fi
Externí odkaz:
http://arxiv.org/abs/2011.03318
Given a graph $G$ and a non trivial partition $(V_1,V_2)$ of its vertex-set, the satisfaction of a vertex $v\in V_i$ is the ratio between the size of it's closed neighborhood in $V_i$ and the size of its closed neighborhood in $G$. The worst ratio ov
Externí odkaz:
http://arxiv.org/abs/2007.12434
Given a graph $G=(V,E)$, $S\subseteq V$ is a dominating set if every $v\in V\setminus S$ is adjacent to an element of $S$. The Minimum Dominating Set problem asks for a dominating set with minimum cardinality. It is well known that its decision versi
Externí odkaz:
http://arxiv.org/abs/2002.12232
We prove that the Minimum Dominating Set problem is polynomial for the class of (claw, P8)-free graphs.
Externí odkaz:
http://arxiv.org/abs/2001.07554
We characterize the vertices belonging to all minimum dominating sets, to some minimum dominating sets but not all, and to no minimum dominating set. We refine this characterization for some well studied sub-classes of graphs: chordal, claw-free, tri
Externí odkaz:
http://arxiv.org/abs/1909.02843
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.