Akademska digitalna zbirka SLovenije - logo
VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
PDF
  • Toll number of the Cartesian and the lexicographic product of graphs
    Dravec, Tanja ; Repolusk, Polona
    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.
    Vir: Discrete mathematics. - ISSN 0012-365X (Vol. 340, iss. 10, 2017, str. 2488-2498)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2017
    Jezik - angleški
    COBISS.SI-ID - 23277064

    Povezava(-e):

    http://doi.org/10.1016/j.disc.2017.06.007
    DOI

vir: Discrete mathematics. - ISSN 0012-365X (Vol. 340, iss. 10, 2017, str. 2488-2498)
loading ...
loading ...
loading ...

Vnos na polico