Bicontactual hypermaps

Esta tese dedica-se ao estudo de hipermapas regulares bicontactuais, hipermapas com a propriedade que cada hiperface contacta só com outras duas hiperfaces. Nos anos 70, S. Wilson classificou os mapas bicontactuais e, em 2003, Wilson e Breda d’Azevedo classificaram os hipermapas bicontactuais no caso não-orientável. Quando esta propriedade é transferida para hipermapas origina três tipos de bicontactualidade, atendendo ao modo como as duas hiperfaces aparecem à volta de uma hiperface fixa: edge-twin, vertextwin and alternate (dois deles são o dual um do outro). Um hipermapa topológico é um mergulho celular de um grafo conexo trivalente numa superfície compacta e conexa tal que as células são 3-coloridas. Ou de maneira mais simples, um hipermapa pode ser visto como um mapa bipartido. Um hipermapa orientado regular é um triplo ordenado consistindo num conjunto finito e dois geradores, que são permutações (involuções) do conjunto tal que o grupo gerado por eles, chamado o grupo de monodromia, actua regularmente no conjunto. Nesta tese, damos uma classificação de todos os hipermapas orientados regulares bicontactuais e, para completar, reclassificamos, usando o nosso método algébrico, os hipermapas não-orientáveis bicontactuais.

Dominating induced matchings

We study the problem of determining whether or not a graph G has an induced matching that dominates every edge of the graph, which is also known as efficient edge domination. This problem is known to be NP-complete in general as well as in some restricted domains, such as bipartite graphs or regular graphs. In this paper, we identify a graph parameter to which the complexity of the problem is sensible and produce results of both negative (intractable) and positive (solvable in polynomial time) type. © 2009 Springer Berlin Heidelberg.

Census of quadrangle groups inclusions

In a classical result of 1972 Singerman classifies the inclusions between triangle groups. We extend the classification to a broader family of triangle and quadrangle groups forming a particular subfamily of Fuchsian groups. With two exceptions, each inclusion determines a finite bipartite map (hypermap) on a 2-dimensional spherical orbifold that encodes the complete information and gives a graphical visualisation of the inclusion. A complete description of all the inclusions is contained in the attached tables.