Locating-total dominating sets in twin-free graphs: a conjecture (Q311495)

Summary: 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) \cap D \neq N(v) \cap 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 \(\gamma_t^L(G)\), is the minimum cardinality of a locating-total dominating set in \(G\). It is well-known that every connected graph of order \(n \geqslant 3\) has a total dominating set of size at most \(\frac{2}{3}n\). We conjecture that if \(G\) is a twin-free graph of order \(n\) with no isolated vertex, then \(\gamma_t^L(G) \leqslant \frac{2}{3}n\). 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 \(\gamma_t^L(G) \leqslant \frac{3}{4}n\).