PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2006 | 26 | 2 | 181-192
Tytuł artykułu

Extremal bipartite graphs with a unique k-factor

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Wydawca
Rocznik
Tom
26
Numer
2
Strony
181-192
Opis fizyczny
Daty
wydano
2006
otrzymano
2002-03-14
poprawiono
2005-12-15
Twórcy
  • Watson Wyatt Deutschland GmbH, 80339 Munich, Germany
  • Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra, Szafrana 4a, 65-516 Zielona Góra, Poland
  • Lehrstuhl II für Mathematik, RWTH-Aachen, 52056 Aachen, Germany
Bibliografia
  • [1] G. Chartrand and L. Lesniak, Graphs and Digraphs 3rd edition (Chapman and Hall, London 1996).
  • [2] G.R.T. Hendry, Maximum graphs with a unique k-factor, J. Combin. Theory (B) 37 (1984) 53-63, doi: 10.1016/0095-8956(84)90044-3.
  • [3] A. Hoffmann and L. Volkmann, On unique k-factors and unique [1,k] -factors in graphs, Discrete Math. 278 (2004) 127-138, doi: 10.1016/S0012-365X(03)00248-6.
  • [4] P. Johann, On the structure of graphs with a unique k-factor, J. Graph Theory 35 (2000) 227-243, doi: 10.1002/1097-0118(200012)35:4<227::AID-JGT1>3.0.CO;2-D
  • [5] D. König, Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Math. Ann. 77 (1916) 453-465, doi: 10.1007/BF01456961.
  • [6] J. Sheehan, Graphs with exactly one hamiltonian circuit, J. Graph Theory 1 (1977) 37-43, doi: 10.1002/jgt.3190010110.
  • [7] L. Volkmann, The maximum size of graphs with a unique k-factor, Combinatorica 24 (2004) 531-540, doi: 10.1007/s00493-004-0032-9.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1311
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.