Main eigenvalues and (κ, τ)-regular sets

A (κ, τ)-regular set is a subset of the vertices of a graph G, inducing a κ-regular subgraph such that every vertex not in the subset has τ neighbors in it. A main eigenvalue of the adjacency matrix A of a graph G has an eigenvector not orthogonal to the all-one vector j. For graphs with a (κ, τ)-regular set a necessary and sufficient condition for an eigenvalue be non-main is deduced and the main eigenvalues are characterized. These results are applied to the construction of infinite families of bidegreed graphs with two main eigenvalues and the same spectral radius (index) and some relations with strongly regular graphs are obtained. Finally, the determination of (κ, τ)-regular sets is analyzed. © 2009 Elsevier Inc. All rights reserved.

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.

A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph

A family of quadratic programming problems whose optimal values are upper bounds on the independence number of a graph is introduced. Among this family, the quadratic programming problem which gives the best upper bound is identified. Also the proof that the upper bound introduced by Hoffman and Lovász for regular graphs is a particular case of this family is given. In addition, some new results characterizing the class of graphs for which the independence number attains the optimal value of the above best upper bound are given. Finally a polynomial-time algorithm for approximating the size of the maximum independent set of an arbitrary graph is described and the computational experiments carried out on 36 DIMACS clique benchmark instances are reported.

Relations between (κ, τ)-regular sets and star complements

Let G be a finite graph with an eigenvalue μ of multiplicity m. A set X of m vertices in G is called a star set for μ in G if μ is not an eigenvalue of the star complement G\X which is the subgraph of G induced by vertices not in X. A vertex subset of a graph is (k ,t)-regular if it induces a k -regular subgraph and every vertex not in the subset has t neighbors in it. We investigate the graphs having a (k,t)-regular set which induces a star complement for some eigenvalue. A survey of known results is provided and new properties for these graphs are deduced. Several particular graphs where these properties stand out are presented as examples.

A recursive construction of the regular exceptional graphs with least eigenvalue -2

In spectral graph theory a graph with least eigenvalue 2 is exceptional if it is connected, has least eigenvalue greater than or equal to 2, and it is not a generalized line graph. A ðk; tÞ-regular set S of a graph is a vertex subset, inducing a k-regular subgraph such that every vertex not in S has t neighbors in S. We present a recursive construction of all regular exceptional graphs as successive extensions by regular sets.

Determination of (0,2)-regular sets in graphs and applications

In this paper, relevant results about the determination of (k,t)-regular sets, using the main eigenvalues of a graph, are reviewed and some results about the determination of (0,2)-regular sets are introduced. An algorithm for that purpose is also described. As an illustration, this algorithm is applied to the determination of maximum matchings in arbitrary graphs.

Supervisão colaborativa para uma educação inclusiva : um estudo com professores do ensino regular

Este trabalho, desenvolvido por uma professora de educação especial no contexto onde exerce funções, resultou da vontade de aprofundar o conhecimento sobre as dinâmicas de trabalho entre os professores do Ensino Regular e entre estes e o professor de Educação Especial. Desta forma elaborámos um projeto de investigação com o propósito de aprofundar o conhecimento sobre estas dinâmicas, no âmbito de uma oficina de formação, dinamizada pela investigadora, realizada no contexto de trabalho dos participantes. Neste âmbito, foi proporcionado um conjunto de experiências vivenciadas em conjunto, procurando contribuir para novas perspetivas teóricas sobre o conhecimento, bem como o envolvimento dos participantes em situações empíricas que lhes permitissem aplicar esses conhecimentos na resolução de problemas concretos emergentes no seu contexto de trabalho. A estratégia formativa baseou-se na colaboração como factor de desenvolvimento e de aprendizagem, surgindo como relevante e necessário o envolvimento dos formandos em processos de investigação da própria prática. A formação, na modalidade de Oficina, foi promovida através do Centro de Formação da Instituição onde a escola, um estabelecimento de ensino particular e cooperativo, se integra. Neste âmbito foi acreditada pelo Conselho Científico-Pedagógico da Formação Contínua e envolveu dezasseis professores do 1.º, 2.º e 3.º ciclos do ensino básico. A formação desenvolveuse em duas fases - a primeira fase, constituída por 4 sessões, teve lugar entre maio e julho de 2011, e a segunda fase, igualmente constituída por 4 sessões, teve lugar de setembro a novembro de 2011, num total de 25 horas presenciais e 25 horas não presenciais. Trata-se de um estudo com uma dupla intencionalidade – formativa e investigativa – no qual se procura compreender (i) a relação entre as estratégias de formação e supervisão promovidas pela professora de educação especial e o desenvolvimento de dinâmicas de trabalho colaborativo entre os participantes (ii) e o impacto dessas dinâmicas no desenvolvimento profissional e nas suas práticas, tendo em vista a promoção de uma educação inclusiva. Configura-se como estudo de caso, na variante de multicaso apresentando, ainda, algumas características de investigação-ação. No âmbito deste estudo, utilizámos um conjunto diverso e complementar de procedimentos investigativos, nomeadamente, o inquérito por questionário aplicado a todos os participantes no início e no fim da oficina de formação; o inquérito por questionário de avaliação das sessões, tendo por base os objetivos do estudo; a entrevista semi-estruturada, realizada a quatro docentes do 1º CEB que constituem os subcasos e o portfolio reflexivo individual dos mesmos, os quais se constituem como estratégia de formação e de investigação. Recorreu-se, ainda, como fontes de informação secundária, ao Teaching portfolio do investigador, às videogravações das sessões de formação, aos registos em vídeo de alguns episódios relativos à intervenção dos formandos em sala de aula e aos projetos de investigação-ação, bem como aos dados recolhidos na entrevista dirigida ao Diretor do estabelecimento de educação e ensino, depois de concluído o programa de formação. Os resultados da análise parecem evidenciar a existência de dinâmicas colaborativas e um clima de inter-ajuda que caraterizou a interação ocorrida na formação, em torno de casos concretos, os quais tiveram um impacto significativo sobre o pensamento e a prática dos participantes. Todo o processo desenvolvido parece ter dado lugar à partilha de saberes e à procura conjunta de soluções para os problemas, tendo contribuído para que os professores passassem a ser mais interventivos, evidenciando novas aprendizagens e uma maior consciencialização do conceito de educação para todos e do que esta implica. Os resultados parecem ainda revelar o desenvolvimento de uma parceria estratégica entre os professores do ensino regular e a professora de educação especial, a qual passou a ser aceite como uma pessoa que pode ajudar a encontrar soluções para os problemas que surgem na sala de aula, de forma a garantir a inclusão de todos os alunos e não apenas dos que têm necessidades educativas especiais.