Clique-transversal sets in cubic graphs

Zuosong Liang, Erfang Shan, Edwin Tai Chiu Cheng

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

6 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 τcG) for cubic graphs, and characterize the extremal cubic graphs achieving the lower bound. In addition, we present a sharp upper bound on τc(G) for claw-free cubic graphs.
Original languageEnglish
Title of host publicationCombinatorics, Algorithms, Probabilistic and Experimental Methodologies - First International Symposium, ESCAPE 2007, Revised Selected Papers
Pages107-115
Number of pages9
Publication statusPublished - 1 Dec 2007
Event1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, ESCAPE 2007 - Hangzhou, China
Duration: 7 Apr 20079 Apr 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4614 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, ESCAPE 2007
Country/TerritoryChina
CityHangzhou
Period7/04/079/04/07

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)
  • Biochemistry, Genetics and Molecular Biology(all)
  • Theoretical Computer Science

Cite this