Podrobno

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

.pdfPDF - Predstavitvena datoteka, prenos (517,24 KB)
MD5: 1452199D10B9E3BB6B936C2EFA675307
URLURL - Izvorni URL, za dostop obiščite https://opuscula.agh.edu.pl/archives/vol-46-2026/vol-5/7/ Povezava se odpre v novem oknu

Izvleček
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.

Jezik:Angleški jezik
Ključne besede:mutual-visibility set, independent set, distance edge-critical graph, dense diamond graph, computational complexity
Vrsta gradiva:Članek v reviji
Tipologija:1.01 - Izvirni znanstveni članek
Organizacija:FMF - Fakulteta za matematiko in fiziko
Status publikacije:Objavljeno
Različica publikacije:Objavljena publikacija
Leto izida:2026
Št. strani:Str. 773-790
Številčenje:Vol. 46, no. 5
PID:20.500.12556/RUL-190769 Povezava se odpre v novem oknu
UDK:519.17
ISSN pri članku:1232-9274
DOI:10.7494/OpMath.202609091 Povezava se odpre v novem oknu
COBISS.SI-ID:303687171 Povezava se odpre v novem oknu
Datum objave v RUL:03.11.2026
Število ogledov:123
Število prenosov:19
Metapodatki:XML DC-XML DC-RDF
:
Kopiraj citat
Objavi na:Bookmark and Share

Gradivo je del revije

Naslov:Rocznik Akademii Górniczo-Hutniczej im. Stanisława Staszica : Opuscula Mathematica
Skrajšan naslov:Rocz. Akad. Gór.-Hut. im. Stanisława Staszica, Opusc. Math.
Založnik:AGH University of Science and Technology Press
ISSN:1232-9274
COBISS.SI-ID:16179545 Povezava se odpre v novem oknu

Licence

Licenca:CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
Povezava:http://creativecommons.org/licenses/by/4.0/deed.sl
Opis:To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

Jezik:Slovenski jezik
Ključne besede:množica vzajemne vidnosti, neodvisna množica, razdaljno povezavno-kritični grafi, graf diamant, računska zahtevnost

Projekti

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:P1-0297
Naslov:Teorija grafov

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:N1-0285
Naslov:Metrični problemi v grafih in hipergrafih

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:N1-0355
Naslov:Prirejanja, transverzale in hipergrafi

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:N1-0431
Naslov:Dominacija v grafih: kubični grafi, produkti in igre

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:J1-70045
Naslov:Splošna lega in vidnost v teoriji grafov

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Nazaj