Some results on the independence number of connected domination critical graphs

Pawaton Kaemawichanurat, Thiradet Jiarasuksakun · AKCE International Journal of Graphs and Combinatorics · 2017

A 𝑘-𝛾𝑐-critical graph is a graph 𝐺 with connected domination number 𝛾𝑐⁡(𝐺)=𝑘 and 𝛾𝑐⁢(𝐺+𝑢⁢𝑣)<𝑘 for any pair of non-adjacent vertices 𝑢 and 𝑣 of 𝐺. Let 𝜔 and 𝛼 be respectively the clique number and the independence number of a graph. In this paper, we prove that every 𝑘-𝛾𝑐-critical graph satisfies 𝛼+𝜔≤𝑛−⌊𝑘2⌋+1 for 1≤𝑘≤3. We also characterize all 3-𝛾𝑐-critical graphs achieving the upper bound. For 𝑘≥4, we show that there are infinitely many 𝑘-𝛾𝑐-critical graphs satisfying 𝛼+𝜔=𝑛−⌊𝑘2⌋+1. Thus, we conclude this paper with an open problem that every 𝑘-𝛾𝑐-critical graph for 𝑘≥4 satisfies 𝛼+𝜔≤𝑛−⌊𝑘2⌋+1.

Read the paper · More papers on PaperTik