Geodesic transversal problem for join and lexicographic product of graphs

被引:0
作者
Iztok Peterin
Gabriel Semanišin
机构
[1] University of Maribor,Institute of Mathematics and Physics, Faculty of Electrical Engineering and Computer Science
[2] Institute of Mathematics,Institute of Computer Science, Faculty of Science
[3] Physics and Mechanics,undefined
[4] Pavol Jozef Šafárik University,undefined
来源
Computational and Applied Mathematics | 2022年 / 41卷
关键词
Geodesic transversal; Geodesic transversal number; Lexicographic product; Join; 05C69; 05C12; 05C76;
D O I
暂无
中图分类号
学科分类号
摘要
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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text{ gt }(G)$$\end{document} 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∘H\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G\circ H$$\end{document} and join G⊕H\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G\oplus H$$\end{document}. We determine gt(G⊕H)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text{ gt }(G\oplus H)$$\end{document} in terms of structural properties of the original graphs and describe gt(G∘H)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text{ gt }(G\circ H)$$\end{document} as a solution of an optimization problem concerning specific subsets of V(G).
引用
收藏
相关论文
共 39 条
  • [1] Brešar B(2011)Minimum Discret Appl Math 159 1189-1195
  • [2] Kardoš F(2011)-path vertex cover Discret Math 311 1693-1698
  • [3] Katrenič J(2021)The geodetic number of the lexicographic product of graphs Bull Malays Math Sci Soc 44 375-392
  • [4] Semanišin G(2012)[1, k]-domination number of lexicographic products of graphs Discret Appl Math 160 2030-2036
  • [5] Brešar B(2012)On the roman domination in the lexicographic product of graphs Appl Anal Discret Math 6 63-71
  • [6] Kraner Šumenjak T(2013)Minimal doubly resolving sets and the strong metric dimension of Hamming graphs Discret Appl Math 161 1022-1027
  • [7] Tepeh A(2015)On the strong metric dimension of corona product graphs and join graphs Open Math 13 64-74
  • [8] Ghareghani N(2016)On the strong metric dimension of the strong products of graphs Discuss Math Graph Theory 36 1051-1064
  • [9] Peterin I(2022)Closed formulae for the strong metric dimension of lexicographic product graphs Appl Math Computat 413 126621-364
  • [10] Sharifani P(2007)The geodesic-transversal problem Discret Appl Math 155 356-19