Geodesic
Strongly maximal matchings in infinite graphs
The electronic journal of combinatorics, Tome 15 (2008)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Given an assignment of weights $w$ to the edges of an infinite graph $G$, a matching $M$ in $G$ is called strongly $w$-maximal if for any matching $N$ there holds $\sum\{w(e) \mid e \in N \setminus M\} \le \sum\{w(e) \mid e \in M \setminus N\}$. We prove that if $w$ assumes only finitely many values all of which are rational then $G$ has a strongly $w$-maximal matching. This result is best possible in the sense that if we allow irrational values or infinitely many values then there need not be a strongly $w$-maximal matching.
DOI : 10.37236/860
Classification : 05C70, 05C22
Mots-clés : weighted edges, infinite graph, matching, strongly weight maximal matching 
@article{10_37236_860,
     author = {Ron Aharoni and Eli Berger and Agelos Georgakopoulos and Philipp Spr\"ussel},
     title = {Strongly maximal matchings in infinite graphs},
     journal = {The electronic journal of combinatorics},
     year = {2008},
     volume = {15},
     doi = {10.37236/860},
     zbl = {1178.05072},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/860/}
}
TY  - JOUR
AU  - Ron Aharoni
AU  - Eli Berger
AU  - Agelos Georgakopoulos
AU  - Philipp Sprüssel
TI  - Strongly maximal matchings in infinite graphs
JO  - The electronic journal of combinatorics
PY  - 2008
VL  - 15
UR  - http://geodesic.mathdoc.fr/articles/10.37236/860/
DO  - 10.37236/860
ID  - 10_37236_860
ER  - 
%0 Journal Article
%A Ron Aharoni
%A Eli Berger
%A Agelos Georgakopoulos
%A Philipp Sprüssel
%T Strongly maximal matchings in infinite graphs
%J The electronic journal of combinatorics
%D 2008
%V 15
%U http://geodesic.mathdoc.fr/articles/10.37236/860/
%R 10.37236/860
%F 10_37236_860
Ron Aharoni; Eli Berger; Agelos Georgakopoulos; Philipp Sprüssel. Strongly maximal matchings in infinite graphs. The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/860

Cité par Sources :