- Tytuł:
- Arbitrarily Partitionable {2K2, C4}-Free Graphs
- Autorzy:
-
Liu, Fengxia
Wu, Baoyindureng
Meng, Jixiang - Powiązania:
- https://bibliotekanauki.pl/articles/32361721.pdf
- Data publikacji:
- 2022-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
arbitrarily partitionable graphs
arbitrarily vertex decomposable
threshold graphs
{2 K 2, C 4 }-free graphs - Opis:
- A graph G = (V, E) of order n is said to be arbitrarily partitionable if for each sequence λ = (λ1, λ2, …, λp) of positive integers with λ1 + … +λp = n, there exists a partition (V1, V2, … , Vp) of the vertex set V such that Vi induces a connected subgraph of order λi in G for each i ∈ {1, 2, …, 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 {2K2, C4}-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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2022, 42, 2; 485-500
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł