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.

O burlesco e o satírico na obra de Marcial e Juvenal

A presente dissertação assenta na análise comparativa da obra de Marcial e Juvenal e tem como principais objectivos evidenciar a natureza burlesca e satírica que lhes assiste, assim como a (a)temporalidade e o alcance pedagógico-didáctico que as suas palavras comportam. Neste sentido, a análise tomou como matéria a abordagem que ambos fazem de temáticas comuns, no âmbito da representação da sociedade imperial do século I d.C. O trabalho divide-se em duas partes: I. Contexto e Condicionalismos; II. A vida quotidiana em Roma. A primeira subdividida em dois capítulos: 1. O espírito burlesco e o espírito satírico; 2. Apologia pro opere suo, e a segunda em quatro: 3. Modus vivendi Romani: prazeres e distracções em Roma; 4. (A)masculinidade Romana; 5. A condição feminina e o seu lugar em Roma; 6. Clientelismo e patronato sob o olhar de Marcial e Juvenal. Depois de uma contextualização dos termos burlesco e satírico, fundamentalmente alicerçada no primitivo espírito romano, procedeu-se à abordagem dos condicionalismos culturais, sócio-políticos e bibliográficos que melhor contribuem para a compreensão das principais diferenças/semelhanças entre a natureza, as intenções, as estratégias discursivas e a projecção das obras em causa. Na segunda parte, a análise comparativa da representação que os autores fazem da vida quotidiana em Roma focou essencialmente quatro aspectos, abordados em capítulos distintos, conforme supra-enunciado: no primeiro, a visão global que os autores projectam de Roma, através da representação dos principais divertimentos e distracções que ocupam e agradam aos Romanos; no segundo, a moralidade/falsidade que assiste aos comportamentos masculinos; no terceiro, a invectiva à mulher e ao lugar que esta ocupa nas relações sociais, afectivas e sexuais; no quarto, a instituição patronatoclientelismo e os valores sociais e morais que a revestem. A partir desta análise atestam-se as afinidades e o alcance de um fim semelhante nas obras de Marcial e Juvenal, não obstante a natureza e as diferenças estruturais que lhes assistem. Desta dissertação constam também uma Introdução e uma Conclusão, uma Bibliografia, bem como um Índice geral e um Index auctorum et locorum latinorum.

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.