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.

Majorantes para a ordem de subgrafos induzidos k-regulares

Muitos dos problemas de otimização em grafos reduzem-se à determinação de um subconjunto de vértices de cardinalidade máxima que induza um subgrafo k-regular. Uma vez que a determinação da ordem de um subgrafo induzido k-regular de maior ordem é, em geral, um problema NP-difícil, são deduzidos novos majorantes, a determinar em tempo polinomial, que em muitos casos constituam boas aproximações das respetivas soluções ótimas. Introduzem-se majorantes espetrais usando uma abordagem baseada em técnicas de programação convexa e estabelecem-se condições necessárias e suficientes para que sejam atingidos. Adicionalmente, introduzem-se majorantes baseados no espetro das matrizes de adjacência, laplaciana e laplaciana sem sinal. É ainda apresentado um algoritmo não polinomial para a determinação de umsubconjunto de vértices de umgrafo que induz umsubgrafo k-regular de ordem máxima para uma classe particular de grafos. Finalmente, faz-se um estudo computacional comparativo com vários majorantes e apresentam-se algumas conclusões.

Spectral characterization of families of split graphs

An upper bound for the sum of the squares of the entries of the principal eigenvector corresponding to a vertex subset inducing a k-regular subgraph is introduced and applied to the determination of an upper bound on the order of such induced subgraphs. Furthermore, for some connected graphs we establish a lower bound for the sum of squares of the entries of the principal eigenvector corresponding to the vertices of an independent set. Moreover, a spectral characterization of families of split graphs, involving its index and the entries of the principal eigenvector corresponding to the vertices of the maximum independent set is given. In particular, the complete split graph case is highlighted.

Necessary and sufficient conditions for a Hamiltonian graph

A graph is singular if the zero eigenvalue is in the spectrum of its 0-1 adjacency matrix A. If an eigenvector belonging to the zero eigenspace of A has no zero entries, then the singular graph is said to be a core graph. A ( k,t)-regular set is a subset of the vertices inducing a k -regular subgraph such that every vertex not in the subset has t neighbours in it. We consider the case when k=t which relates to the eigenvalue zero under certain conditions. We show that if a regular graph has a ( k,k )-regular set, then it is a core graph. By considering the walk matrix we develop an algorithm to extract ( k,k )-regular sets and formulate a necessary and sufficient condition for a graph to be Hamiltonian.

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.

Metabolic signature of lung cancer: a metabolomic study of human tissues and biofluids

This thesis reports the application of metabolomics to human tissues and biofluids (blood plasma and urine) to unveil the metabolic signature of primary lung cancer. In Chapter 1, a brief introduction on lung cancer epidemiology and pathogenesis, together with a review of the main metabolic dysregulations known to be associated with cancer, is presented. The metabolomics approach is also described, addressing the analytical and statistical methods employed, as well as the current state of the art on its application to clinical lung cancer studies. Chapter 2 provides the experimental details of this work, in regard to the subjects enrolled, sample collection and analysis, and data processing. In Chapter 3, the metabolic characterization of intact lung tissues (from 56 patients) by proton High Resolution Magic Angle Spinning (HRMAS) Nuclear Magnetic Resonance (NMR) spectroscopy is described. After careful assessment of acquisition conditions and thorough spectral assignment (over 50 metabolites identified), the metabolic profiles of tumour and adjacent control tissues were compared through multivariate analysis. The two tissue classes could be discriminated with 97% accuracy, with 13 metabolites significantly accounting for this discrimination: glucose and acetate (depleted in tumours), together with lactate, alanine, glutamate, GSH, taurine, creatine, phosphocholine, glycerophosphocholine, phosphoethanolamine, uracil nucleotides and peptides (increased in tumours). Some of these variations corroborated typical features of cancer metabolism (e.g., upregulated glycolysis and glutaminolysis), while others suggested less known pathways (e.g., antioxidant protection, protein degradation) to play important roles. Another major and novel finding described in this chapter was the dependence of this metabolic signature on tumour histological subtype. While main alterations in adenocarcinomas (AdC) related to phospholipid and protein metabolisms, squamous cell carcinomas (SqCC) were found to have stronger glycolytic and glutaminolytic profiles, making it possible to build a valid classification model to discriminate these two subtypes. Chapter 4 reports the NMR metabolomic study of blood plasma from over 100 patients and near 100 healthy controls, the multivariate model built having afforded a classification rate of 87%. The two groups were found to differ significantly in the levels of lactate, pyruvate, acetoacetate, LDL+VLDL lipoproteins and glycoproteins (increased in patients), together with glutamine, histidine, valine, methanol, HDL lipoproteins and two unassigned compounds (decreased in patients). Interestingly, these variations were detected from initial disease stages and the magnitude of some of them depended on the histological type, although not allowing AdC vs. SqCC discrimination. Moreover, it is shown in this chapter that age mismatch between control and cancer groups could not be ruled out as a possible confounding factor, and exploratory external validation afforded a classification rate of 85%. The NMR profiling of urine from lung cancer patients and healthy controls is presented in Chapter 5. Compared to plasma, the classification model built with urinary profiles resulted in a superior classification rate (97%). After careful assessment of possible bias from gender, age and smoking habits, a set of 19 metabolites was proposed to be cancer-related (out of which 3 were unknowns and 6 were partially identified as N-acetylated metabolites). As for plasma, these variations were detected regardless of disease stage and showed some dependency on histological subtype, the AdC vs. SqCC model built showing modest predictive power. In addition, preliminary external validation of the urine-based classification model afforded 100% sensitivity and 90% specificity, which are exciting results in terms of potential for future clinical application. Chapter 6 describes the analysis of urine from a subset of patients by a different profiling technique, namely, Ultra-Performance Liquid Chromatography coupled to Mass Spectrometry (UPLC-MS). Although the identification of discriminant metabolites was very limited, multivariate models showed high classification rate and predictive power, thus reinforcing the value of urine in the context of lung cancer diagnosis. Finally, the main conclusions of this thesis are presented in Chapter 7, highlighting the potential of integrated metabolomics of tissues and biofluids to improve current understanding of lung cancer altered metabolism and to reveal new marker profiles with diagnostic value.

Fiabilidade e validade do instrumento Physiosensing na avaliação do equilíbrio em pessoas com deficiência intelectual

Enquadramento: O ‘Physiosensing’ (‘PhyS’) é um dispositivo médico destinado ao treino do controlo postural nas posições de sentado e de pé, bem como no levantar e sentar, possibilitando também a avaliação do desempenho a este nível. Este trabalho teve como objetivo avaliar a fiabilidade e a validade da plataforma ‘Physiosensing’ na avaliação do equilíbrio em pessoas com deficiência intelectual (PCDI). Métodos: Para o grupo experimental (GE) foram recrutados 47 indivíduos com deficiência intelectual e para o grupo de controlo (GC) 39 indivíduos sem deficiência intelectual, provenientes da região do BaixoMondego. A avaliação da fiabilidade incluiu as análises da concordância entre observadores, reprodutibilidade temporal e consistência interna. A análise fatorial exploratória analisou os pressupostos de subdomínios propostos pelos autores. A validade discriminante foi analisada através da comparação de resultados entre o GE e o GC, e a validade concorrente pela análise dos valores de associação entre os resultados do ‘PhyS’ com a Escala de Equilíbrio de Berg (EEB). Resultados: O subconjunto de exercícios relacionados com a transferência de peso lateralmente (TPL) apresentou os resultados mais elevados a nível da concordância entre observadores (0,40 ≤ CCI > 0,75) e na reprodutibilidade intemporal (CCI ≥ 0,75). O instrumento apresenta uma consistência interna fraca (α = 0,63) quando considerados todos os exercícios, tendo-se obtido o melhor resultado para o subconjunto de exercícios TPL (α = 0,81). A análise fatorial exploratória devolveu quatro fatores, explicando 76,4% da variância, agrupando no primeiro fator o subconjunto de exercícios TPL. Foram encontradas diferenças estatisticamente significativas entre os resultados dos participantes com e sem deficiência intelectual, em dez dos onze exercícios que compõem a configuração da plataforma. Seis exercícios, que incluem os exercícios TPL, apresentam valores de associação estatisticamente significativos com a EEB. Conclusão: Alguns exercícios da plataforma ‘PhyS’ não se mostram adequados para medir o equilíbrio em PCDI, não podendo ser incluídos numa medida global. No entanto, os exercícios TPL poderão constituir um indicador global do equilíbrio em pessoas com PCDI. Recomenda-se a definição de procedimentos de medição de forma a melhorar os índices de fiabilidade, o aprofundamento da configuração de exercícios para a avaliação do equilíbrio e o estudo do potencial da plataforma em programas de intervenção para o treino das funções do equilíbrio.