# zbMATH — the first resource for mathematics

Toll number of the strong product of graphs. (English) Zbl 1403.05122
Summary: A tolled walk $$T$$ between two non-adjacent vertices $$u$$ and $$v$$ in a graph $$G$$ is a walk, in which $$u$$ is adjacent only to the second vertex of $$T$$ and $$v$$ is adjacent only to the second-to-last vertex of $$T$$. A toll interval between $$u, v \in V(G)$$ is a set $$T_G(u, v) = \{x \in V(G) \mid x \text{ lies on a tolled walk between } u \text{ and } v \}$$. A set $$S \subseteq V(G)$$ is toll convex, if $$T_G(u, v) \subseteq S$$ for all $$u, v \in S$$. A toll closure of a set $$S \subseteq V(G)$$ is the union of toll intervals between all pairs of vertices from $$S$$. The size of a smallest set $$S$$ whose toll closure is the whole vertex set is called the toll number of $$G$$, $$\operatorname{tn}(G)$$. This paper investigates the toll number of the strong product of graphs. First, a description of toll intervals between two vertices in the strong product graphs is given. Using this result we characterize graphs with $$\operatorname{tn}(G \boxtimes H) = 2$$ and graphs with $$\operatorname{tn}(G \boxtimes H) = 3$$, which are the only two possibilities. As an addition, for the t-hull number of $$G \boxtimes H$$ we show that $$\operatorname{th}(G \boxtimes H) = 2$$ for any non-complete graphs $$G$$ and $$H$$. As extreme vertices play an important role in different convexity types, we show that no vertex of the strong product graph of two non-complete graphs is an extreme vertex with respect to the toll convexity.
##### MSC:
 05C76 Graph operations (line graphs, products, etc.)
##### Keywords:
toll convexity; toll number; strong product
Full Text:
##### References:
  Alcón, L., A note on path domination, Discuss. Math. Graph Theory, 36, 1021-1034, (2016) · Zbl 1350.05069  Alcón, L.; Brešar, B.; Gologranc, T.; Gutierrez, M.; Kraner, T.; Peterin, I.; Tepeh, A., Toll convexity, European J. Combin., 46, 161-175, (2015) · Zbl 1307.05123  Brešar, B.; Klavžar, S.; Tepeh Horvat, A., On the geodetic number and related metric sets in Cartesian product graphs, Discrete Math., 308, 5555-5561, (2008) · Zbl 1200.05060  Brešar, B.; Kovše, M.; Tepeh, A., Geodetic sets in graphs, (Dehmer, M., Structural Analysis of Complex Networks, (2010), Birkhäuser: Birkhäuser Boston), 197-218 · Zbl 1221.05107  Brešar, B.; Kraner Šumenjak, T.; Tepeh, A., The geodetic number of the lexicographic product of graphs, Discrete Math., 311, 1693-1698, (2011) · Zbl 1223.05253  Cáceres, J.; Hernando, C.; Mora, M.; Pelayo, I. M.; Puertas, M. L., On the geodetic and the hull numbers in strong product graphs, Comput. Math. Appl., 60, 11, 3020-3031, (2010) · Zbl 1207.05043  Cagaanan, G. B.; Canoy Jr, S. R., On the hull sets and hull number of the Cartesian product of graphs, Discrete Math., 287, 141-144, (2004) · Zbl 1050.05042  Changat, M.; Mulder, H. M.; Sierksma, G., Convexities related to path properties on graphs, Discrete Math., 290, 117-131, (2005) · Zbl 1058.05043  Chartrand, G.; Harary, F.; Zhang, P., On the geodetic number of a graph, Networks, 39, 1-6, (2002) · Zbl 0987.05047  Chartrand, G.; Palmer, E. M.; Zhang, P., The geodetic number of a graph: a survey, Congr. Numer., 156, 37-58, (2002) · Zbl 1027.05033  Chartrand, G.; Zhang, P., The Steiner number of a graph, Discrete Math., 242, 41-54, (2002) · Zbl 0988.05034  Everett, M. G.; Seidman, S. B., The hull number of a graph, Discrete Math., 57, 217-223, (1985) · Zbl 0584.05044  Farber, M.; Jamison, R. E., Convexity in graphs and hypergraphs, SIAM J. Algebr. Discrete Math., 7, 433-444, (1986) · Zbl 0591.05056  Gologranc, T.; Repolusk, P., Toll number of the Cartesian and the lexicographic product of graphs, Discrete Math., 340, 2488-2498, (2017) · Zbl 1367.05177  Hammack, R.; Imrich, W.; Klavžar, S., Handbook of Product Graphs, (2011), CRC Press: CRC Press Boca Raton, FL · Zbl 1283.05001  Harary, F.; Loukakis, E.; Tsouros, C., The geodetic number of a graph, Math. Comput. Modelling, 17, 89-95, (1993) · Zbl 0825.68490  Hernando, C.; Jiang, T.; Mora, M.; Pelayo, I.; Seara, C., On the Steiner, geodetic and hull numbers of graphs, Discrete Math., 293, 139-154, (2005) · Zbl 1062.05052  Pelayo, I. M., Geodesic Convexity in Graphs, (2013), Springer: Springer New York · Zbl 1285.05001  Santhakumaran, A. P.; Titus, P.; Ganesamoorthy, K., On the monophonic number of a graph, J. Appl. Math. Inform., 32, 255-266, (2014) · Zbl 1285.05049  Santhakumaran, A. P.; Ullas Chandran, S. V., The geodetic number of strong product graphs, Discuss. Math. Graph Theory, 30, 687-700, (2010) · Zbl 1217.05085  Santhakumaran, A. P.; Ullas Chandran, S. V., The hull number of strong product graphs, Discuss. Math. Graph Theory, 31, 493-507, (2011) · Zbl 1229.05240  van de Vel, M. J.L., Theory of Convex Structures, (1993), North-Holland: North-Holland Amsterdam · Zbl 0785.52001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.