Displaying similar documents to “A generalization of a theorem of Turán for valuated graphs”

Extremal bipartite graphs with a unique k-factor

Arne Hoffmann, Elżbieta Sidorowicz, Lutz Volkmann (2006)

Discussiones Mathematicae Graph Theory

Similarity:

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