# Article

 Title: On perfect and unique maximum independent sets in graphs (English) Author: Volkmann, Lutz Language: English Journal: Mathematica Bohemica ISSN: 0862-7959 (print) ISSN: 2464-7136 (online) Volume: 129 Issue: 3 Year: 2004 Pages: 273-282 Summary lang: English . Category: math . Summary: A perfect independent set $I$ of a graph $G$ is defined to be an independent set with the property that any vertex not in $I$ has at least two neighbors in $I$. For a nonnegative integer $k$, a subset $I$ of the vertex set $V(G)$ of a graph $G$ is said to be $k$-independent, if $I$ is independent and every independent subset $I^{\prime }$ of $G$ with $|I^{\prime }|\ge |I|-(k-1)$ is a subset of $I$. A set $I$ of vertices of $G$ is a super $k$-independent set of $G$ if $I$ is $k$-independent in the graph $G[I,V(G)-I]$, where $G[I,V(G)-I]$ is the bipartite graph obtained from $G$ by deleting all edges which are not incident with vertices of $I$. It is easy to see that a set $I$ is $0$-independent if and only if it is a maximum independent set and 1-independent if and only if it is a unique maximum independent set of $G$. In this paper we mainly investigate connections between perfect independent sets and $k$-independent as well as super $k$-independent sets for $k=0$ and $k=1$. (English) Keyword: independent sets Keyword: perfect independent sets Keyword: unique independent sets Keyword: strong unique independent sets Keyword: super unique independent sets MSC: 05C69 MSC: 05C70 idZBL: Zbl 1080.05527 idMR: MR2092713 DOI: 10.21136/MB.2004.134148 . Date available: 2009-09-24T22:15:00Z Last updated: 2020-07-29 Stable URL: http://hdl.handle.net/10338.dmlcz/134148 . Reference: [1] C. Berge: Graphs.Second revised edition, North-Holland, 1985. Zbl 0566.05001, MR 0809587 Reference: [2] G. Chartrand, L. Lesniak: Graphs and Digraphs.Third edition, Chapman and Hall, London, 1996. MR 1408678 Reference: [3] C. Croitoru, E. Suditu: Perfect stables in graphs.Inf. Process. Lett. 17 (1983), 53–56. MR 0724697, 10.1016/0020-0190(83)90091-1 Reference: [4] P. Hall: On representatives of subsets.J. London Math. Soc. 10 (1935), 26–30. Zbl 0010.34503 Reference: [5] G. Hopkins, W. Staton: Graphs with unique maximum independent sets.Discrete Math. 57 (1985), 245–251. MR 0816813, 10.1016/0012-365X(85)90177-3 Reference: [6] D. König: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre.Math. Ann. 77 (1916), 453–465. MR 1511872, 10.1007/BF01456961 Reference: [7] D. König: Graphs and matrices.Math. Fiz. Lapok 38 (1931), 116–119. (Hungarian) Reference: [8] D. König: Theorie der endlichen und unendlichen Graphen.Akademische Verlagsgesellschaft, Leipzig, 1936; reprinted: Teubner-Archiv zur Mathematik, Band 6, Leipzig, 1986. MR 0886676 Reference: [9] J. B. Listing: Der Census räumlicher Complexe oder Verallgemeinerungen des Eulerschen Satzes von den Polyedern.Göttinger Abhandlungen 10 (1862). Reference: [10] L. Lovász: A generalization of König’s theorem.Acta Math. Acad. Sci. Hung. 21 (1970), 443–446. 10.1007/BF01894789 Reference: [11] L. Lovász, M. D. Plummer: Matching Theory.Ann. Discrete Math. 29, North-Holland, 1986. Reference: [12] W. Siemes, J. Topp, L. Volkmann: On unique independent sets in graphs.Discrete Math. 131 (1994), 279–285. MR 1287738, 10.1016/0012-365X(94)90389-1 Reference: [13] L. Volkmann: Minimale und unabhängige minimale Überdeckungen.An. Univ. Bucur. Mat. 37 (1988), 85–90. MR 0993604 .

## Files

Files Size Format View
MathBohem_129-2004-3_4.pdf 314.3Kb application/pdf View/Open

Partner of