Monitoreo de los bordes de un grafo utilizando distancias con una longitud de ciclo dada

Para un conjunto de vértices M y un borde uv de un grafo G, si existe un vértice x∈M tal que dG(x,u)≠dG−uv(x,u) o dG(x,v)≠dG−uv(x,v), entonces uv es monitoreado por x. Un conjunto de vértices M del grafo G es un conjunto de monitoreo de bordes por distancia (conocido como conjunto DEM) si todos los bordes e∈E(G) son monitoreados por algunos vértices de M. El número de monitoreo de bordes por distancia dem(G) de un grafo G se define como la cardinalidad mínima de un conjunto DEM de G. En este artículo, demostramos que dem(G)≤n−⌊g(G)/2⌋ para un grafo conectado G, que no es un árbol, de orden n, donde g(G) (g abreviado) es la longitud de un ciclo más corto en G. Además, la igualdad se sostiene si y solo si G es un ciclo C4 o un grafo completo Kn (n≥3). Sea Gk,g la clase de grafos conectados con número DEM k y longitud de ciclo g. Para cualquier G∈Gk,g, tenemos |V(G)|≥k+⌊g(G)/2⌋. Además, la igualdad se sostiene si y solo si g(G)=3 y k=n−1 o g(G)=4 y k=2. Además, existe un grafo G∈Gk,g tal que |V(G)| puede ser arbitrariamente grande. También damos la relación entre dem(G) y |V(G)| para g(G)≥5, es decir, dem(G)≤2n/5. Finalmente, sugerimos algunos límites y grafos extremales relacionados para |E(G)|, donde G∈Gk,g.