Geodesic
A quantitative approach to perfect one-factorizations of complete bipartite graphs
Natacha Astromujoff1 ; Martin Matamala2
1Departamento de ciencias, universidad de chile
2Department of Mathematical Engineering, Universidad de Chile
The electronic journal of combinatorics, Tome 22 (2015) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Given a one-factorization $\mathcal{F}$ of the complete bipartite graph $K_{n,n}$, let ${\sf pf}(\mathcal{F})$ denote the number of Hamiltonian cycles obtained by taking pairwise unions of perfect matchings in $\mathcal{F}$. Let ${\sf pf}(n)$ be the maximum of ${\sf pf}(\mathcal{F})$ over all one-factorizations $\mathcal{F}$ of $K_{n,n}$. In this work we prove that ${\sf pf}(n)\geq n^2/4$, for all $n\geq 2$.
DOI : 10.37236/4122
Classification : 05C70, 05C45, 05B15
Mots-clés : perfect one-factorizations, Latin squares

Natacha Astromujoff  1   ; Martin Matamala  2

1 Departamento de ciencias, universidad de chile
2 Department of Mathematical Engineering, Universidad de Chile 
@article{10_37236_4122,
     author = {Natacha Astromujoff and Martin Matamala},
     title = {A quantitative approach to perfect one-factorizations of complete bipartite graphs},
     journal = {The electronic journal of combinatorics},
     year = {2015},
     volume = {22},
     number = {1},
     doi = {10.37236/4122},
     zbl = {1310.05168},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/4122/}
}
TY  - JOUR
AU  - Natacha Astromujoff
AU  - Martin Matamala
TI  - A quantitative approach to perfect one-factorizations of complete bipartite graphs
JO  - The electronic journal of combinatorics
PY  - 2015
VL  - 22
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/4122/
DO  - 10.37236/4122
ID  - 10_37236_4122
ER  - 
%0 Journal Article
%A Natacha Astromujoff
%A Martin Matamala
%T A quantitative approach to perfect one-factorizations of complete bipartite graphs
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/4122/
%R 10.37236/4122
%F 10_37236_4122
Natacha Astromujoff; Martin Matamala. A quantitative approach to perfect one-factorizations of complete bipartite graphs. The electronic journal of combinatorics, Tome 22 (2015) no. 1. doi: 10.37236/4122

Cité par Sources :