Geodesic
Extremal bipartite graphs with a unique k-factor
Discussiones Mathematicae. Graph Theory, Tome 26 (2006) no. 2, pp. 181-192.

Voir la notice de l'article provenant de la source Library of Science

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.
Mots-clés : unique k-factor, bipartite graphs, extremal graphs 
@article{DMGT_2006_26_2_a0,
     author = {Hoffmann, Arne and Sidorowicz, El\.zbieta and Volkmann, Lutz},
     title = {Extremal bipartite graphs with a unique k-factor},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {181--192},
     publisher = {mathdoc},
     volume = {26},
     number = {2},
     year = {2006},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/item/DMGT_2006_26_2_a0/}
}
TY  - JOUR
AU  - Hoffmann, Arne
AU  - Sidorowicz, Elżbieta
AU  - Volkmann, Lutz
TI  - Extremal bipartite graphs with a unique k-factor
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2006
SP  - 181
EP  - 192
VL  - 26
IS  - 2
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/item/DMGT_2006_26_2_a0/
LA  - en
ID  - DMGT_2006_26_2_a0
ER  - 
%0 Journal Article
%A Hoffmann, Arne
%A Sidorowicz, Elżbieta
%A Volkmann, Lutz
%T Extremal bipartite graphs with a unique k-factor
%J Discussiones Mathematicae. Graph Theory
%D 2006
%P 181-192
%V 26
%N 2
%I mathdoc
%U https://geodesic-test.mathdoc.fr/item/DMGT_2006_26_2_a0/
%G en
%F DMGT_2006_26_2_a0
Hoffmann, Arne; Sidorowicz, Elżbieta; Volkmann, Lutz. Extremal bipartite graphs with a unique k-factor. Discussiones Mathematicae. Graph Theory, Tome 26 (2006) no. 2, pp. 181-192. https://geodesic-test.mathdoc.fr/item/DMGT_2006_26_2_a0/

[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:4227::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.