Two classes of graphs in which some problems related to convexity are efficiently solvable
| Autor: | Marina Moscarini, Francesco M. Malvestuto |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Geodesic
geodesic convexity Astrophysics::Instrumentation and Methods for Astrophysics monophonic convexity Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology distance-hereditary graphs 01 natural sciences Convexity 2-geodesic convexity cross-cyclic Combinatorics 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Computer Science::General Literature Discrete Mathematics and Combinatorics Geodesic convexity Mathematics |
| Popis: | Monophonic, geodesic and 2-geodesic convexities ([Formula: see text]-convexity, [Formula: see text]-convexity and [Formula: see text]-convexity, for short) on graphs are based on the families of induced paths, shortest paths and shortest paths of length [Formula: see text], respectively. We introduce a class of graphs, the class of cross-cyclicgraphs, in which every connected [Formula: see text]-convex set is also [Formula: see text]-convex and [Formula: see text]-convex. We show that this class is properly contained in the class, say [Formula: see text], of graphs in which geodesic and monophonic convexities are equivalent and properly contains the class of distance-hereditary graphs. Moreover, we show that (1) an [Formula: see text]-hull set (i.e., a subset of vertices, with minimum cardinality, whose [Formula: see text]-convex hull equals the whole vertex set) and, hence, the m-hull number and the g-hull number of a graph in [Formula: see text] can be computed in polynomial time and that (2) both the geodesic-convex hull and the monophonic-convex hull can be computed in linear time in a cross-cyclic graph without cycles of length [Formula: see text] and, hence, in a bipartite distance-hereditary graph. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|