zbMATH — the first resource for mathematics

Clique-transversal sets in cubic graphs. (English) Zbl 1176.05059
Chen, Bo (ed.) et al., Combinatorics, algorithms, probabilistic and experimental methodologies. First international symposium, ESCAPE 2007, Hangzhou, China, April 7–9, 2007. Revised selected papers. Berlin: Springer (ISBN 978-3-540-74449-8/pbk). Lecture Notes in Computer Science 4614, 107-115 (2007).
Summary: 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 \(\tau _{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 \(\tau _{c }(G)\) for cubic graphs, and characterize the extremal cubic graphs achieving the lower bound. In addition, we present a sharp upper bound on \(\tau _{c }(G)\) for claw-free cubic graphs.
For the entire collection see [Zbl 1122.68003].

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C35 Extremal problems in graph theory
Full Text: DOI