Paul Dorbec

dblp:03/6993 · DBLP profile ↗
← Back
13ranked-venue papers
5as first author
4since 2021 · last 2025
0009-0007-1179-6082ORCID · verified

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 12 · 4 first-author · 4 since 2021Security and privacy · 1 · 1 first-author
YearPublicationVenuePosition
2025 Orientable burning number of graphs
Julien Courtiel, Paul Dorbec, Tatsuya Gima, Romain Lecoq, Yota Otachi
Discret. Appl. Math.2
2024 Theoretical Analysis of Git Bisect
Julien Courtiel, Paul Dorbec, Romain Lecoq
Algorithmica2
2022 Theoretical Analysis of git bisect
Julien Courtiel, Paul Dorbec, Romain Lecoq
LATIN2
2021 Dominating sets reconfiguration under token sliding
Marthe Bonamy, Paul Dorbec, Paul Ouvrard
Discret. Appl. Math.2
2016 Game total domination for cycles and paths
Paul Dorbec, Michael A. Henning
Discret. Appl. Math.1
2016 Complexity of the game domination problem
Bostjan Bresar, Paul Dorbec, Sandi Klavzar, Gasper Kosmrlj, Gabriel Renault
Theor. Comput. Sci.2
2015 Rook-Drawing for Plane Graphs
David Auber, Nicolas Bonichon, Paul Dorbec, Claire Pennarun
GD3
2014 Contact Representations of Planar Graphs: Extending a Partial Representation is Hard
Steven Chaplick, Paul Dorbec, Jan Kratochvíl, Mickaël Montassier, Juraj Stacho
WG2
2014 Rainbow connection in oriented graphs
Paul Dorbec, Ingo Schiermeyer, Elzbieta Sidorowicz, Éric Sopena
Discret. Appl. Math.1
2013 Generalized Power Domination in Regular Graphs
abstract
In this paper, we continue the study of power domination in graphs (see [T. W. Haynes et al., SIAM J. Discrete Math., 15 (2002), pp. 519--529; P. Dorbec et al., SIAM J. Discrete Math., 22 (2008), pp. 554--567; A. Aazami et al., SIAM J. Discrete Math., 23 (2009), pp. 1382--1399]). Power domination in graphs was birthed from the problem of monitoring an electric power system by placing as few measurement devices in the system as possible. A set of vertices is defined to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set following a set of rules (according to Kirschoff laws) for power system monitoring. The minimum cardinality of a power dominating set of a graph is its power domination number. We show that the power domination of a connected cubic graph on $n$ vertices different from $K_{3,3}$ is at most $n/4$ and this bound is tight. More generally, we show that for $k \ge 1$, the $k$-power domination number of a connected $(k+2)$-regular graph on $n$ vertices different from $K_{k+2,k+2}$ is at most $n/(k+3)$, where the $1$-power domination number is the ordinary power domination number. We show that these bounds are tight.
Paul Dorbec, Michael A. Henning, Christian Löwenstein, Mickaël Montassier, André Raspaud
SIAM J. Discret. Math.1
2012 Generalized power domination of graphs
Gerard J. Chang, Paul Dorbec, Mickaël Montassier, André Raspaud
Discret. Appl. Math.2
2009 Weighted codes in Lee metrics
Paul Dorbec, Sylvain Gravier, Iiro S. Honkala, Michel Mollard
Des. Codes Cryptogr.1
2008 Power Domination in Product Graphs
abstract
The power system monitoring problem asks for as few as possible measurement devices to be put in an electric power system. The problem has a graph theory model involving power dominating sets in graphs. The power domination number $\gamma_P(G)$ of G is the minimum cardinality of a power dominating set. Dorfling and Henning [Discrete Appl. Math., 154 (2006), pp. 1023–1027] determined the power domination number of the Cartesian product of paths. In this paper the power domination number is determined for all direct products of paths except for the odd component of the direct product of two odd paths. For instance, if n is even and C a connected component of $P_m\times P_n$, where m is odd or $m\geq n$, then $\gamma_P(C)=\left\lceil n/4 \right\rceil$. For the strong product we prove that $\gamma_P(P_n \boxtimes P_m) = \max\{\lceil n/3\rceil, \lceil (n+m-2)/4\rceil\}$, unless $3m-n-6 \equiv 4\pmod 8$. The power domination number is also determined for an arbitrary lexicographic product.
Paul Dorbec, Michel Mollard, Sandi Klavzar, Simon Spacapan
SIAM J. Discret. Math.1