Your browser does not allow JavaScript!
JavaScript is necessary for the proper functioning of this website. Please enable JavaScript or use a modern browser.
Repository of the University of Ljubljana
Open Science Slovenia
Open Science
DiKUL
slv
|
eng
Search
Advanced
New in RUL
About RUL
In numbers
Help
Sign in
Details
Independent mutual-visibility sets and distance edge-critical graphs
ID
Tian, Jing
(
Author
),
ID
Bujtás, Csilla
(
Author
),
ID
Klavžar, Sandi
(
Author
)
PDF - Presentation file,
Download
(517,24 KB)
MD5: 1452199D10B9E3BB6B936C2EFA675307
URL - Source URL, Visit
https://opuscula.agh.edu.pl/archives/vol-46-2026/vol-5/7/
Image galllery
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
UDC:
519.17
ISSN on article:
1232-9274
DOI:
10.7494/OpMath.202609091
COBISS.SI-ID:
303687171
Publication date in RUL:
03.11.2026
Views:
119
Downloads:
19
Metadata:
Cite this work
Plain text
BibTeX
EndNote XML
EndNote/Refer
RIS
ABNT
ACM Ref
AMA
APA
Chicago 17th Author-Date
Harvard
IEEE
ISO 690
MLA
Vancouver
:
Copy citation
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
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