Garijo, González and Márquez's location-domination conjecture for twin-free graphs

About 11 years old · traced to

A graph is twin-free if every two distinct vertices have distinct open and closed neighborhoods. For a graph GG, a set DD of vertices locates a vertex v∉Dv\notin D if the neighborhood of vv within DD is unique among all vertices in V(G)∖DV(G)\setminus D; a locating-dominating set is a dominating set that locates every vertex outside it. The location-domination number γL(G)\gamma_L(G) 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 n1n_1 such that for any n≥n1n\geq n_1, the maximum value of the location-domination number of a connected twin-free graph of order nn is ⌊n2⌋\lfloor\frac{n}{2}\rfloor.

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

Never refreshed

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.