Some cases of the polynomial solvability of the problem of findingan independent $\{K_1,K_2\}$-packing of maximum weight in a graph

V. V. Lepin

Trudy Instituta matematiki, Tome 24 (2016) no. 2, pp. 72-90

Résumé

Let $\mathcal{H}$ be a fixed set of connected graphs. A $\mathcal{H}$-packing of a given graph $G$ is a pairwise vertex-disjoint set of subgraphs of $G,$ each isomorphic to a member of $\mathcal{H}.$ An independent $\mathcal{H}$-packing of a given graph $G$ is an $\mathcal{H}$-packing of $G$ in which no two subgraphs of the packing are joined by an edge of $G.$ Given a graph $G$ with a vertex weight function $\omega_V:~V(G)\to\mathbb{N}$ and an edge weight function and $\omega_E:~E(G)\to\mathbb{N},$ weight of an independent $\{K_1,K_2\}$-packing $S$ in $G$ is $\sum_{v\in U}\omega_V(v)+\sum_{e\in F}\omega_E(e),$ where $U=\bigcup_{H\in\mathcal{S},~H\cong K_1}V(H),$ and $F=\bigcup_{H\in\mathcal{S}}E(H).$ The problem of finding an independent $\{K_1,K_2\}$-packing of maximum weight is considered. Let $C(G_1,\ldots ,G_{|V(C)|})$ denote a graph formed from a labelled graph $C$ and unlabelled graphs $G_1,\ldots ,G_{|V(C)|},$ replacing every vertex $v_i\in V(C)$ by the graph $G_i,$ and joining the vertices of $V(G_i)$ with all the vertices of those of $V(G_j),$ whenever $v_iv_j\in E(C).$ For unlabelled graphs $C,G_1,\ldots ,G_{|V(C)|},$ let $\Phi_C(G_1,\ldots ,G_{|V(C)|})$ stand for the class of all graphs $C(G_1,\ldots ,G_{|V(C)|})$ taken over all possible orderings of $V(C).$ Let $\mathcal{B,C}$ be classes of prime graphs such that $K_1\in \mathcal{B}\backslash \mathcal{C}.$ A prime inductive class of graphs, $I(\mathcal{B,C}),$ is defined inductively as follows: (1) all graphs from $\mathcal{B}$ belong to $I(\mathcal{B,C}),$ (2) if $C\in \mathcal{C}$ and $\{G_1,\ldots ,G_{|V(C)|}\}\subseteq$ $\subseteq I(\mathcal{B,C}),$ then all graphs from $\Phi_C(G_1,\ldots ,G_{|V(C)|})$ belong to $I(\mathcal{B,C}).$ We present a robust $O(m(m+n))$ time algorithm solving this problem for the graph class $I(\{K_1\}, \mathcal{G}_1\cup \mathcal{G}_2\cup \mathcal{G}_3\cup \mathcal{G}_4),$ where $\mathcal{G}_1$ — prime split graphs, $\mathcal{G}_2$ — prime trees, $\mathcal{G}_3$ — prime unicycle, $\mathcal{G}_3$ — prime co-gem-free graphs.