Utilize este identificador para referenciar este registo:
|Título:||Determination of (0,2)-regular sets in graphs|
|Autor:||Pacheco, Maria F.|
Cardoso, Domingos Moreira
Luz, Carlos J.
|Editora:||Universidade de Aveiro|
|Citação:||Pacheco, Maria F.; Cardoso, Domingos Moreira; Luz, Carlos J. (2013) - Determination of (0,2)-regular sets in graphs. In Research Day - Universidade de Aveiro. Aveiro|
|Resumo:||An eigenvalue of a graph is main iff its associated eigenspace is not orthogonal to the all-one vector j. The main characteristic polynomial of a graph G with p main distinct eigenvalues is 𝑚_𝐺 (λ)=λ^𝑝−𝑐_0 λ^(𝑝−1)−𝑐_1 λ^(𝑝−2)-…-𝑐_(𝑝−2) λ−𝑐_(𝑝−1) and it has integer coefficients. If G has n vertices, the nxk walk matrix of G is 𝑾_𝒌=(j,𝑨_𝑮j,𝑨_𝑮^"2" "j",…,𝑨_𝑮^(𝒌−𝟏) j) and W, the walk matrix of G, is 𝑾_𝒌 for which rank(𝑾_𝒌)=k. The number k coincides with the number of distinct main eigenvalues of G. In  it was proved that the coefficients of the main characteristic polynomial of G are the solutions of 𝑾𝑿=𝑨_𝑮^𝒑j. A (,)- regular set  is a subset of the vertices of a graph inducing a -regular subgraph such that every vertex not in the subset has neighbors in it. In , a strategy for the determination of (0,1)-regular sets is described and we generalize it in order to solve the problem of the determination of (0,2)-regular sets in arbitrary graphs. An algorithm for deciding whether or not a given graph has a (0,2)-regular set is described. Its complexity depends on the multiplicity of −2 as an eigenvalue of the adjacency matrix of the graph. When such multiplicity is low, the generalization of the results in  assure that the algorithm is polynomial. An example of application of the algorithm to a graph for which this multiplicity is low is also presented.|
|Aparece nas colecções:||ESTiG - Posters em Encontros Científicos Internacionais|
Ficheiros deste registo:
|posterMFPACHECOcomlogos.pdf||1,7 MB||Adobe PDF||Ver/Abrir|
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.