Czasopismo
Tytuł artykułu
Autorzy
Treść / Zawartość
Pełne teksty:
Warianty tytułu
Języki publikacji
Abstrakty
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.
Słowa kluczowe
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
167-182
Opis fizyczny
Daty
wydano
2005
otrzymano
2003-11-28
poprawiono
2005-03-08
Twórcy
autor
- Institute of Computer Science, Polish Academy of Sciences, 21 Ordona street, 01-237 Warsaw, Poland
Bibliografia
- [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1270