Factorisation of the complete bipartite graph into spanning semiregular factors

DOI10.1007/S00026-023-00635-5MaRDI QIDQ6065686zbMATH OpenFDO

Authors Mahdieh Hasheminezhad, Brendan D. McKay

Publication date 15 November 2023

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2206.12793

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We enumerate factorisations of the complete bipartite graph into spanning semiregular graphs in several cases, including when the degrees of all the factors except one or two are small. The resulting asymptotic behaviour is seen to generalise the number of semiregular graphs in an elegant way. This leads us to conjecture a general formula when the number of factors is vanishing compared to the number of vertices. As a corollary, we find the average number of ways to partition the edges of a random semiregular bipartite graph into spanning semiregular subgraphs in several cases. Our proof of one case uses a switching argument to find the probability that a set of sufficiently sparse semiregular bipartite graphs are edge-disjoint when randomly labelled.

Recommendations

• Factorisation of the complete graph into spanning regular factors
• scientific article; zbMATH DE number 3893248
• Bipartite 2-factorizations of complete multipartite graphs
• Counting 1-factors in regular bipartite graphs
• Unbalanced star-factorisations of complete bipartite graphs

Cites work

• Asymptotic enumeration of 0-1 matrices with equal row sums and equal column sums
• Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums
• Asymptotic Enumeration of Hypergraphs by Degree Sequence
• Asymptotic enumeration of Latin rectangles
• Asymptotic enumeration of sparse 0--1 matrices with irregular row and column sums
• Complex martingales and asymptotic enumeration
• scientific article; zbMATH DE number 3878944 (Why is no real title available?)
• On a Local Limit Theorem for Integer Random Vectors
• On the number of Latin squares
• Random dense bipartite graphs and directed graphs with specified degrees

Cited in

(3)

• k-regular factors and semi-k-regular factors in bipartite graphs
• On 4-semiregular 1-factorizations of complete graphs and complete bipartite graphs
• scientific article; zbMATH DE number 33140 (Why is no real title available?)

This page was built for publication: Factorisation of the complete bipartite graph into spanning semiregular factors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065686)