Strong Geodetic Number of Complete Bipartite Graphs, Crown Graphs and Hypercubes

被引:0
作者
Valentin Gledel
Vesna Iršič
机构
[1] Univ Lyon,Université Lyon 1, LIRIS UMR CNRS 5205
[2] Institute of Mathematics,Faculty of Mathematics and Physics
[3] Physics and Mechanics,undefined
[4] University of Ljubljana,undefined
来源
Bulletin of the Malaysian Mathematical Sciences Society | 2020年 / 43卷
关键词
Geodetic number; Strong geodetic number; Complete bipartite graph; Crown graph; Hypercube; 05C12; 05C70;
D O I
暂无
中图分类号
学科分类号
摘要
The strong geodetic number, sg(G),\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {sg}(G),$$\end{document} of a graph G is the smallest number of vertices such that by fixing a suitable geodesic between each pair of selected vertices, all vertices of the graph are covered. In this paper, the formula for sg(Kn,m)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {sg}(K_{n,m})$$\end{document} is given, as well as a formula for the crown graphs Sn0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$S_n^0$$\end{document}. Bounds on the strong geodetic number of the hypercube Qn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Q_n$$\end{document} are also discussed.
引用
收藏
页码:2757 / 2767
页数:10
相关论文
共 60 条
[1]  
Artigas D(2011)Partitioning a graph into convex sets Discrete Math. 311 1968-1977
[2]  
Dantas S(1988)Geodetic graphs of diameter two Geom. Dedic. 25 527-533
[3]  
Dourado MC(2011)Minimum Discrete Appl. Math. 159 1189-1195
[4]  
Szwarcfiter JL(2008)-path vertex cover Discrete Math 308 5555-5561
[5]  
Blokhuis A(2018)On the geodetic number and related metric sets in Cartesian product graphs Inform. Process. Lett. 135 22-27
[6]  
Brouwer AE(2000)On the hardness of finding the geodetic number of a subcubic graph Discuss. Math. Graph Theory 20 129-138
[7]  
Brešar B(2008)Geodetic sets in graphs Util. Math. 76 129-144
[8]  
Jakovac M(2010)The ultimate isometric path number of a graph Discrete Math. 310 832-837
[9]  
Katrenič J(2001)Some remarks on the geodetic number of a graph J. Comb. Math. Comb. Comput. 38 97-110
[10]  
Semanišin G(1999)The isometric path number of a graph Congr. Numer. 137 109-119