Domination and location in acyclic graphs

Networks - Tập 17 Số 1 - Trang 55-64 - 1987
Peter J. Slater1
1Univ. of Alabama in Huntsville, Huntsville#TAB#

Tóm tắt

AbstractLocating‐dominating sets are of interest in safeguard applications of graphical models of facilities. A subset S of the vertex set V of a graph G is a dominating set if each vertex u ϵ V ‐ S is adjacent to at least one vertex in S. For each v in V ‐ S let S(v) denote the set of vertices in S which are adjacent to v. A dominating set S is defined to be “locating” if for any two vertices v and w in V ‐ S one has S(v) ≠ S(w). Sharp bounds on the cardinality of locating‐dominating sets for arbitrary graphs on p vertices and for trees on p vertices are given, and a linear (that is O(P)) algorithm for finding a minimum cardinality locating‐dominating set in an acyclic graph is presented.

Từ khóa


Tài liệu tham khảo

10.1016/0020-0190(75)90011-3

10.1002/net.3230070305

10.21236/AD0705364

Harary F., 1976, The metric basis of a graph, Ars Combinatoria, 2, 191

10.2172/5313603

Hulme B. L., 1982, Computing Minimum Cost Fire Protection. SAND82–0809

Hulme B. L., A Boolean algebraic analysis of fire protection, Ann. Discrete Math.

Knuth D. E., 1968, Fundamental Algorithms, 334

Ore O., 1962, Theory of Graphs, Amer. Math. Soc. Colloq. Publ., 38

P. J.Slater Leaves of tree. Proc. of the Sixth S. E. Conf. on Combinatorics Graph Theory and Computing Utilitas Math. (1975)549–559.

10.1145/321958.321964

P. J.Slater Dominating and reference sets in a graph. To appear.

10.1137/0201010

Thông tin
Thông tin xuất bản

Networks

Tập 17 Số 1

55-64

Thông tin tác giả