Toll number of the Cartesian and the lexicographic product of graphs

preprint2016arXivOpen access

Abstract

Toll convexity is a variation of the so-called interval convexity. A tolled walk TT between uu and vv in GG is a walk of the form T:u,w1,…,wk,v,T: u,w_1,\ldots,w_k,v, where k≥1k\ge 1, in which w1w_1 is the only neighbor of uu in TT and wkw_k is the only neighbor of vv in TT. As in geodesic or monophonic convexity, toll interval between u,v∈V(G)u,v\in V(G) is a set TG(u,v)={x∈V(G) : x lies on a tolled walk between u and v}T_G(u,v)=\{x\in V(G)\,:\,x \textrm{ lies on a tolled walk between } u \textrm{ and } v\}. A set of vertices SS is toll convex, if TG(u,v)⊆ST_{G}(u,v)\subseteq S for all u,v∈Su,v\in S. First part of the paper reinvestigates the characterization of convex sets in the Cartesian product of graphs. Toll number and toll hull number of the Cartesian product of two arbitrary graphs is proven to be 2. The second part deals with the lexicographic product of graphs. It is shown that if HH is not isomorphic to a complete graph, tn(G∘H)≤3⋅tn(G)tn(G \circ H) \leq 3\cdot tn(G). We give some necessary and sufficient conditions for tn(G∘H)=3⋅tn(G)tn(G \circ H) = 3\cdot tn(G). Moreover, if GG has at least two extreme vertices, a complete characterization is given. Also graphs with tn(G∘H)=2tn(G \circ H)=2 are characterized - this is the case iff GG has an universal vertex and tn(H)=2tn(H)=2. Finally, the formula for tn(G∘H)tn(G \circ H) is given - it is described in terms of the so-called toll-dominating triples.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.