MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEOn the hull number of some graph classes.
par Julio Araujo
| Date : | 05/07/11 | | Time : | 10:30 | | Location : | Lagrange Gris |
The convexity notions in the Euclidian space can be extended to graphs.
Given a graph G = (V, E), the closed interval of a pair of vertices u, v, denoted by I[u, v], is the set of vertices that belongs to some shortest (u, v)-path.
For a given set S of vertices, let I[S] be the union of the intervals I[u, v] over all pairs u,v of vertices in S. We say that S is a convex set if I[S] = S.The convex hull Ih [S] of a subset S of vertices is the smallest convex set that contains S. We say that S is a hull set if Ih [S] = V . The cardinality of a minimum hull set of G is the hull number of G, denoted by hn(G).
In this talk, we discuss some previous results about the Hull number of a given graph G and present some new complexity results.
We show that deciding if hn(G) is at most k is an NP-complete problem, even if G is bipartite. We also prove that hn(G) can be computed in polynomial time for cactus and P4 -sparse graphs. These results are joint work with V. Campos, F. Giroire, L. Sampaio, R. Soares and will be presented in EuroComb'11.
At the end of the talk, we present further results we obtained with N. Nisse, showing that hn(G) can be computed in polynomial time for complements of bipartite graphs and for (q,q-4)-graphs, for a fixed positive integer q.
Page des séminaires
| 
