- Tytuł:
- Extremal bipartite graphs with a unique k-factor
- Autorzy:
-
Hoffmann, Arne
Sidorowicz, Elżbieta
Volkmann, Lutz - Powiązania:
- https://bibliotekanauki.pl/articles/743924.pdf
- Data publikacji:
- 2006
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
unique k-factor
bipartite graphs
extremal graphs - Opis:
- Given integers p > k > 0, we consider the following problem of extremal graph theory: How many edges can a bipartite graph of order 2p have, if it contains a unique k-factor? We show that a labeling of the vertices in each part exists, such that at each vertex the indices of its neighbours in the factor are either all greater or all smaller than those of its neighbours in the graph without the factor. This enables us to prove that every bipartite graph with a unique k-factor and maximal size has exactly 2k vertices of degree k and 2k vertices of degree (|V(G)|)/2. As our main result we show that for k ≥ 1, p ≡ t mod k, 0 ≤ t < k, a bipartite graph G of order 2p with a unique k-factor meets 2|E(G)| ≤ p(p+k)-t(k-t). Furthermore, we present the structure of extremal graphs.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2006, 26, 2; 181-192
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł