ON BOUNDS AND EXACT VALUES OF k-EFFICIENT DOMINATION NUMBER OF A GRAPH
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
In a graph G with vertex set V and edge set E, a set S ⊆ V is an efficient dominating set if every vertex of G is dominated exactly once by the vertices of S. As a generalization of this concept, k-efficient domination is introduced. A set S is a k-efficient dominating set if there is a partition of V which is a collection of i-neighbourhoods of vertices of S, where i’s vary between 0 and k. The minimum cardinality of a k-efficient dominating set is the k-efficient domination number of G, denoted by εₖ(G). In this paper, some bounds on εₖ(G) and exact values of ε₁(G) are obtained for products of paths and cycles.
Abstract
In a graph G with vertex set V and edge set E, a set S ⊆ V is an efficient dominating set if every vertex of G is dominated exactly once by the vertices of S. As a generalization of this concept, k-efficient domination is introduced. A set S is a k-efficient dominating set if there is a partition of V which is a collection of i-neighbourhoods of vertices of S, where i’s vary between 0 and k. The minimum cardinality of a k-efficient dominating set is the k-efficient domination number of G, denoted by εₖ(G). In this paper, some bounds on εₖ(G) and exact values of ε₁(G) are obtained for products of paths and cycles.
참고문헌 (10)
- D. W. Bange, "Efficient dominating sets in graphs", Applications of Discrete Math, 189, pp.189~199 (1988)
- N. Biggs, "Perfect codes in graphs", J. Combin. Theory Ser. B, 15(3), pp.289~296 (1973)
- G. Chartrand, "Introduction to graph theory" (1977), Courier Corporation
- M. Chellali, "k-efficient partitions of graphs", Commun. Comb. Optim, 4(2), pp.109~122 (2019)
- T. T. Chelvam, "Efficient domination in Cartesian products of cycles", Journal of Advanced Research in Pure Math, pp.42~49 (2011)
- T. W. Haynes, "Fundamentals of domination in graphs" (2013), CRC Press
- K. R. Kumar, "Efficient domination in circulant graphs", Discrete Math, 313(6), pp.767~771 (2013)
- M. Livingston, "Perfect dominating sets" (1990), Citeseer
- M. Nandi, "The domination numbers of cylindrical grid graphs", Appl. Math. Comput, 217(10), pp.4879~4889 (2011)
- D. B. West, "Introduction to graph theory, Vol. 2" (2001), Prentice Hall US