Computing the hull and interval numbers in the weakly toll convexity

Abstract: A walk

u_{0} u_{1} l d o t s u_{k - 1} u_{k}

of a graph

G

is a extit{weakly toll walk} if

u_{0} u_{k} o t i n E (G)

,

u_{0} u_{i} i n E (G)

implies

u_{i} = u_{1}

, and

u_{j} u_{k} i n E (G)

implies

u_{j} = u_{k - 1}

. The {em weakly toll interval} of a set

S s u b s e t e q V (G)

, denoted by

I (S)

, is formed by

S

and the vertices belonging to some weakly toll walk between two vertices of

S

. Set

S

is {it weakly toll convex} if

I (S) = S

. The {em weakly toll convex hull} of

S

, denote by

H (S)

, is the minimum weakly toll convex set containing

S

. The {em weakly toll interval number} of

G

is the minimum cardinality of a set

S s u b s e t e q V (G)

such that

I (S) = V (G)

; and the {em weakly toll hull number} of

G

is the minimum cardinality of a set

S s u b s e t e q V (G)

such that

H (S) = V (G)

. In this work, we show how to compute the weakly toll interval and the weakly toll hull numbers of a graph in polynomial time. In contrast, we show that determining the weakly toll convexity number of a graph

G

(the size of a maximum weakly toll convex set distinct from

V (G)

) is NP-hard.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Computing the hull and interval numbers in the weakly toll convexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6131192)