Bounds on the clique-transversal number of regular graphs

Erfang Shan, Edwin Tai Chiu Cheng, Liying Kang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

12 Citations (Scopus)

Abstract

A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G. The clique-transversal number, denoted τc(G), is the minimum cardinality of a clique-transversal set in G. In this paper we present the bounds on the clique-transversal number for regular graphs and characterize the extremal graphs achieving the lower bound. Also, we give the sharp bounds on the clique-transversal number for claw-free cubic graphs and we characterize the extremal graphs achieving the lower bound.
Original languageEnglish
Pages (from-to)851-863
Number of pages13
JournalScience in China, Series A: Mathematics
Volume51
Issue number5
DOIs
Publication statusPublished - 1 May 2008

Keywords

  • Claw-free cubic graph
  • Clique-transversal number
  • Clique-transversal set
  • Graph
  • Regular graph

ASJC Scopus subject areas

  • Mathematics(all)

Cite this