tailieunhanh - Báo cáo toán học: "A new bound on the domination number of graphs with minimum degree two"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: A new bound on the domination number of graphs with minimum degree two. | A new bound on the domination number of graphs with minimum degree two 1Michael A. Henning 2Ingo Schiermeyer and 3Anders Yeo department of Mathematics University of Johannesburg Auckland Park 2006 South Africa mahenning@ 2Diskrete Mathematik TU Bergakademie Freiberg Institut fur Diskrete Mathematik und Algebra 09596 Freiberg Germany schierme@ department of Computer Science Royal Holloway University of London Egham Surrey TW20 OEX UK anders@ Submitted Apr 30 2009 Accepted Dec 18 2010 Published Jan 5 2011 Mathematics Subject Classification 05C69 Abstract For a graph G let y G denote the domination number of G and let ỗ G denote the minimum degree among the vertices of G. A vertex x is called a bad-cut-vertex of G if G x contains a component Cx which is an induced 4-cycle and x is adjacent to at least one but at most three vertices on Cx. A cycle C is called a special-cycle if C is a 5-cycle in G such that if u and v are consecutive vertices on C then at least one of u and v has degree 2 in G. We let bc G denote the number of bad-cut-vertices in G and sc G the maximum number of vertex disjoint special-cycles in G that contain no bad-cut-vertices. We say that a graph is C4 C5 -free if it has no induced 4-cycle or 5-cycle. Bruce Reed 14 showed that if G is a graph of order n with ỗ G 3 then y G 3n 8. In this paper we relax the minimum degree condition from three to two. Let G be a connected graph of order n 14 with ỗ G 2. As Research supported in part by the South African National Research Foundation THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P12 1 an application of Reed s result we show that y G 1 3n sc G bc G . As a consequence of this result we have that i y G 2n 5 ii if G contains no special-cycle and no bad-cut-vertex then y G 3n 8 iii if G is C4 C5 -free then y G 3n 8 iv if G is 2-connected and dG u dG v 5 for every two adjacent vertices u and v then y G 3n 8. All bounds are sharp. Keywords bounds cycles domination .