Page 240 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 240
ALGORITHMIC GRAPH THEORY (MS-54)
On Efficient Domination for H-free bipartite graphs
Andreas Brandstaedt, andreas.brandstaedt@uni-rostock.de
Institute of Informatics, Germany
Coauthor: Raffaele Mosca
A vertex set D in a finite undirected graph G is an efficient dominating set (e.d.s. for short) of
G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED)
problem, asks for the existence of an e.d.s. in G; it is the Exact Cover problem for the closed
neighborhood hypergraph of G. ED is known to be NP-complete even for very restricted H-
free graph classes such as for 2P3-free chordal graphs (and thus, for P7-free graphs) while it is
solvable in polynomial time for P6-free graphs. For H-free graphs, ED is either NP-complete or
polynomial, i.e., a dichotomy. However, for H-free bipartite graphs, there is no such dichotomy.
Lu and Tang showed that ED is NP-complete for chordal bipartite graphs and for planar
bipartite graphs; actually, ED is NP-complete even for planar bipartite graphs with vertex degree
at most 3 and girth at least g for every fixed g. Thus, ED is NP-complete for K1,4-free bipartite
graphs and for C4-free bipartite graphs. For classes of bounded clique-width, ED is solvable in
polynomial time. Dabrowski and Paulusma published a dichotomy for clique-width of H-free
bipartite graphs. For instance, clique-width of S1,2,3-free bipartite graphs is bounded.
In Discrete Applied Math. 270 (2019), we published a manuscript “On efficient domination
for some classes of H-free bipartite graphs”. We showed that (weighted) ED can be solved in
polynomial time for H-free bipartite graphs when H is P7 or P4 for fixed , and similarly for
P9-free bipartite graphs with vertex degree at most 3, and when H is S2,2,4. In this talk, we also
mention a polynomial time solution for P8-free bipartite graphs (which was an open problem in
our publication).
Domination number of graphs with fixed minimum degree
Csilla Bujtás, csilla.bujtas@fmf.uni-lj.si
University of Ljubljana, Slovenia
We discuss upper bounds on the domination number of graphs with a fixed minimum degree.
The main result states that for every graph G on n vertices and with minimum degree 5, the
domination number γ(G) cannot exceed n/3. The proof is obtained via an algorithmic approach
where a weighting method is combined with a discharging process.
Extending Thomason’s Algorithm
Kathie Cameron, kcameron@wlu.ca
Wilfrid Laurer University, Canada
Carsten Thomassen and I proved that in any graph G, the number of cycles containing a spec-
ified edge as well as all the odd-degree vertices is odd if and only if G is eulerian. Where all
vertices have even degree this is a theorem of Shunichi Toida and where all vertices have odd
degree it is Andrew Thomason’s extension of Smith’s Theorem. Andrew Thomason proved his
theorem by constructing a graph X(G) in which the odd-degree vertices correspond precisely to
the things he wants to show there are an even number of, namely the hamiltonian cycles contain-
238
On Efficient Domination for H-free bipartite graphs
Andreas Brandstaedt, andreas.brandstaedt@uni-rostock.de
Institute of Informatics, Germany
Coauthor: Raffaele Mosca
A vertex set D in a finite undirected graph G is an efficient dominating set (e.d.s. for short) of
G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED)
problem, asks for the existence of an e.d.s. in G; it is the Exact Cover problem for the closed
neighborhood hypergraph of G. ED is known to be NP-complete even for very restricted H-
free graph classes such as for 2P3-free chordal graphs (and thus, for P7-free graphs) while it is
solvable in polynomial time for P6-free graphs. For H-free graphs, ED is either NP-complete or
polynomial, i.e., a dichotomy. However, for H-free bipartite graphs, there is no such dichotomy.
Lu and Tang showed that ED is NP-complete for chordal bipartite graphs and for planar
bipartite graphs; actually, ED is NP-complete even for planar bipartite graphs with vertex degree
at most 3 and girth at least g for every fixed g. Thus, ED is NP-complete for K1,4-free bipartite
graphs and for C4-free bipartite graphs. For classes of bounded clique-width, ED is solvable in
polynomial time. Dabrowski and Paulusma published a dichotomy for clique-width of H-free
bipartite graphs. For instance, clique-width of S1,2,3-free bipartite graphs is bounded.
In Discrete Applied Math. 270 (2019), we published a manuscript “On efficient domination
for some classes of H-free bipartite graphs”. We showed that (weighted) ED can be solved in
polynomial time for H-free bipartite graphs when H is P7 or P4 for fixed , and similarly for
P9-free bipartite graphs with vertex degree at most 3, and when H is S2,2,4. In this talk, we also
mention a polynomial time solution for P8-free bipartite graphs (which was an open problem in
our publication).
Domination number of graphs with fixed minimum degree
Csilla Bujtás, csilla.bujtas@fmf.uni-lj.si
University of Ljubljana, Slovenia
We discuss upper bounds on the domination number of graphs with a fixed minimum degree.
The main result states that for every graph G on n vertices and with minimum degree 5, the
domination number γ(G) cannot exceed n/3. The proof is obtained via an algorithmic approach
where a weighting method is combined with a discharging process.
Extending Thomason’s Algorithm
Kathie Cameron, kcameron@wlu.ca
Wilfrid Laurer University, Canada
Carsten Thomassen and I proved that in any graph G, the number of cycles containing a spec-
ified edge as well as all the odd-degree vertices is odd if and only if G is eulerian. Where all
vertices have even degree this is a theorem of Shunichi Toida and where all vertices have odd
degree it is Andrew Thomason’s extension of Smith’s Theorem. Andrew Thomason proved his
theorem by constructing a graph X(G) in which the odd-degree vertices correspond precisely to
the things he wants to show there are an even number of, namely the hamiltonian cycles contain-
238
