| 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 |
| . |
