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