| Summary: | A graph <i>G</i> is said to be <i>k</i>-<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>γ</mi><mi>c</mi></msub></semantics></math></inline-formula>-critical if the connected domination 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> is equal to <i>k</i> and <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><mi>u</mi><mi>v</mi><mo>)</mo></mrow><mo><</mo><mi>k</mi></mrow></semantics></math></inline-formula> for any pair of non-adjacent vertices <i>u</i> and <i>v</i> of <i>G</i>. Let <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>ζ</mi></semantics></math></inline-formula> be the number of cut vertices of <i>G</i> and let <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>ζ</mi><mn>0</mn></msub></semantics></math></inline-formula> be the maximum number of cut vertices that can be contained in one block. For an integer <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>ℓ</mo><mo>≥</mo><mn>0</mn></mrow></semantics></math></inline-formula>, a graph <i>G</i> is <i>ℓ</i>-factor critical if <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>−</mo><mi>S</mi></mrow></semantics></math></inline-formula> has a perfect matching for any subset <i>S</i> of vertices of size <i>ℓ</i>. It was proved by Ananchuen in 2007 for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>=</mo><mn>3</mn></mrow></semantics></math></inline-formula>, Kaemawichanurat and Ananchuen in 2010 for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>=</mo><mn>4</mn></mrow></semantics></math></inline-formula> and by Kaemawichanurat and Ananchuen in 2020 for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>≥</mo><mn>5</mn></mrow></semantics></math></inline-formula> that every <i>k</i>-<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>γ</mi><mi>c</mi></msub></semantics></math></inline-formula>-critical graph has at most <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>−</mo><mn>2</mn></mrow></semantics></math></inline-formula> cut vertices and the graphs with maximum number of cut vertices were characterized. In 2020, Kaemawichanurat and Ananchuen proved further that, for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>≥</mo><mn>4</mn></mrow></semantics></math></inline-formula>, every <i>k</i>-<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>γ</mi><mi>c</mi></msub></semantics></math></inline-formula>-critical graphs satisfies the inequality <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>ζ</mi><mn>0</mn></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>≤</mo><mo movablelimits="true" form="prefix">min</mo><mfenced separators="" open="{" close="}"><mfenced separators="" open="⌊" close="⌋"><mfrac><mrow><mi>k</mi><mo>+</mo><mn>2</mn></mrow><mn>3</mn></mfrac></mfenced><mo>,</mo><mi>ζ</mi></mfenced></mrow></semantics></math></inline-formula>. In this paper, we characterize all <i>k</i>-<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>γ</mi><mi>c</mi></msub></semantics></math></inline-formula>-critical graphs having <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>−</mo><mn>3</mn></mrow></semantics></math></inline-formula> cut vertices. Further, we establish realizability that, for given <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>≥</mo><mn>4</mn></mrow></semantics></math></inline-formula>, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>2</mn><mo>≤</mo><mi>ζ</mi><mo>≤</mo><mi>k</mi><mo>−</mo><mn>2</mn></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>2</mn><mo>≤</mo><msub><mi>ζ</mi><mn>0</mn></msub><mo>≤</mo><mo movablelimits="true" form="prefix">min</mo><mfenced separators="" open="{" close="}"><mfenced separators="" open="⌊" close="⌋"><mfrac><mrow><mi>k</mi><mo>+</mo><mn>2</mn></mrow><mn>3</mn></mfrac></mfenced><mo>,</mo><mi>ζ</mi></mfenced></mrow></semantics></math></inline-formula>, there exists a <i>k</i>-<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>γ</mi><mi>c</mi></msub></semantics></math></inline-formula>-critical graph with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>ζ</mi></semantics></math></inline-formula> cut vertices having a block which contains <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>ζ</mi><mn>0</mn></msub></semantics></math></inline-formula> cut vertices. Finally, we proved that every <i>k</i>-<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>γ</mi><mi>c</mi></msub></semantics></math></inline-formula>-critical graph of odd order with minimum degree two is 1-factor critical if and only if <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>1</mn><mo>≤</mo><mi>k</mi><mo>≤</mo><mn>2</mn></mrow></semantics></math></inline-formula>. Further, we proved that every <i>k</i>-<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>γ</mi><mi>c</mi></msub></semantics></math></inline-formula>-critical <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>K</mi><mrow><mn>1</mn><mo>,</mo><mn>3</mn></mrow></msub></semantics></math></inline-formula>-free graph of even order with minimum degree three is 2-factor critical if and only if <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>1</mn><mo>≤</mo><mi>k</mi><mo>≤</mo><mn>2</mn></mrow></semantics></math></inline-formula>.
|
|---|