×

Independence number in claw-free cubic graphs. (Chinese. English summary) Zbl 1199.05272

Summary: A set \(X\) is independent if no two vertices of \(X\) are adjacent. A set \(X\) is dominating if \(N[X]=V(G)\). A dominating set \(X\) is minimal if no set \(X\backslash \{x\}\) with \(x\in X\) is dominating. The independence number \(i(G)(\beta(G))\) is the minimum (maximum) cardinality of a maximal independent set of \(G\). The domination number \(\gamma(G)\) (the upper domination number \(\Gamma(G))\) is the minimum (maximum) cardinality of a minimal dominating set of \(G\). In this paper, we prove that:
(1)
if \(G\in \operatorname{Re}\) and \(G\) is a cubic graph of order \(n\), then \(\gamma(G)=i(G)\), \(\beta(G)=n/3\);
(2)
for every connected claw-free cubic graph \(G\) of order \(n\), if \(G\) (\(G\neq K_4\)) contains no \(K_4-e\) as induced subgraph, then \(\beta(G)=n/3\).

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite