DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

F.X. Liu, B. Wu and J.X. Meng

Title:

Arbitrarily partitionable $\{2K_2, C_4\}$-free graphs

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-12-02, Revised: 2019-11-30, Accepted: 2019-11-30, https://doi.org/10.7151/dmgt.2289

Abstract:

A graph $G=(V,E)$ of order $n$ is said to be arbitrarily partitionable if for each sequence $\lambda=(\lambda_1, \lambda_2, \dots, \lambda_p)$ of positive integers with $\lambda_1+\cdots+\lambda_p=n$, there exists a partition $(V_1, V_2, \dots, V_p)$ of the vertex set $V$ such that $V_i$ induces a connected subgraph of order $\lambda_i$ in $G$ for each $i\in \{1,2,\dots,p\}$. In this paper, we show that a threshold graph is arbitrarily partitionable if and only if it admits a perfect matching or a near perfect matching. We also give a necessary and sufficient condition for a $\{2K_2, C_4\}$-free graph being arbitrarily partitionable, as an extension for a result of Broersma, Kratsch and Woeginger [Fully decomposable split graphs, European J. Combin. 34 (2013) 567–575] on split graphs.

Keywords:

arbitrarily partitionable graphs, arbitrarily vertex decomposable, threshold graphs, $\{2K_2, C_4\}$-free graphs

PDF
Close