# zbMATH — the first resource for mathematics

Toll number of the Cartesian and the lexicographic product of graphs. (English) Zbl 1367.05177
Summary: Toll convexity is a variation of the so-called interval convexity. 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) : 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 a toll number of a graph $$G$$, $$\operatorname{tn}(G)$$. The first part of the paper reinvestigates the characterization of convex sets in the Cartesian product of two graphs. It is proved that the toll number of the Cartesian product of two graphs equals 2. In the second part, the toll number of the lexicographic product of two graphs is studied. It is shown that if $$H$$ is not isomorphic to a complete graph, $$\operatorname{tn}(G \circ H) \leq 3 \cdot \operatorname{tn}(G)$$. We give some necessary and sufficient conditions for $$\operatorname{tn}(G \circ H) = 3 \cdot \operatorname{tn}(G)$$. Moreover, if $$G$$ has at least two extreme vertices, a complete characterization is given. Furthermore, graphs with $$\operatorname{tn}(G \circ H) = 2$$ are characterized. Finally, the formula for $$\operatorname{tn}(G \circ H)$$ is given – it is described in terms of the so-called toll-dominating triples or, if $$H$$ is complete, toll-dominating pairs.

##### MSC:
 05C76 Graph operations (line graphs, products, etc.)
##### Keywords:
toll convexity; toll number; graph 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 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. Algebra Discrete Math., 7, 433-444, (1986) · Zbl 0591.05056  Hammack, R.; Imrich, W.; Klavžar, S., Handbook of Product Graphs, (2011), CRC Press Boca Raton, FL · Zbl 1283.05001  Harary, F.; Loukakis, E.; Tsouros, C., The geodetic number of a graph, Mathl. 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 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  van de Vel, M. J.L., Theory of Convex Structures, (1993), 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.