Geodesic transversal problem for join and lexicographic product of graphs

被引:2
作者
Peterin, Iztok [1 ,2 ]
Semanisin, Gabriel [3 ]
机构
[1] Univ Maribor, Fac Elect Engn & Comp Sci, Inst Math & Phys, Koroska Cesta 46, Maribor 2000, Slovenia
[2] Inst Math Phys & Mech, Jadranska 19, Ljubljana 1000, Slovenia
[3] Pavol Jozef Safarik Univ, Fac Sci, Inst Comp Sci, Jesenna 5, Kosice 04154, Slovakia
关键词
Geodesic transversal; Geodesic transversal number; Lexicographic product; Join; STRONG METRIC DIMENSION;
D O I
10.1007/s40314-022-01834-1
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A set S of vertices of a graph G is a geodesic transversal of G if every maximal geodesic of G contains at least one vertex of S. The minimum cardinality of a geodesic transversal of G is denoted by gt(G) and is called geodesic transversal number. For two graphs G and H we deal with the behavior of this invariant for the lexicographic product G omicron H and join G circle plus H. We determine gt(G circle plus H) in terms of structural properties of the original graphs and describe gt(G omicron H) as a solution of an optimization problem concerning specific subsets of V (G).
引用
收藏
页数:13
相关论文
共 15 条
[1]   Minimum k-path vertex cover [J].
Bresar, Bostjan ;
Kardos, Frantisek ;
Katrenic, Jan ;
Semanisin, Gabriel .
DISCRETE APPLIED MATHEMATICS, 2011, 159 (12) :1189-1195
[2]   The geodetic number of the lexicographic product of graphs [J].
Bresar, Bostjan ;
Sumenjak, Tadeja Kraner ;
Tepeh, Aleksandra .
DISCRETE MATHEMATICS, 2011, 311 (16) :1693-1698
[3]   [1, k]-Domination Number of Lexicographic Products of Graphs [J].
Ghareghani, Narges ;
Peterin, Iztok ;
Sharifani, Pouyeh .
BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2021, 44 (01) :375-392
[4]  
Hammack R., 2011, Handbook of Product Graphs, V2, DOI [10.1201/b10959 1283.05001, DOI 10.1201/B10959, 10.1201/b10959]
[5]   MINIMAL DOUBLY RESOLVING SETS AND THE STRONG METRIC DIMENSION OF HAMMING GRAPHS [J].
Kratica, Jozef ;
Kovacevic-Vujcic, Vera ;
Cangalovic, Mirjana ;
Stojanovic, Milica .
APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS, 2012, 6 (01) :63-71
[6]   CLOSED FORMULAE FOR THE STRONG METRIC DIMENSION OF LEXICOGRAPHIC PRODUCT GRAPHS [J].
Kuziak, Dorota ;
Yero, Ismael G. ;
Rodriguez-Velazquez, Juan A. .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2016, 36 (04) :1051-1064
[7]   On the strong metric dimension of the strong products of graphs [J].
Kuziak, Dorota ;
Yero, Ismael G. ;
Rodriguez-Velazquez, Juan A. .
OPEN MATHEMATICS, 2015, 13 (01) :64-74
[8]   On the strong metric dimension of corona product graphs and join graphs [J].
Kuziak, Dorota ;
Yero, Ismael G. ;
Rodriguez-Velazquez, Juan A. .
DISCRETE APPLIED MATHEMATICS, 2013, 161 (7-8) :1022-1027
[9]  
Manuel P, 2021, GEODESIC TRANSVERSAL
[10]   The geodesic-transversal problem [J].
Manuel, Paul ;
Bresar, Bostjan ;
Klavzar, Sandi .
APPLIED MATHEMATICS AND COMPUTATION, 2022, 413