Some results on the independence number of connected domination critical graphs

บทความในวารสาร

ผู้เขียน/บรรณาธิการ

กลุ่มสาขาการวิจัยเชิงกลยุทธ์

ไม่พบข้อมูลที่เกี่ยวข้อง

รายละเอียดสำหรับงานพิมพ์

รายชื่อผู้แต่ง: Kaemawichanurat P., Jiarasuksakun T.

ผู้เผยแพร่: Kalasalingam University

ปีที่เผยแพร่ (ค.ศ.): 2018

Volume number: 15

Issue number: 2

หน้าแรก: 190

หน้าสุดท้าย: 196

จำนวนหน้า: 7

นอก: 0972-8600

eISSN: 0972-8600

URL: https://www.scopus.com/inward/record.uri?eid=2-s2.0-85030476239&doi=10.1016%2fj.akcej.2017.09.004&partnerID=40&md5=897b3b4a0f2bc98004290beb51e3673c

ภาษา: English-Great Britain (EN-GB)

ดูในเว็บของวิทยาศาสตร์ | ดูบนเว็บไซต์ของสำนักพิมพ์ | บทความในเว็บของวิทยาศาสตร์

บทคัดย่อ

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

คำสำคัญ

Clique number, Connected domination, Domination, Independence number, γc-critical graphs