Dominating a family of graphs with small connected subgraphs (Q2703021)

Domination in a graph is generalized here to families of graphs. Let \(F= \{G_1,\dots, G_t\}\) be a family of graphs on the same vertex set \(V\) with \(n\) vertices and let \(k\) be a positive integer. An \((F,k)\)-core is a subset \(D\) of \(V\) such that for each vertex \(v\in V\) and each \(i\in \{1,\dots, t\}\) there exist \(k\) vertices which are adjacent to \(v\) in \(G\). If moreover \(D\) induces a connected subgraph in each graph from \(F\), then \(D\) is called a connected \((F,k)\)-core. The minimum number of vertices of an \((F,k)\)-core is denoted by \(c(k,F)\), of a connected \((F,k)\)-core by \(c_c(k,F)\). The main results state upper bounds for \(c(k, F)\) and \(c_c(k,F)\) in the case when each graph in \(F\) has minimum degree at least \(\delta\) and \(k< \sqrt{\ln\delta}\), \(t< \ln\ln\delta\).