Details

Independent mutual-visibility sets and distance edge-critical graphs
ID Tian, Jing (Author), ID Bujtás, Csilla (Author), ID Klavžar, Sandi (Author)

.pdfPDF - Presentation file, Download (517,24 KB)
MD5: 1452199D10B9E3BB6B936C2EFA675307
URLURL - Source URL, Visit https://opuscula.agh.edu.pl/archives/vol-46-2026/vol-5/7/ This link opens in a new window

Abstract
In this paper, connections between independent sets and the variety of mutual-visibility sets are studied. It is proved that every outer mutual-visibility set of a graph is independent if and only if the graph is distance edge-critical. Several constructions yielding distance edge-critical graphs are given. Graphs in which every independent set is a total mutual-visibility or a dual mutual-visibility set are characterized, as well as graphs in which every total mutual-visibility set is independent. Along the way the total mutual-visibility number of some graphs derived from fullerenes is determined. Diameter four graphs in which every independent set is a mutual-visibility set are characterized. It is proved that determining the maximum cardinality of an independent mutual-visibility set and deciding whether it equals the independence number of a graph are NP-hard problems, and the same is true for independent total, outer and dual mutual-visibility sets.

Language:English
Keywords:mutual-visibility set, independent set, distance edge-critical graph, dense diamond graph, computational complexity
Work type:Article
Typology:1.01 - Original Scientific Article
Organization:FMF - Faculty of Mathematics and Physics
Publication status:Published
Publication version:Version of Record
Year:2026
Number of pages:Str. 773-790
Numbering:Vol. 46, no. 5
PID:20.500.12556/RUL-190769 This link opens in a new window
UDC:519.17
ISSN on article:1232-9274
DOI:10.7494/OpMath.202609091 This link opens in a new window
COBISS.SI-ID:303687171 This link opens in a new window
Publication date in RUL:03.11.2026
Views:119
Downloads:19
Metadata:XML DC-XML DC-RDF
:
Copy citation
Share:Bookmark and Share

Record is a part of a journal

Title:Rocznik Akademii Górniczo-Hutniczej im. Stanisława Staszica : Opuscula Mathematica
Shortened title:Rocz. Akad. Gór.-Hut. im. Stanisława Staszica, Opusc. Math.
Publisher:AGH University of Science and Technology Press
ISSN:1232-9274
COBISS.SI-ID:16179545 This link opens in a new window

Licences

License:CC BY 4.0, Creative Commons Attribution 4.0 International
Link:http://creativecommons.org/licenses/by/4.0/
Description:This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

Language:Slovenian
Keywords:množica vzajemne vidnosti, neodvisna množica, razdaljno povezavno-kritični grafi, graf diamant, računska zahtevnost

Projects

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:P1-0297
Name:Teorija grafov

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:N1-0285
Name:Metrični problemi v grafih in hipergrafih

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:N1-0355
Name:Prirejanja, transverzale in hipergrafi

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:N1-0431
Name:Dominacija v grafih: kubični grafi, produkti in igre

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:J1-70045
Name:Splošna lega in vidnost v teoriji grafov

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Back