Monitoring-edge-geodetic sets in product networks

Abstract

Let G be a graph with vertex set $V(G)$ and edge set $E(G)$. For any $e\in E(G)$ and $u,v\in V(G)$, the edge e is monitored by two vertices u and v in graph G if $d_G(u,v)\ne d_{G-e}(u,v)$. A set M of vertices of G is a monitoring-edge-geodetic set of G if for any edge $e\in E(G)$ there exists a pair $u,v\in M$ such that e is monitored by u, v. The monitoring-edge-geodetic number $\mathrm{meg}(G)$ is the cardinality of the minimum MEG-set in G. In this paper, we obtain the exact values or bounds for the MEG numbers of graph products, including join, corona, cluster, lexicographic products and direct products.

KEYWORDS:

• Distance
• monitoring-edge-geodetic set
• monitoring-edge-geodetic number
• metric dimension
• graph product

2020 AMS SUBJECT CLASSIFICATIONS:

• 05D10
• 05D40
• 05C80

Acknowledgments

The author thanks the anonymous referee for many helpful comments and correcting errors in the paper.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

Supported by the National Science Foundation of China (No. 12061059) and the Qinghai Key Laboratory of Internet of Things Project (2017-ZJ-Y21).