Garijo, González and Márquez's location-domination conjecture for twin-free graphs
A graph is twin-free if every two distinct vertices have distinct open and closed neighborhoods. For a graph , a set of vertices locates a vertex if the neighborhood of within is unique among all vertices in ; a locating-dominating set is a dominating set that locates every vertex outside it. The location-domination number is the minimum cardinality of a locating-dominating set. The order of a graph is its number of vertices.
Garijo, González and Márquez's conjecture. There exists an integer such that for any , the maximum value of the location-domination number of a connected twin-free graph of order is .
This conjecture asserts that, for sufficiently large connected twin-free graphs, the location-domination number obeys the same one-half-order upper bound as the classical domination number. The source does not give evidence that it has been resolved.
References
Primary source
Florent Foucaud and Michael A. Henning, “Location-domination in line graphs”, arXiv:1506.02623 (2016).
Additional references
2 papers in this index state this conjecture (2015). The statement above is taken from the most recent of them; the others are arXiv:1503.02950.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.