Acta mathematica scientia,Series A

• Articles • Previous Articles     Next Articles

Independence Number in Claw-free Cubic Graphs

Wang Chunxiang   

  1. (Department of Mathematics, Huazhong Normal University, Wuhan 430079)
  • Received:2006-06-21 Revised:2007-09-20 Online:2009-02-25 Published:2009-02-25
  • Contact: Wang Chunxiang

Abstract: 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\{x} with x∈ 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 γ(G) (the upper domination number Γ(G)) is the minimum (maximum) cardinality of a minimal dominating set of G. In this paper, we prove that: (1) if G ∈ R and G is a cubic graph of order n, then γ(G)=i(G), β(G)=n/3; (2) for every connected claw-free cubic graph G of order n, if G(G≠ K4) contains no K4-e as induced subgraph, then β(G)=n/3.

Key words: Cubic graph, The domination number, The independence number, Colouring.

CLC Number: 

  • 05C
Trendmd