Previous |  Up |  Next


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:
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 Size Format View
MathBohem_129-2004-3_4.pdf 314.3Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo