Mutual-visibility and general position in double graphs and in Mycielskians

Roy, Dhanya (author), Klavžar, Sandi (author), Lakshmanan S., Aparna (author)

The general position problem in graphs is to find the largest possible set of vertices with the property that no three of them lie on a common shortest path. The mutual-visibility problem in graphs is to find the maximum number of vertices that can be selected such that every pair of vertices in the collection has a shortest path between them with no vertex from the collection as an internal vertex. Here, the general position problem and the mutual-visibility problem are investigated in double graphs and in Mycielskian graphs. Sharp general bounds are proved, in particular involving the total and the outer mutual-visibility number of base graphs. Several exact values are also determined, in particular the mutual-visibility number of the double graphs and of the Mycielskian of cycles.

• Language: English
• Keywords: general position, mutual-visibility, double graph, Mycielskian graph, outer mutual-visibility, total mutual-visibility
• 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: 2025
• Number of pages: 9 str.
• Numbering: Vol. 488, art. 129131
• PID: 20.500.12556/RUL-164335
• UDC: 519.17
• ISSN on article: 0096-3003
• DOI: 10.1016/j.amc.2024.129131
• COBISS.SI-ID: 212344835
• Publication date in RUL: 22.10.2024

Record is a part of a journal

• Title: Applied mathematics and computation
• Shortened title: Appl. math. comput.
• Publisher: Elsevier
• ISSN: 0096-3003
• COBISS.SI-ID: 24983808

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: splošna lega, vzajemna vidnost, dvojni graf, graf Mycielskega, zunanja vzajemna vidnost, celotna vzajemna vidnost