Back to Search
Start Over
On the Δ-interval and the Δ-convexity numbers of graphs and graph products
- Source :
- Discrete Applied Mathematics. 319:487-498
- Publication Year :
- 2022
- Publisher :
- Elsevier BV, 2022.
-
Abstract
- Given a graph G and a set S ⊆ V ( G ) , the Δ -interval of S , [ S ] Δ , is the set formed by the vertices of S and every w ∈ V ( G ) forming a triangle with two vertices of S . If [ S ] Δ = S , then S is Δ -convex of G ; if [ S ] Δ = V ( G ) , then S is a Δ -interval set of G . The Δ -interval number of G is the minimum cardinality of a Δ -interval set and the Δ -convexity number of G is the maximum cardinality of a proper Δ -convex subset of V ( G ) . In this work, we show that the problem of computing the Δ -convexity number is W[1]-hard and NP-hard to approximate within a factor O ( n 1 − ɛ ) for any constant ɛ > 0 even for graphs with diameter 2 and that the problem of computing the Δ -interval number is NP-complete for general graphs. For the positive side, we present characterizations that lead to polynomial-time algorithms for computing the Δ -convexity number of chordal graphs and for computing the Δ -interval number of block graphs. We also present results on the Δ -hull, Δ -interval and Δ -convexity numbers concerning the three standard graph products, namely, the Cartesian, the strong and the lexicographic products, in function of these and well-studied parameters of the operands.
Details
- ISSN :
- 0166218X
- Volume :
- 319
- Database :
- OpenAIRE
- Journal :
- Discrete Applied Mathematics
- Accession number :
- edsair.doi...........af25fb8d2f65c27c2961c9e1200a4dba