Mutual d-visibility in Graphs

Autor segons l'article: Kuziak, Dorota; Montejano, Luis P; Rodriguez-Velazquez, Juan A

Departament: Enginyeria Informàtica i Matemàtiques

Autor/s de la URV: Rodríguez Velázquez, Juan Alberto

Paraules clau: <italic>d</italic>-mutual-visibility number; <italic>d</italic>-mutual-visibility set; D-mutual-visibility number; D-mutual-visibility set; Dissociation number; Mutual visibility; Packing number; Product graph; Product graphs

Resum: Let d be a positive integer. The mutual d-visibility number mu d(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mu d}(G)$$\end{document} of a graph G is introduced as the cardinality of the largest mutual d-visibility set. That is, X subset of V(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X\subseteq V(G)$$\end{document} is a mutual d-visibility set if for any pair of vertices x,y is an element of X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x,y\in X$$\end{document}, the distance between them is larger than d, or there exists a shortest x, y-path in G whose internal vertices are not in X. Several combinatorial and computational aspects of mu d(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mu d}(G)$$\end{document} are given in this work. Finally, the NP-completeness of the decision problem concerning finding mu d(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mu d}(G)$$\end{document} is proved.

Àrees temàtiques: Applied mathematics; Economia; Ensino; Matemática / probabilidade e estatística; Mathematics; Mathematics (miscellaneous); Mathematics, applied

Accès a la llicència d'ús: https://creativecommons.org/licenses/by/3.0/es/

Adreça de correu electrònic de l'autor: juanalberto.rodriguez@urv.cat

Data d'alta del registre: 2025-08-02

Versió de l'article dipositat: info:eu-repo/semantics/publishedVersion

Enllaç font original: https://link.springer.com/article/10.1007/s00025-025-02450-1

Referència a l'article segons font original: Results In Mathematics. 80 (5): 130-

Referència de l'ítem segons les normes APA: Kuziak, Dorota; Montejano, Luis P; Rodriguez-Velazquez, Juan A (2025). Mutual d-visibility in Graphs. Results In Mathematics, 80(5), 130-. DOI: 10.1007/s00025-025-02450-1

URL Document de llicència: https://repositori.urv.cat/ca/proteccio-de-dades/

DOI de l'article: 10.1007/s00025-025-02450-1

Entitat: Universitat Rovira i Virgili

Any de publicació de la revista: 2025

Tipus de publicació: Journal Publications