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 (print)
1611-3349 (online)
Appears in Collections:Conference Paper

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

SCOPUSTM   
Citations

3
Citations as of Apr 30, 2016

Page view(s)

98
Last Week
45
Last month
Checked on Apr 23, 2017

Google ScholarTM

Check



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