Geodesic
Arithmetically maximal independent sets in infinite graphs
Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 1-2, pp. 167-182.

Voir la notice de l'article provenant de la source Library of Science

Families of all sets of independent vertices in graphs are investigated. The problem how to characterize those infinite graphs which have arithmetically maximal independent sets is posed. A positive answer is given to the following classes of infinite graphs: bipartite graphs, line graphs and graphs having locally infinite clique-cover of vertices. Some counter examples are presented.
Keywords: infinite graph, independent set, arithmetical maximal set, line graph 
@article{DMGT_2005_25_1-2_a16,
     author = {Bylka, Stanis{\l}aw},
     title = {Arithmetically maximal independent sets in infinite graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {167--182},
     publisher = {mathdoc},
     volume = {25},
     number = {1-2},
     year = {2005},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2005_25_1-2_a16/}
}
TY  - JOUR
AU  - Bylka, Stanisław
TI  - Arithmetically maximal independent sets in infinite graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2005
SP  - 167
EP  - 182
VL  - 25
IS  - 1-2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2005_25_1-2_a16/
LA  - en
ID  - DMGT_2005_25_1-2_a16
ER  - 
%0 Journal Article
%A Bylka, Stanisław
%T Arithmetically maximal independent sets in infinite graphs
%J Discussiones Mathematicae. Graph Theory
%D 2005
%P 167-182
%V 25
%N 1-2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2005_25_1-2_a16/
%G en
%F DMGT_2005_25_1-2_a16
Bylka, Stanisław. Arithmetically maximal independent sets in infinite graphs. Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 1-2, pp. 167-182. http://geodesic.mathdoc.fr/item/DMGT_2005_25_1-2_a16/

[1] R. Aharoni, König's duality theorem for infinite bipartite graphs, J. London Math. Society 29 (1984) 1-12, doi: 10.1112/jlms/s2-29.1.1.

[2] J.C. Bermond and J.C. Meyer, Graphe représentatif des aretes d'un multigraphe, J. Math. Pures Appl. 52 (1973) 229-308.

[3] Y. Caro and Z. Tuza, Improved lower bounds on k-independence, J. Graph Theory 15 (1991) 99-107, doi: 10.1002/jgt.3190150110.

[4] M.J. Jou and G.J. Chang, Algorithmic aspects of counting independent sets, Ars Combinatoria 65 (2002) 265-277.

[5] J. Komar and J. Łoś, König's theorem in the infinite case, Proc. of III Symp. on Operat. Res., Mannheim (1978) 153-155.

[6] C.St.J.A. Nash-Williams, Infinite graphs - a survey, J. Combin. Theory 3 (1967) 286-301, doi: 10.1016/S0021-9800(67)80077-2.

[7] K.P. Podewski and K. Steffens, Injective choice functions for countable families, J. Combin. Theory (B) 21 (1976) 40-46, doi: 10.1016/0095-8956(76)90025-3.

[8] K. Steffens, Matching in countable graphs, Can. J. Math. 29 (1976) 165-168, doi: 10.4153/CJM-1977-016-8.

[9] J. Zito, The structure and maximum number of maximum independent sets in trees, J. Graph Theory 15 (1991) 207-221, doi: 10.1002/jgt.3190150208.