# Csilla Bujtas: Bipartite graphs with close domination and k-domination numbers

Source: Discrete mathematics seminar

**Tuesday, January 12th at 10.15 **

**Join Zoom Meeting**

https://uni-lj-si.zoom.us/j/95203068752?pwd=elN1QngvWmZIeFVWTHVTNU1FRHNiZz09

Meeting ID: 952 0306 8752

Passcode: 436520

**Abstract.** Let *k* be a positive integer and let *G* be a graph with vertex set
*V*(*G*). A subset D \subseteq *V*(*G*) is a *k*-dominating set if
every vertex outside *D* is adjacent to at least *k* vertices in *D*. The *k*-domination number \gamma_k(G) is the minimum cardinality of a *k*-dominating set in *G*. For any
graph *G*, we know that \gamma_k(G) >= \gamma(G)+k-2 where \Delta(*G*) >= *k* >= 2 and this bound is sharp for every *k* >= 2.
In the talk, after discussing some prliminaries,
we characterize bipartite graphs satisfying the equality for *k* >= 3
and present a necessary and sufficient condition for a bipartite graph
to satisfy the equality hereditarily when *k*=3. We also prove that
the problem of deciding whether a graph satisfies
the given equality is NP-hard in general.

Based on a joint work with Gülnaz Boruzanli Ekinci.