Arithmetically maximal independent sets in infinite graphs
Stanisław Bylka
Discussiones Mathematicae Graph Theory, Tome 25 (2005), p. 167-182 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2005-01-01
EUDML-ID : urn:eudml:doc:270448 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1270,
     author = {Stanis\l aw Bylka},
     title = {Arithmetically maximal independent sets in infinite graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {25},
     year = {2005},
     pages = {167-182},
     zbl = {1077.05070},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1270}
}

Stanisław Bylka. Arithmetically maximal independent sets in infinite graphs. Discussiones Mathematicae Graph Theory, Tome 25 (2005) pp. 167-182. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1270/

[000] [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. | Zbl 0505.05049

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

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

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

[004] [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. | Zbl 0398.90069

[005] [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. | Zbl 0153.25801

[006] [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. | Zbl 0357.04017

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

[008] [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. | Zbl 0764.05082