Geodesic
Strongly maximal matchings in infinite graphs
The electronic journal of combinatorics, Tome 15 (2008)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl arXiv EuDML
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 
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
@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

Cité par Sources :