Clique-transversal number in cubic graphs

Erfang Shan, Liang Zuosong, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 Citations (Scopus)

Abstract

A clique-transversal set S of a graph G is a set of vertices of G such that S 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 an upper bound and a lower bound on τC(G) for a connected cubic graph G and characterize the extremal cubic graphs achieving the lower bound. Also, we show that every connected claw-free cubic graph G is weakly 2-colorable, this implies that it has clique-transversal number at most one-half its order.
Original languageEnglish
Pages (from-to)115-124
Number of pages10
JournalDiscrete Mathematics and Theoretical Computer Science
Volume10
Issue number2
Publication statusPublished - 16 Jul 2008

Keywords

  • Claw-free
  • Clique-transversal number
  • Cubic graph

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Computational Mathematics

Cite this