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
Fingerprint
Dive into the research topics of 'Clique-transversal number in cubic graphs'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver