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.

Persistent luminescence of SrAl2O4:Ce(III), Dy, Eu nanotubes, nanowires and core-shells for people with disabilities: nano-emergency

Este estudo transversal está focado na propriedade de luminescência persistente do aluminato de estrôncio co-dopado com cério (III), disprósio (III) e európio (II), SrAl2O4:Ce3+, Dy3+, Eu2+, em sistemas de sinalização de áreas de risco e emergências para pessoas com deficiências. Na área da ciência e engenharia dos materiais, foram desenvolvidos novos materiais com características nanométricas, nanotubos, nanoarames e nanobastões luminescentes de SrAl2O4:Ce3+, Dy3+, Eu2+ para aplicações na área da reabilitação e acessibilidade de pessoas com deficiências. Os nanotubos foram obtidos a partir de micro- e nano-partículas precursoras sintetizadas por reacção do estado-sólido e tratamento térmico de recozedura (1273-1473 K). Os nanoarames e nanobastões foram preparados por moagem, sonificação e recozedura (373 K). Novas nanocápsulas de aluminatos luminescentes dopados com cério (III) e encapsulados com TiO2 foram criadas de modo a obter-se materiais multifuncionais, designadamente com acção fotocatalítica antimicrobiana, antibacteriana e resistência à água. Tais aluminatos podem ser amplamente aplicados como superfícies higiénicas, auto-limpantes, em biomateriais, no domínio de medicamentos antibióticos, na formulação de vacinas, e com ênfase à aplicação em cerâmicas fotoluminescentes. As metodologias de obtenção de tais nanoestruturas de aluminato de estrôncio dopado com cério (III) e do seu encapsulamento, desenvolvidas no âmbito desta tese, são aplicáveis a diversos aluminatos dopados com outros iões lantanídeos (Ln consiste em La, Ce, Pr, Nd, Pm, Sm, Eu, Gd, Tb, Dy, Ho, Er, Yb, Tm ou Lu) com a fórmula M(1-x-y)N2O4:Cex, Lny, onde M é Be, Mg, Ca, Sr ou Ba. Na área da oftalmologia, foi desenvolvido um equipamento médico para o diagnóstico de biofuncionalidade das células retinais fotoreceptoras, e como suporte à telemedicina oftalmológica. Este equipamento foi utilizado para realizar testes de visão cromática FM100HUE em fundo branco/preto para a personalização de materiais luminescentes. Os resultados demonstraram uma biofuncionalidade celular à visibilidade fotópica das cores em fundo preto superior no grupo de tratamento, composto por pessoas com retinopatia diabética (n=38), em comparação ao grupo de referência (n=38). Estes resultados sugerem a recomendação de materiais com fotoluminescência persistente (λem=485-555 nm), incluindo SrAl2O4:Ce3+, Dy3+, Eu2+, para o referido grupo de tratamento, em sinalização de emergência e em ambientes de baixa iluminação. Na área da arquitectura, foi proposta uma nova aplicação dos referidos nanomateriais luminescentes à base de SrAl2O4:Ce3+, Dy3+, Eu2+ em cerâmica de revestimento, tendo em vista a sua boa visibilidade e uso por pessoas com deficiências. Novos pavimentos, cerâmicos, fotoluminescentes, foram desenhados com propriedades multisensoriais (contraste táctil, sonoro e visual) e antimicrobianas, para pessoas portadoras de deficiências utilizarem, no escuro, com a prioridade de salvar vidas em emergências. Tais pisos, com relevos, podem ser combinados de modo a compor um sistema exclusivo de sinalização fotoluminescente multisensorial que possibilita a rápida evacuação mediante o uso de auxílios de mobilidade (e.g. bengala, cadeira de rodas, andadores, muletas). A solução integrada de tais inovações que potencializa a propriedade de luminescência persistente de SrAl2O4:Ce3+, Dy3+, Eu2+ de modo acessível para as pessoas com deficiências, pode contribuir para salvar vidas, no escuro, em emergências.

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.