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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1311,
author = {Arne Hoffmann and El\.zbieta Sidorowicz and Lutz Volkmann},
title = {Extremal bipartite graphs with a unique k-factor},
journal = {Discussiones Mathematicae Graph Theory},
volume = {26},
year = {2006},
pages = {181-192},
zbl = {1142.05067},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1311}
}
Arne Hoffmann; Elżbieta Sidorowicz; Lutz Volkmann. Extremal bipartite graphs with a unique k-factor. Discussiones Mathematicae Graph Theory, Tome 26 (2006) pp. 181-192. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1311/
[000] [1] G. Chartrand and L. Lesniak, Graphs and Digraphs 3rd edition (Chapman and Hall, London 1996). | Zbl 0890.05001
[001] [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. | Zbl 0535.05036
[002] [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. | Zbl 1041.05060
[003] [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 | Zbl 0965.05080
[004] [5] D. König, Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Math. Ann. 77 (1916) 453-465, doi: 10.1007/BF01456961.
[005] [6] J. Sheehan, Graphs with exactly one hamiltonian circuit, J. Graph Theory 1 (1977) 37-43, doi: 10.1002/jgt.3190010110. | Zbl 0359.05026
[006] [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. | Zbl 1058.05042