On domination and independent domination numbers of a graph

✍ Scribed by Robert B. Allan; Renu Laskar

• Publisher: Elsevier Science
• Year: 1978
• Tongue: English
• Weight: 399 KB
• Volume: 23
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(78)90105-x

✦ Synopsis

For a graph G, the definitions of doknation number, denoted y(G), and independent domination number, denoted i(G), are given, and the following results are obtained: oorollrrg 1. For any graph G, y(L(G)) = i@(G)), where Z,(G) is the line graph of G. (This $xh!s t.lic rtsult ~(L(T))~i(L(T)), h w ere T is a tree. Hedetoiemi and Mitchell, S. E. Conf. B.awn .Roue, 1977.) OyroRaq 2. For any Graph G, y(M(G)) = 104(G)), where A4 is tFil. middle graph of G. In this paper we shall consider a graph G = (V, E) as fmite, undirected, with no multiple e:dges, arsd with no loops. Al1 definitions not presented here can be foun,d in [3]. 0.1 A number of terms to be &d are defined for a given graph G = (V, E), where V={q, 2)2,. . . , UP}. DerGnition 1. A set D E V is a domimting set (of G), if Vu E V-D, N(v) n Df 8. DefhutIon 2. A set Ic V is an independent set (of G), if Vu, v E I, N(u) n (v} = pl. Dt&Mon 3. .4 set Ic V is an independent domination set (of G) if I is both a.n independent and dominating set. 0.2 The following are two useful results which can bc found in [63 and [l] respectively.