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.

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 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. Algebra Discrete Math., 7, 433-444, (1986) · Zbl 0591.05056
[14] Hammack, R.; Imrich, W.; Klavžar, S., Handbook of Product Graphs, (2011), CRC Press Boca Raton, FL · Zbl 1283.05001
[15] Harary, F.; Loukakis, E.; Tsouros, C., The geodetic number of a graph, Mathl. Comput. Modelling, 17, 89-95, (1993) · Zbl 0825.68490
[16] 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
[17] Pelayo, I. M., Geodesic Convexity in Graphs, (2013), Springer New York · Zbl 1285.05001
[18] 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
[19] 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.