Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/14529
Title: Clique-transversal sets in cubic graphs
Authors: Liang, Z
Shan, E
Cheng, TCE 
Keywords: Bound
Claw-free
Clique-transversal number
Cubic graph
Issue Date: 2007
Publisher: Springer
Source: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics), 2007, v. 4614 LNCS, p. 107-115 How to cite?
Journal: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics) 
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.
Description: 1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, ESCAPE 2007, Hangzhou, 7-9 April 2007
URI: http://hdl.handle.net/10397/14529
ISBN: 9783540744498
ISSN: 0302-9743
EISSN: 1611-3349
Appears in Collections:Conference Paper

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

5
Citations as of May 16, 2017

Page view(s)

120
Last Week
1
Last month
Checked on Aug 20, 2017

Google ScholarTM

Check



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.