Efficient edge domination in regular graphs

An induced matching of a graph G is a matching having no two edges joined by an edge. An efficient edge dominating set of G is an induced matching M such that every other edge of G is adjacent to some edge in M. We relate maximum induced matchings and efficient edge dominating sets, showing that efficient edge dominating sets are maximum induced matchings, and that maximum induced matchings on regular graphs with efficient edge dominating sets are efficient edge dominating sets. A necessary condition for the existence of efficient edge dominating sets in terms of spectra of graphs is established. We also prove that, for arbitrary fixed p ≥ 3, deciding on the existence of efficient edge dominating sets on p-regular graphs is NP-complete. © 2008 Elsevier B.V. All rights reserved.

Efficient domination through eigenvalues

The paper begins with a new characterization of (k,τ)(k,τ)-regular sets. Then, using this result as well as the theory of star complements, we derive a simplex-like algorithm for determining whether or not a graph contains a (0,τ)(0,τ)-regular set. When τ=1τ=1, this algorithm can be applied to solve the efficient dominating set problem which is known to be NP-complete. If −1−1 is not an eigenvalue of the adjacency matrix of the graph, this particular algorithm runs in polynomial time. However, although it does not work in polynomial time in general, we report on its successful application to a vast set of randomly generated graphs.

Estruturadores do discurso na aula de português em Moçambique

O nosso estudo debruça-se sobre o uso de estruturadores do discurso na interacção verbal, em contexto pedagógico. As nossas referências teóricas estão vinculadas à Análise do Discurso, quer à escola francesa (com origem na Linguística), quer à escola anglo-saxónica (com origem na Antropologia). Em relação à área da Linguística, buscámos os pressupostos da Pragmática, Sociolinguística e Psicolinguística; relativamente à Antropologia, seguimos as abordagens etnográficas, etnometodológicas e interaccionistas. Nesta pesquisa participaram 15 professores e 778 alunos de cinco escolas do ensino secundário/equiparado da cidade da Beira e da região de Maputo (Moçambique), que integravam, nomeadamente, as turmas do 1.º e 2.º ano do ramo comercial e 9.ª e 10.ª classe do ensino secundário geral. Observámos 40 aulas, das quais foram transcritas e analisadas 10 aulas. A transcrição e a anotação foram realizadas com o auxílio do programa Transcriber. Usámos métodos qualitativos e quantitativos e, predominantemente, procedimentos descritivos. Identificámos 4700 marcadores discursivos distribuídos nas seguintes subcategorias: marcadores discursivos directivos, marcadores discursivos de confirmação, marcadores discursivos de natureza fáctica e de concordância e as interjeições como marcadores discursivos. Os resultados da nossa pesquisa permitiram-nos concluir que os marcadores discursivos e as disfluências desempenham funções ligadas à estruturação textual-interactiva. Estes fenómenos linguísticos, ao estruturarem o discurso de professores e alunos, contribuem para a produção/compreensão de sentido das frases.

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.

Bullying nas escolas: prevenção e intervenção

A temática da violência (e do bullying) nas escolas em Portugal tem vindo, nos anos mais recentes, a assumir uma crescente visibilidade fruto de variados fatores, entre os quais podemos destacar o aparente aumento no número de incidentes reportados envolvendo alunos, professores e pessoal não docente ou, ainda, como resultado da maior atenção dispensada ao(s) fenómeno(s) pela comunicação social. Na relação que se estabelece entre alunos, o bullying (e ultimamente o cyberbullying) tem igualmente ocupado um maior espaço de discussão no contexto português pela elevada complexidade que o carateriza e pelas diversas consequências negativas e irreversíveis que acarreta para vítimas, agressores, famílias e escolas. Para que sejam encontradas estratégias e soluções eficazes na abordagem ao(s) fenómeno(s), torna-se necessário aprofundar – e partilhar – o(s) conhecimento(s) em torno dos fatores e das dinâmicas que caraterizam o fenómeno e que contribuem para a sua (re)ocorrência. Procurámos, portanto, refletir sobre o papel que a escola, enquanto organização com uma missão muito própria ‒ e todos os demais elementos que a integram (diretores, docentes, assistentes operacionais, alunos e respetivas famílias) ‒ devem efetivamente desempenhar no sentido de serem promovidas e implementadas políticas e medidas que possam acautelar e solucionar quaisquer manifestações de violência, com especial incidência nos episódios de bullying. Sobressai, em primeira instância, a necessidade de sensibilizar e de mobilizar toda a comunidade escolar, prestando especial atenção ao papel vital que cada sujeito desempenha. Destaque-se, por outro lado, a aposta que deve ser feita na vertente da (in)formação de professores, não docentes, alunos e pais com o claro propósito de serem criados climas de escola positivos e seguros. Dividimos o trabalho empírico da nossa investigação em dois momentos. Do estudo comparativo (resultante da recolha de informação baseada na pesquisa e análise documental) que levámos a cabo na primeira parte a um conjunto de doze programas de prevenção e de intervenção de bullying implementados (e igualmente avaliados) em países anglo-saxónicos, procurámos identificar os seus componentes fundamentais (princípios teóricos subjacentes às intervenções, objetivos pretendidos, destinatários, níveis/fases de ação, componentes/estratégias de atuação e materiais de apoio disponibilizados). Pudemos verificar que essas iniciativas assentaram numa perspetiva sistémica da problemática do bullying que sublinha a necessidade de mudanças persistentes e contibuadas ao nível da sensibilização, da consciencialização e de transformações nas atitudes da população escolar no seu todo. Este exercício possibilitou, por outro lado, a identificação e a assimiliação de algumas das boas práticas experimentadas com esses programas. Na segunda parte, desenvolvemos um projeto-piloto numa escola Secundária com o 3.º Ciclo do Ensino Básico ao longo do ano letivo de 2010/2011 (envolvendo diretamente na iniciativa duas turmas ‒ uma do 7.º e outra do 10.º ano ‒ e os respetivos professores), sendo de destacar que a temática se tornou mais familiar para a maior parte dos participantes (por via da mobilização, da sensibilização e da formação desses atores). Na sequência da aplicação de dois questionários a 190 alunos no âmbito do projeto-piloto, foi ainda possível apurar que as percentagens de vitimação de bullying presencial moderado se situam abaixo dos 10%, sendo que para as ofensas sofridas de modo mais intenso esses níveis não ultrapassam os 5% para qualquer uma das formas de agressão apresentadas. Os dados indicaram igualmente as ofensas diretas verbais e indiretas como sendo as mais frequentes entre os inquiridos, surgindo em terceiro lugar as de pendor direto físico. Os índices de vitimação apresentam valores superiores junto dos alunos mais novos, independentemente do seu género. Perto de 45% dos sujeitos objeto de agressão admitiu não ter reportado o sucedido a uma terceira pessoa. Cerca de 27% dos jovens confessou assumir uma atitude passiva ou de indiferença perante uma agressão testemunhada. Foi, por outro lado, possível constatar que um conjunto significativo de jovens admitiu conhecer um colega da escola que tenha sido já gozado ou ameaçado no ciberespaço.

Nós há de morrer...óss tem de cantar! : música, memória e imaginação em Damão : trânsitos pós-coloniais

O presente trabalho inscreve-se no domínio da etnomusicologia, resulta da realização de trabalho de campo multissituado e propõe-se compreender a comunidade católica damanense residente em Damão (Índia) e no Reino Unido partindo do estudo da música adotada e praticada pelos seus membros. O repertório performativo analisado neste trabalho inclui música (religiosa e secular) e dança entendidas pelos damanenses como herdadas do antigo colonizador, música e dança anglo-saxónica e de Bollywood transmitida pelos meios de comunicação de massa atuais e, ainda, aquela que é veicularmente considerada pelos damanenses católicos como “a música damanense” ou “a música original de Damão” e à qual é aqui dado um enfoque especial: o mandó. Argumento que a compreensão deste repertório e dos diferentes significados de que se reveste nos permite também compreender a própria damanidade, cuja performance é caracterizada pelos mesmos princípios que definem a da música. Permite-nos, igualmente, entender o modo como os damanenses católicos vivem a sua condição de integração na Índia enquanto comunidade pós-colonial não-independente. Este trabalho procura contribuir, portanto, para a inscrição da realidade dos territórios poscoloniais integrados no quadro da teoria do poscolonialismo e reflete sobre o protagonismo da música na construção de lugares de memória e de imaginação tanto no território de origem (Damão) como na diáspora (Reino Unido).