Geodesic
On perfect and unique maximum independent sets in graphs
Mathematica Bohemica, Tome 129 (2004) no. 3, pp. 273-282

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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$.
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$.
DOI : 10.21136/MB.2004.134148
Classification : 05C69, 05C70
Keywords: independent sets; perfect independent sets; unique independent sets; strong unique independent sets; super unique independent sets 
Volkmann, Lutz. On perfect and unique maximum independent sets in graphs. Mathematica Bohemica, Tome 129 (2004) no. 3, pp. 273-282. doi: 10.21136/MB.2004.134148
@article{10_21136_MB_2004_134148,
     author = {Volkmann, Lutz},
     title = {On perfect and unique maximum independent sets in graphs},
     journal = {Mathematica Bohemica},
     pages = {273--282},
     year = {2004},
     volume = {129},
     number = {3},
     doi = {10.21136/MB.2004.134148},
     mrnumber = {2092713},
     zbl = {1080.05527},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2004.134148/}
}
TY  - JOUR
AU  - Volkmann, Lutz
TI  - On perfect and unique maximum independent sets in graphs
JO  - Mathematica Bohemica
PY  - 2004
SP  - 273
EP  - 282
VL  - 129
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2004.134148/
DO  - 10.21136/MB.2004.134148
LA  - en
ID  - 10_21136_MB_2004_134148
ER  - 
%0 Journal Article
%A Volkmann, Lutz
%T On perfect and unique maximum independent sets in graphs
%J Mathematica Bohemica
%D 2004
%P 273-282
%V 129
%N 3
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2004.134148/
%R 10.21136/MB.2004.134148
%G en
%F 10_21136_MB_2004_134148

[1] C. Berge: Graphs. Second revised edition, North-Holland, 1985. | MR | Zbl

[2] G. Chartrand, L. Lesniak: Graphs and Digraphs. Third edition, Chapman and Hall, London, 1996. | MR

[3] C. Croitoru, E. Suditu: Perfect stables in graphs. Inf. Process. Lett. 17 (1983), 53–56. | DOI | MR

[4] P. Hall: On representatives of subsets. J. London Math. Soc. 10 (1935), 26–30. | Zbl

[5] G. Hopkins, W. Staton: Graphs with unique maximum independent sets. Discrete Math. 57 (1985), 245–251. | DOI | MR

[6] D. König: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math. Ann. 77 (1916), 453–465. | DOI | MR

[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

[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

[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 | MR

[13] L. Volkmann: Minimale und unabhängige minimale Überdeckungen. An. Univ. Bucur. Mat. 37 (1988), 85–90. | MR

Cité par Sources :