Abstract
A total dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D. A locating-total dominating set of G is a total dominating set D of G with the additional property that every two distinct vertices outside D have distinct neighbors in D; that is, for distinct vertices u and v outside D, N(u) ∩ D ≠ N(v) ∩ D where N(u) denotes the open neighborhood of u. A graph is twin-free if every two distinct vertices have distinct open and closed neighborhoods. The location-total domination number of G, denoted γ L t (G), is the minimum cardinality of a locating-total dominating set in G. It is well-known that every connected graph of order n ≥ 3 has a total dominating set of size at most 2/3;n. We conjecture that if G is a twin-free graph of order n with no isolated vertex, then γL t (G) ≤ 2/3n. We prove the conjecture for graphs without 4-cycles as a subgraph. We also prove that if G is a twin-free graph of order n, then γL t (G) ≤ 3/4n.
Original language | English |
---|---|
Journal | Electronic Journal of Combinatorics |
Volume | 23 |
Issue number | 3 |
DOIs | |
Publication status | Published - 2016 |
Keywords
- Dominating sets
- Locating-dominating sets
- Total dominating sets
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics