Arithmetically maximal independent sets in infinite graphs
Discussiones Mathematicae Graph Theory (2005)
- Volume: 25, Issue: 1-2, page 167-182
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topStanisław Bylka. "Arithmetically maximal independent sets in infinite graphs." Discussiones Mathematicae Graph Theory 25.1-2 (2005): 167-182. <http://eudml.org/doc/270448>.
@article{StanisławBylka2005,
abstract = {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.},
author = {Stanisław Bylka},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {infinite graph; independent set; arithmetical maximal set; line graph},
language = {eng},
number = {1-2},
pages = {167-182},
title = {Arithmetically maximal independent sets in infinite graphs},
url = {http://eudml.org/doc/270448},
volume = {25},
year = {2005},
}
TY - JOUR
AU - Stanisław Bylka
TI - Arithmetically maximal independent sets in infinite graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2005
VL - 25
IS - 1-2
SP - 167
EP - 182
AB - 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.
LA - eng
KW - infinite graph; independent set; arithmetical maximal set; line graph
UR - http://eudml.org/doc/270448
ER -
References
top- [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. Zbl0505.05049
- [2] J.C. Bermond and J.C. Meyer, Graphe représentatif des aretes d'un multigraphe, J. Math. Pures Appl. 52 (1973) 229-308. Zbl0219.05078
- [3] Y. Caro and Z. Tuza, Improved lower bounds on k-independence, J. Graph Theory 15 (1991) 99-107, doi: 10.1002/jgt.3190150110. Zbl0753.68079
- [4] M.J. Jou and G.J. Chang, Algorithmic aspects of counting independent sets, Ars Combinatoria 65 (2002) 265-277. Zbl1071.05576
- [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. Zbl0398.90069
- [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. Zbl0153.25801
- [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. Zbl0357.04017
- [8] K. Steffens, Matching in countable graphs, Can. J. Math. 29 (1976) 165-168, doi: 10.4153/CJM-1977-016-8. Zbl0324.05122
- [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. Zbl0764.05082
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.