- Tytuł:
- Dense Arbitrarily Partitionable Graphs
- Autorzy:
-
Kalinowski, Rafał
Pilśniak, Monika
Schiermeyer, Ingo
Woźniak, Mariusz - Powiązania:
- https://bibliotekanauki.pl/articles/31341197.pdf
- Data publikacji:
- 2016-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
arbitrarily partitionable graph
Erdös-Gallai condition
traceable graph
perfect matching - Opis:
- A graph $G$ of order $n$ is called arbitrarily partitionable (AP for short) if, for every sequence $(n_1, . . ., n_k)$ of positive integers with $n_1 + ⋯ + n_k = n$, there exists a partition $(V_1, . . ., V_k)$ of the vertex set $V(G)$ such that $V_i$ induces a connected subgraph of order $n_i$ for $i = 1, . . ., k$. In this paper we show that every connected graph $G$ of order $n \ge 22$ and with \( ‖G‖ > \binom{n-4}{2} + 12 \) edges is AP or belongs to few classes of exceptional graphs.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2016, 36, 1; 5-22
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł