Arithmetically maximal independent sets in infinite graphs

• Autorzy: Stanisław Bylka
• Języki publikacji: EN

Abstrakty

EN

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

EN

infinite graph; independent set; arithmetical maximal set; line graph

Kategorie tematyczne

• 05C69: Dominating sets, independent sets, cliques
• 05D05: Extremal set theory
• 05C65: Hypergraphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2005
• Tom: 25
• Numer: 1-2
• Strony: 167-182

Daty

wydano

2005

otrzymano

2003-11-28

poprawiono

2005-03-08

Twórcy

autor

Stanisław Bylka

• 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.

Identyfikatory

DOI

10.7151/dmgt.1270