Escola Superior de Tecnologia e Gestão
Permanent URI for this community
Browse
Browsing Escola Superior de Tecnologia e Gestão by Subject "(0,2)-Regular sets"
Now showing 1 - 5 of 5
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.
- Determination of (0,2)-regular sets in graphs and applicationsPublication . Pacheco, Maria F.; Cardoso, Domingos M.; Luz, Carlos J.A (k,tau)- regular set in a graph is a subset of vertices inducing a tau-regular subgraph and such that each vertex not in the set has exactly tau neighbours in it. We will present a new algorithm for the determination of (0, 2)- regular sets as well as its application to the determination of maximum matchings in arbitrary graphs.
- Determination of (0,2)-regular sets in graphs and applicationsPublication . Pacheco, Maria F.; Cardoso, Domingos M.; Luz, Carlos J.A (k,τ)-regular set in a graph is a subset of vertices inducing a k-regular subgraph and such that each vertex not in the set has exactly τ neighbours in it. We will present a new algorithm for the determination of (0,2)-regular sets as well as its application to the determination of maximum matchings in arbitrary graphs.
- Determination of (0,2)-regular sets in graphs and applicationsPublication . Cardoso, Domingos M.; Luz, Carlos J.; Pacheco, Maria F.In this paper, relevant results about the determination of ( κ , τ )- 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.
- How to solve the maximum matching problem determining (0,2)-regular setsPublication . Pacheco, Maria F.; Cardoso, Domingos M.; Luz, Carlos J.A (K-1)-regular set in a graph is a subset of vertices such that each vertex in the set hask neighbours in it and each vertex not in the set has exactly i neighbours in it.