On three polynomial kernels of sequences for arbitrarily partitionable graphs

详细信息    查看全文

• 作者：Julien Bensmail ^{julien.bensmail.phd@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Arbitrarily partitionable graph ; Kernel of sequences
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：31 March 2016
• 年：2016
• 卷：202
• 期：Complete
• 页码：19-29
• 全文大小：416 K

文摘

A graph G$G$ is arbitrarily partitionable if every sequence (n₁,n₂,…,n_p)$(n_1,n_2,\dots ,n_p)$ of positive integers summing up to |V(G)|$\left|V\left(G\right)\right|$ is realizable in G$G$, i.e.   there exists a partition (V₁,V₂,…,V_p)$(V_1,V_2,\dots ,V_p)$ of V(G)$V\left(G\right)$ such that V_i$V_i$ induces a connected subgraph of G$G$ on n_i$n_i$ vertices for every i∈{1,2,…,p}$i\in \{1,2,\dots ,p\}$. Given a family F(n)$\mathcal{F}\left(n\right)$ of graphs with order n≥1$n\ge 1$, a kernel of sequences for F(n)$\mathcal{F}\left(n\right)$ is a set K_F(n)$K_{\mathcal{F}}\left(n\right)$ of sequences summing up to n$n$ such that every member G$G$ of F(n)$\mathcal{F}\left(n\right)$ is arbitrarily partitionable if and only if every sequence of K_F(n)$K_{\mathcal{F}}\left(n\right)$ is realizable in G$G$. We herein provide kernels with polynomial size for three classes of graphs, namely complete multipartite graphs, graphs with about a half universal vertices, and graphs made up of several arbitrarily partitionable components. Our kernel for complete multipartite graphs yields a polynomial-time algorithm to decide whether such a graph is arbitrarily partitionable.