Clique-transversal number in cubic graphs

Erfang Shan; Liang Zuosong; Edwin Tai Chiu Cheng

Clique-transversal number in cubic graphs

Erfang Shan, Liang Zuosong, Edwin Tai Chiu Cheng

Research output: Journal article publication › Journal article › Academic research › peer-review

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 language	English
Pages (from-to)	115-124
Number of pages	10
Journal	Discrete Mathematics and Theoretical Computer Science
Volume	10
Issue number	2
Publication status	Published - 16 Jul 2008

Keywords

Claw-free
Clique-transversal number
Cubic graph

ASJC Scopus subject areas

Computer Science (miscellaneous)
Computational Mathematics

Cite this

@article{11493028eba7482aadd98852ab67c4f6,

title = "Clique-transversal number in cubic graphs",

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.",

keywords = "Claw-free, Clique-transversal number, Cubic graph",

author = "Erfang Shan and Liang Zuosong and Cheng, {Edwin Tai Chiu}",

year = "2008",

month = jul,

day = "16",

language = "English",

volume = "10",

pages = "115--124",

journal = "Discrete Mathematics and Theoretical Computer Science",

issn = "1462-7264",

publisher = "Maison de l'informatique et des mathematiques discretes",

number = "2",

}

TY - JOUR

T1 - Clique-transversal number in cubic graphs

AU - Shan, Erfang

AU - Zuosong, Liang

AU - Cheng, Edwin Tai Chiu

PY - 2008/7/16

Y1 - 2008/7/16

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 τ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.

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 τ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.

KW - Claw-free

KW - Clique-transversal number

KW - Cubic graph

UR - http://www.scopus.com/inward/record.url?scp=46949084545&partnerID=8YFLogxK

M3 - Journal article

SN - 1462-7264

VL - 10

SP - 115

EP - 124

JO - Discrete Mathematics and Theoretical Computer Science

JF - Discrete Mathematics and Theoretical Computer Science

IS - 2

ER -

Clique-transversal number in cubic graphs

Abstract

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this