Extremal bipartite graphs with a unique k-factor

Arne Hoffmann; Elżbieta Sidorowicz; Lutz Volkmann

Discussiones Mathematicae Graph Theory (2006)

  • Volume: 26, Issue: 2, page 181-192
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Arne Hoffmann, Elżbieta Sidorowicz, and Lutz Volkmann. "Extremal bipartite graphs with a unique k-factor." Discussiones Mathematicae Graph Theory 26.2 (2006): 181-192. <http://eudml.org/doc/270421>.

@article{ArneHoffmann2006,
abstract = {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.},
author = {Arne Hoffmann, Elżbieta Sidorowicz, Lutz Volkmann},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {unique k-factor; bipartite graphs; extremal graphs; unique -factor},
language = {eng},
number = {2},
pages = {181-192},
title = {Extremal bipartite graphs with a unique k-factor},
url = {http://eudml.org/doc/270421},
volume = {26},
year = {2006},
}

TY - JOUR
AU - Arne Hoffmann
AU - Elżbieta Sidorowicz
AU - Lutz Volkmann
TI - Extremal bipartite graphs with a unique k-factor
JO - Discussiones Mathematicae Graph Theory
PY - 2006
VL - 26
IS - 2
SP - 181
EP - 192
AB - 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.
LA - eng
KW - unique k-factor; bipartite graphs; extremal graphs; unique -factor
UR - http://eudml.org/doc/270421
ER -

References

top
  1. [1] G. Chartrand and L. Lesniak, Graphs and Digraphs 3rd edition (Chapman and Hall, London 1996). Zbl0890.05001
  2. [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. Zbl0535.05036
  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. Zbl1041.05060
  4. [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 Zbl0965.05080
  5. [5] D. König, Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Math. Ann. 77 (1916) 453-465, doi: 10.1007/BF01456961. 
  6. [6] J. Sheehan, Graphs with exactly one hamiltonian circuit, J. Graph Theory 1 (1977) 37-43, doi: 10.1002/jgt.3190010110. Zbl0359.05026
  7. [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. Zbl1058.05042

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.