TY - GEN
T1 - Clique-transversal sets in cubic graphs
AU - Liang, Zuosong
AU - Shan, Erfang
AU - Cheng, Edwin Tai Chiu
PY - 2007/12/1
Y1 - 2007/12/1
N2 - 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.
AB - 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.
KW - Bound
KW - Claw-free
KW - Clique-transversal number
KW - Cubic graph
UR - http://www.scopus.com/inward/record.url?scp=38048999941&partnerID=8YFLogxK
M3 - Conference article published in proceeding or book
SN - 9783540744498
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 107
EP - 115
BT - Combinatorics, Algorithms, Probabilistic and Experimental Methodologies - First International Symposium, ESCAPE 2007, Revised Selected Papers
T2 - 1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, ESCAPE 2007
Y2 - 7 April 2007 through 9 April 2007
ER -