ESTiG - Posters em Encontros Cientรญficos Internacionais
Permanent URI for this collection
Browse
Browsing ESTiG - Posters em Encontros Cientรญficos Internacionais by Subject "(0,2)-Regular sets"
Now showing 1 - 1 of 1
Results Per Page
Sort Options
- Determination of (0,2)-regular sets in graphsPublication . Pacheco, Maria F.; Cardoso, Domingos M.; Luz, Carlos J.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 [2] it was proved that the coefficients of the main characteristic polynomial of G are the solutions of ๐พ๐ฟ=๐จ_๐ฎ^๐j. A (๏ซ,๏ด)- regular set [3] 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 [1], 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 [1] 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.