On perfect and unique maximum independent sets in graphs

Lutz Volkmann

Mathematica Bohemica (2004)

  • Volume: 129, Issue: 3, page 273-282
  • ISSN: 0862-7959

Abstract

top
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 ' of G with | I ' | ≥ | 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 .

How to cite

top

Volkmann, Lutz. "On perfect and unique maximum independent sets in graphs." Mathematica Bohemica 129.3 (2004): 273-282. <http://eudml.org/doc/249397>.

@article{Volkmann2004,
abstract = {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$.},
author = {Volkmann, Lutz},
journal = {Mathematica Bohemica},
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},
language = {eng},
number = {3},
pages = {273-282},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On perfect and unique maximum independent sets in graphs},
url = {http://eudml.org/doc/249397},
volume = {129},
year = {2004},
}

TY - JOUR
AU - Volkmann, Lutz
TI - On perfect and unique maximum independent sets in graphs
JO - Mathematica Bohemica
PY - 2004
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 129
IS - 3
SP - 273
EP - 282
AB - 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$.
LA - eng
KW - 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
UR - http://eudml.org/doc/249397
ER -

References

top
  1. Graphs, Second revised edition, North-Holland, 1985. (1985) Zbl0566.05001MR0809587
  2. Graphs and Digraphs, Third edition, Chapman and Hall, London, 1996. (1996) MR1408678
  3. 10.1016/0020-0190(83)90091-1, Inf. Process. Lett. 17 (1983), 53–56. (1983) MR0724697DOI10.1016/0020-0190(83)90091-1
  4. On representatives of subsets, J. London Math. Soc. 10 (1935), 26–30. (1935) Zbl0010.34503
  5. 10.1016/0012-365X(85)90177-3, Discrete Math. 57 (1985), 245–251. (1985) MR0816813DOI10.1016/0012-365X(85)90177-3
  6. 10.1007/BF01456961, Math. Ann. 77 (1916), 453–465. (1916) MR1511872DOI10.1007/BF01456961
  7. Graphs and matrices, Math. Fiz. Lapok 38 (1931), 116–119. (Hungarian) (1931) 
  8. Theorie der endlichen und unendlichen Graphen, Akademische Verlagsgesellschaft, Leipzig, 1936; reprinted: Teubner-Archiv zur Mathematik, Band 6, Leipzig, 1986. (1986) MR0886676
  9. Der Census räumlicher Complexe oder Verallgemeinerungen des Eulerschen Satzes von den Polyedern, Göttinger Abhandlungen 10 (1862). (1862) 
  10. 10.1007/BF01894789, Acta Math. Acad. Sci. Hung. 21 (1970), 443–446. (1970) DOI10.1007/BF01894789
  11. Matching Theory, Ann. Discrete Math. 29, North-Holland, 1986. (1986) 
  12. 10.1016/0012-365X(94)90389-1, Discrete Math. 131 (1994), 279–285. (1994) MR1287738DOI10.1016/0012-365X(94)90389-1
  13. Minimale und unabhängige minimale Überdeckungen, An. Univ. Bucur. Mat. 37 (1988), 85–90. (1988) MR0993604

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.