Common Independence in Graphs
The cardinality of a largest independent set of <i>G</i>, denoted by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>α</mi><mo>(</mo><mi>G</mi><mo>...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-08-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-8994/13/8/1411 |
| _version_ | 1797522019780132864 |
|---|---|
| author | Magda Dettlaff Magdalena Lemańska Jerzy Topp |
| author_facet | Magda Dettlaff Magdalena Lemańska Jerzy Topp |
| author_sort | Magda Dettlaff |
| collection | DOAJ |
| description | The cardinality of a largest independent set of <i>G</i>, denoted by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>α</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula>, is called the independence number of <i>G</i>. The independent domination number <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>i</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> of a graph <i>G</i> is the cardinality of a smallest independent dominating set of <i>G</i>. We introduce the concept of the <i>common independence number</i> of a graph <i>G</i>, denoted by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>α</mi><mi>c</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, as the greatest integer <i>r</i> such that every vertex of <i>G</i> belongs to some independent subset <i>X</i> of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>V</mi><mi>G</mi></msub></semantics></math></inline-formula> with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>|</mo><mi>X</mi><mo>|</mo><mo>≥</mo><mi>r</mi></mrow></semantics></math></inline-formula>. The common independence number <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>α</mi><mi>c</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> of <i>G</i> is the limit of symmetry in <i>G</i> with respect to the fact that each vertex of <i>G</i> belongs to an independent set of cardinality <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>α</mi><mi>c</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> in <i>G</i>, and there are vertices in <i>G</i> that do not belong to any larger independent set in G. For any graph <i>G</i>, the relations between above parameters are given by the chain of inequalities <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>i</mi><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>≤</mo><msub><mi>α</mi><mi>c</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>≤</mo><mi>α</mi><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>. In this paper, we characterize the trees <i>T</i> for which <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>i</mi><mrow><mo>(</mo><mi>T</mi><mo>)</mo></mrow><mo>=</mo><msub><mi>α</mi><mi>c</mi></msub><mrow><mo>(</mo><mi>T</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, and the block graphs <i>G</i> for which <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>α</mi><mi>c</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>=</mo><mi>α</mi><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>. |
| first_indexed | 2024-03-10T08:20:40Z |
| format | Article |
| id | doaj.art-9af732d735c24421a562f0febd87bd78 |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-03-10T08:20:40Z |
| publishDate | 2021-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-9af732d735c24421a562f0febd87bd782023-11-22T10:01:02ZengMDPI AGSymmetry2073-89942021-08-01138141110.3390/sym13081411Common Independence in GraphsMagda Dettlaff0Magdalena Lemańska1Jerzy Topp2Technical Physics and Applied Mathematics Department, Gdańsk University of Technology, 80-803 Gdańsk, PolandTechnical Physics and Applied Mathematics Department, Gdańsk University of Technology, 80-803 Gdańsk, PolandInstitute of Applied Informatics, The State University of Applied Sciences in Elbla̧g, 82-300 Elbla̧g, PolandThe cardinality of a largest independent set of <i>G</i>, denoted by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>α</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula>, is called the independence number of <i>G</i>. The independent domination number <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>i</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> of a graph <i>G</i> is the cardinality of a smallest independent dominating set of <i>G</i>. We introduce the concept of the <i>common independence number</i> of a graph <i>G</i>, denoted by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>α</mi><mi>c</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, as the greatest integer <i>r</i> such that every vertex of <i>G</i> belongs to some independent subset <i>X</i> of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>V</mi><mi>G</mi></msub></semantics></math></inline-formula> with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>|</mo><mi>X</mi><mo>|</mo><mo>≥</mo><mi>r</mi></mrow></semantics></math></inline-formula>. The common independence number <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>α</mi><mi>c</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> of <i>G</i> is the limit of symmetry in <i>G</i> with respect to the fact that each vertex of <i>G</i> belongs to an independent set of cardinality <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>α</mi><mi>c</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> in <i>G</i>, and there are vertices in <i>G</i> that do not belong to any larger independent set in G. For any graph <i>G</i>, the relations between above parameters are given by the chain of inequalities <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>i</mi><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>≤</mo><msub><mi>α</mi><mi>c</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>≤</mo><mi>α</mi><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>. In this paper, we characterize the trees <i>T</i> for which <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>i</mi><mrow><mo>(</mo><mi>T</mi><mo>)</mo></mrow><mo>=</mo><msub><mi>α</mi><mi>c</mi></msub><mrow><mo>(</mo><mi>T</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, and the block graphs <i>G</i> for which <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>α</mi><mi>c</mi></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>=</mo><mi>α</mi><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>.https://www.mdpi.com/2073-8994/13/8/1411independence numberdomination numberindependence domination numbercommon independence number |
| spellingShingle | Magda Dettlaff Magdalena Lemańska Jerzy Topp Common Independence in Graphs Symmetry independence number domination number independence domination number common independence number |
| title | Common Independence in Graphs |
| title_full | Common Independence in Graphs |
| title_fullStr | Common Independence in Graphs |
| title_full_unstemmed | Common Independence in Graphs |
| title_short | Common Independence in Graphs |
| title_sort | common independence in graphs |
| topic | independence number domination number independence domination number common independence number |
| url | https://www.mdpi.com/2073-8994/13/8/1411 |
| work_keys_str_mv | AT magdadettlaff commonindependenceingraphs AT magdalenalemanska commonindependenceingraphs AT jerzytopp commonindependenceingraphs |