Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Extremal bipartite graphs with a unique k-factor

100%

Hoffmann A., Sidorowicz E., Volkmann L.

Discussiones Mathematicae Graph Theory

2006

tom 26

nr 2

181-192

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Hoffmann A.

1 Sidorowicz E.

1 Volkmann L.

1 2006

Wyniki wyszukiwania

Extremal bipartite graphs with a unique k-factor