# Topics on Domination by S. T. Hedetniemi

By S. T. Hedetniemi

The contributions during this quantity are divided into 3 sections: theoretical, new versions and algorithmic. the 1st part makes a speciality of homes of the normal domination quantity &ggr;(G), the second one part is worried with new diversifications at the domination subject matter, and the 3rd is essentially taken with discovering periods of graphs for which the domination quantity (and numerous different domination-related parameters) might be computed in polynomial time.

Similar mathematics books

The Mathematics of Paul Erdos II (Algorithms and Combinatorics 14)

This is often the main complete survey of the mathematical lifetime of the mythical Paul Erd? s, probably the most flexible and prolific mathematicians of our time. For the 1st time, all of the major parts of Erd? s' study are lined in one undertaking. due to overwhelming reaction from the mathematical group, the undertaking now occupies over 900 pages, prepared into volumes.

Extra resources for Topics on Domination

Sample text

Conjecture of Berge-Duchet [3]). Is it true that (7) j (8)? (Perfect Graph Conjecture). Is it true that (6) j (8)? (Weak form of the Perfect Graph Conjecture). Is it true that the odd circuits are the only connected kernless graphs such that the removal of any arc results in a graph with a kernel? (Conjecture of Duchet, [91) References [l] C. Berge, Graphs, North-Holland Mathematical Library, Vol. 6 (North-Holland, Amsterdam, 1985) Chapter 14. [2] C. Berge, Nouvelles extensions du noyau d‘un graphe et ses applications en theorie des jeux, Publ.

The graph H obtained by removing two adjacent edges from C,, consists of an isolated vertex and a path of order n - 1. Thus, a ( H ) = 1 + a(P,,-,) = 1 + [(n - 1)/3] = 1 + [n/3] = 1 + a(C,,), whence b(C,,)S 2 in this case. Combining this with the upper bound obtained earlier, we have b(C,,) = 2 if n = 0, 2 (mod 3). Case 2. Suppose now that n = 1(mod 3). The graph H resulting from the deletion of three consecutive edges of C,, consists of two isolated vertices and a path of order n - 2. Thus, + [ ( n - 2)/3] = 2 + (n - 1)/3 = 2 + ( I d 3 1 - 1) = 1 + ~(c,,), a ( H )= 2 so that b(C,,)S 3.

If b ( G )S deg u, then b (G) s p - 1, so we suppose that b (G) > deg u. Let Eu denote the set of edges incident with u. Then a(G - E,) = a(G) and a(G - u ) = a(G) - 1. Also, if D denotes the union of all minimum dominating sets for G - u , then u is adjacent in G to no vertex of D . Hence, JE,(s p - 1 - (Dl and v t\$ D . Now, if F, denotes the set of edges from v to a vertex in D , then since u t\$ D we must have a(G - u - F , ) > a(G - u ) , or equivalently, a(G - u - F , ) > a(G) - 1. Thus a((; - (E, U 4))> a(G) and we see that b ( G )S IEU u F,I = lEUl+ lFvl S ( p - 1 - IDl)+ ID1 = p - 1.