Some results on the independence number of connected domination critical graphs
Journal article
Authors/Editors
Strategic Research Themes
No matching items found.
Publication Details
Author list: Kaemawichanurat P., Jiarasuksakun T.
Publisher: Kalasalingam University
Publication year: 2018
Volume number: 15
Issue number: 2
Start page: 190
End page: 196
Number of pages: 7
ISSN: 0972-8600
eISSN: 0972-8600
Languages: English-Great Britain (EN-GB)
View in Web of Science | View on publisher site | View citing articles in Web of Science
Abstract
A k-γc-critical graph is a graph G with connected domination number γc(G)=k and γc(G+uv)<k for any pair of non-adjacent vertices u and v of G. Let ω and α be respectively the clique number and the independence number of a graph. In this paper, we prove that every k-γc-critical graph satisfies α+ω≤n−⌊[Formula presented]⌋+1 for 1≤k≤3. We also characterize all 3-γc-critical graphs achieving the upper bound. For k≥4, we show that there are infinitely many k-γc-critical graphs satisfying α+ω=n−⌊[Formula presented]⌋+1. Thus, we conclude this paper with an open problem that every k-γc-critical graph for k≥4 satisfies α+ω≤n−⌊[Formula presented]⌋+1. © 2017 Kalasalingam University
Keywords
Clique number, Connected domination, Domination, Independence number, γc-critical graphs
Contact Information