Geodesic
Maximum cardinality 1-restricted simple 2-matchings
The electronic journal of combinatorics, Tome 14 (2007)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A simple 2-matching in a graph is a subgraph all of whose nodes have degree $1$ or $2$. A simple 2-matching is called $k$-restricted if every connected component has $>k$ edges. We consider the problem of finding a $k$-restricted simple 2-matching with a maximum number of edges, which is a relaxation of the problem of finding a Hamilton cycle in a graph. Our main result is a min-max theorem for the maximum number of edges in a 1-restricted simple 2-matching. We prove this result constructively by presenting a polynomial time algorithm for finding a 1-restricted simple 2-matching with a maximum number of edges.
DOI : 10.37236/991
Classification : 05C70, 05C38, 90C27, 05C35
Mots-clés : 1-restricted 2-matchings, Hamilton cycle, min max theorem 
@article{10_37236_991,
     author = {David Hartvigsen},
     title = {Maximum cardinality 1-restricted simple 2-matchings},
     journal = {The electronic journal of combinatorics},
     year = {2007},
     volume = {14},
     doi = {10.37236/991},
     zbl = {1158.05332},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/991/}
}
TY  - JOUR
AU  - David Hartvigsen
TI  - Maximum cardinality 1-restricted simple 2-matchings
JO  - The electronic journal of combinatorics
PY  - 2007
VL  - 14
UR  - http://geodesic.mathdoc.fr/articles/10.37236/991/
DO  - 10.37236/991
ID  - 10_37236_991
ER  - 
%0 Journal Article
%A David Hartvigsen
%T Maximum cardinality 1-restricted simple 2-matchings
%J The electronic journal of combinatorics
%D 2007
%V 14
%U http://geodesic.mathdoc.fr/articles/10.37236/991/
%R 10.37236/991
%F 10_37236_991
David Hartvigsen. Maximum cardinality 1-restricted simple 2-matchings. The electronic journal of combinatorics, Tome 14 (2007). doi: 10.37236/991

Cité par Sources :