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.
05C76 Graph operations (line graphs, products, etc.)
Full Text: DOI arXiv
[1] Alcón, L., A note on path domination, Discuss. Math. Graph Theory, 36, 1021-1034, (2016) · Zbl 1350.05069
[2] 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
[3] 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
[4] 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
[5] 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
[6] 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
[7] 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
[8] Changat, M.; Mulder, H. M.; Sierksma, G., Convexities related to path properties on graphs, Discrete Math., 290, 117-131, (2005) · Zbl 1058.05043
[9] Chartrand, G.; Harary, F.; Zhang, P., On the geodetic number of a graph, Networks, 39, 1-6, (2002) · Zbl 0987.05047
[10] Chartrand, G.; Palmer, E. M.; Zhang, P., The geodetic number of a graph: a survey, Congr. Numer., 156, 37-58, (2002) · Zbl 1027.05033
[11] Chartrand, G.; Zhang, P., The Steiner number of a graph, Discrete Math., 242, 41-54, (2002) · Zbl 0988.05034
[12] Everett, M. G.; Seidman, S. B., The hull number of a graph, Discrete Math., 57, 217-223, (1985) · Zbl 0584.05044
[13] Farber, M.; Jamison, R. E., Convexity in graphs and hypergraphs, SIAM J. Algebr. Discrete Math., 7, 433-444, (1986) · Zbl 0591.05056
[14] Gologranc, T.; Repolusk, P., Toll number of the Cartesian and the lexicographic product of graphs, Discrete Math., 340, 2488-2498, (2017) · Zbl 1367.05177
[15] Hammack, R.; Imrich, W.; Klavžar, S., Handbook of Product Graphs, (2011), CRC Press: CRC Press Boca Raton, FL · Zbl 1283.05001
[16] Harary, F.; Loukakis, E.; Tsouros, C., The geodetic number of a graph, Math. Comput. Modelling, 17, 89-95, (1993) · Zbl 0825.68490
[17] 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
[18] Pelayo, I. M., Geodesic Convexity in Graphs, (2013), Springer: Springer New York · Zbl 1285.05001
[19] 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
[20] 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
[21] 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
[22] 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.