Source author record

Polona Repolusk

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Catalog footprint

Research overview

1works
1topics
1close collaborators

Published work

1 publications

preprint2016arXiv

Toll number of the Cartesian and the lexicographic product of graphs

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.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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