























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 \textrm{ lies on a tolled walk between } u \textrm{\, 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$, $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 $tn(G \boxtimes H)=2$ and graphs with $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 $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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。