Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: On domination in 2-connected cubic graphs. | On domination in 2-connected cubic graphs B. Y. Stodolsky Submitted Mar 26 2007 Accepted Oct 15 2008 Published Oct 20 2008 Mathematics Subject Classihcation 05C69 05C40 Abstract In 1996 Reed proved that the domination number 7 G of every n-vertex graph G with minimum degree at least 3 is at most 3n 8 and conjectured that 7 H pn 3 for every connected 3-regular cubic n-vertex graph H. In 1 this conjecture was disproved by presenting a connected cubic graph G on 60 vertices with 7 G 21 and a sequence Gk 1_1 of connected cubic graphs with limk_1 jV G j 3 69. All the counter-examples however had cut-edges. On the other hand in 2 it was proved that 7 G 4n 11 for every connected cubic n-vertex graph G with at least 10 vertices. In this note we construct a sequence of graphs Gk k_1 of 2-connected tC k1 1 cuuic grapus wmi mk o jv G j 3 78 anc a sequence vTTI i_1 or connected Piitup Tpqnlic Iirl i 41P41 tnr ứQí il i Y2 ynTCí B QTTYU 1 I 1 cuuic grapns wnere ror eacn cq we nave jv Gf j 3 69 1 Introduction A set D of vertices is dominating in a graph G if every vertex of G n D is adjacent to a vertex in D. An arbitrary set A of vertices in a graph G dominates itself and the vertices at distance one from it. The domination number 7 G of a graph G is the minimum size of a dominating set in G. Ore 8 proved that 7 G n 2 for every n-vertex graph without isolated vertices . with Ỗ G 1 . Blank 3 proved that 7 G 2n 5 for every n-vertex graph with Ố G 2. Blank s result was also discovered by McCuaig and Shepherd 6 . Reed 9 proved that 7 G 3n 8 for every n-vertex graphs with Ỗ G 3. All these bounds are best possible. However Reed 9 conjectured that the domination number of each connected 3-regular cubic n-vertex graph is at most n 3 . In 1 this conjecture was disporved by exhibiting a connected cubic graph G on 60 vertices with 7 G 21 and a sequence Gkgk_1 of connected cubic graphs with limk_1 jp G j 3 69. All the counter-examples in 1 had cut-edges. In 2 Reed s upper bound of
