Some Cycle and Star Related Nordhaus-Gaddum Type Relations on Strong Effcient Dominating Sets
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Let G = (V,E) be a simple graph with p vertices and q edges. A subset S of V (G) is called a strong (weak) efficient dominating set of G if for every v in V (G) we have [Ns[v] S] = 1 (resp. [Nw[v] S] = 1), where Ns(v) = { u in V (G) : uv 2 E(G), deg(u) > deg(v)g}. The minimum cardinality of a strong (weak) ecient dominating set of G is called the strong (weak) ecient domination number of G and is denoted by se(G) (we(G)). A graph G is strong ecient if there exists a strong ecient dominating set of G. In this paper, some cycle and star related Nordhaus-Gaddum type relations on strong ecient dominating sets and the number of strong ecient dominating sets are studied.
Abstract
Let G = (V,E) be a simple graph with p vertices and q edges. A subset S of V (G) is called a strong (weak) efficient dominating set of G if for every v in V (G) we have [Ns[v] S] = 1 (resp. [Nw[v] S] = 1), where Ns(v) = { u in V (G) : uv 2 E(G), deg(u) > deg(v)g}. The minimum cardinality of a strong (weak) ecient dominating set of G is called the strong (weak) ecient domination number of G and is denoted by se(G) (we(G)). A graph G is strong ecient if there exists a strong ecient dominating set of G. In this paper, some cycle and star related Nordhaus-Gaddum type relations on strong ecient dominating sets and the number of strong ecient dominating sets are studied.
참고문헌 (12)
- D. W. Bange, "Effcient dominating sets in graphs, Application of Discrete Mathematics", pp.189~199 (1988), SIAM
- G. Chartrand, "Subgraph distances in graphs defined by edge transfers", Discrete Math, 170, pp.63~79 (1997)
- F. Harary, "Graph theory" (1969), Addison-Wesley
- F. Harary, "Effcient and excess domination in graphs", J. Combin. Math. Combin. Comput, 26, pp.83~95 (1998)
- T. W. Haynes, "Fundamentals of domination in graphs" (1998), Marcel Dekker, Inc
- T. W. Haynes, "The complementary product of two graphs", Bull. Inst. Combin. Appl, 51, pp.21~30 (2007)
- N. Meena, "Studies in graph theory-effcient domination and related topics", Ph. D., pp.2013
- K. Murugan, "Some Nordhaus-Gaddum type relation on strong effcient dominating sets", J. New Results Sci, 5(11), pp.4~16 (2016)
- E. Sampathkumar, "Semi-total graphs of a graph I", J. Karnatak Univ. Sci, 18, pp.274~280 (1973)
- E. Sampathkumar, "Strong weak domination and domination balance in a graph", Discrete Math, 161, pp.235~242 (1996)
- D. V. S. S. Sastry, "Graph equations for line graphs, total graphs, middle graphs and quasitotal graphs", Discrete Math, 48, pp.113~119 (1984)
- H. Whitney, "Congruent graphs and the connectivity graphs", Amer. J. Math, 54, pp.150~168 (1932)