Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
independent sets; perfect independent sets; unique independent sets; strong unique independent sets; super unique independent sets
independent sets; perfect independent sets; unique independent sets; strong unique independent sets; super unique independent sets
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$.
References:
[1] C. Berge: Graphs. Second revised edition, North-Holland, 1985. MR 0809587 | Zbl 0566.05001
[2] G. Chartrand, L. Lesniak: Graphs and Digraphs. Third edition, Chapman and Hall, London, 1996. MR 1408678
[3] C. Croitoru, E. Suditu: Perfect stables in graphs. Inf. Process. Lett. 17 (1983), 53–56. DOI 10.1016/0020-0190(83)90091-1 | MR 0724697
[4] P. Hall: On representatives of subsets. J. London Math. Soc. 10 (1935), 26–30. Zbl 0010.34503
[5] G. Hopkins, W. Staton: Graphs with unique maximum independent sets. Discrete Math. 57 (1985), 245–251. DOI 10.1016/0012-365X(85)90177-3 | MR 0816813
[6] D. König: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math. Ann. 77 (1916), 453–465. DOI 10.1007/BF01456961 | MR 1511872
[7] D. König: Graphs and matrices. Math. Fiz. Lapok 38 (1931), 116–119. (Hungarian)
[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
[9] J. B. Listing: Der Census räumlicher Complexe oder Verallgemeinerungen des Eulerschen Satzes von den Polyedern. Göttinger Abhandlungen 10 (1862).
[10] L. Lovász: A generalization of König’s theorem. Acta Math. Acad. Sci. Hung. 21 (1970), 443–446. DOI 10.1007/BF01894789
[11] L. Lovász, M. D. Plummer: Matching Theory. Ann. Discrete Math. 29, North-Holland, 1986.
[12] W. Siemes, J. Topp, L. Volkmann: On unique independent sets in graphs. Discrete Math. 131 (1994), 279–285. DOI 10.1016/0012-365X(94)90389-1 | MR 1287738
[13] L. Volkmann: Minimale und unabhängige minimale Überdeckungen. An. Univ. Bucur. Mat. 37 (1988), 85–90. MR 0993604
Search
Partner of
