Browsing by Author "Cardoso, Domingos M."
Now showing 1 - 10 of 18
Results Per Page
Sort Options
- Algorithmic strategies for the recognition of graphs with convex quadratic stability numberPublication . Pacheco, Maria F.; Luz, Carlos J.; Cardoso, Domingos M.A major difficulty in the recognition of graphs with convex quadratic stability number is the existence of adverse subgraphs (an adverse subgraph is a subgraph such that the smallest eigenvalue of its adjacency matrix doesn’t change when any vertex or the neighbourhood of any vertex is deleted). It is a challenge to find adverse graphs without convex quadratic stability number. We present the main results about graphs with convex quadratic stability number and conclusions about the existence of adverse subgraphs belonging to this family in certain classes of graphs.
- Algorithmic strategies for the recognition of graphs with convex quadratic stability numberPublication . Pacheco, Maria F.; Luz, Carlos J.; Cardoso, Domingos M.A major difficulty in the recognition of graphs with convex quadratic stability number is the existence of adverse subgraphs (an adverse subgraph is a subgraph such that the smallest eigenvalue of its adjacency matrix doesn’t change when any vertex or the neighbourhood of any vertex is deleted). It is a challenge to find adverse graphs without convex quadratic stability number. We present the main results about graphs with convex quadratic stability number and conclusions about the existence of adverse subgraphs belonging to this family in certain classes of graphs.
- Convex quadratic programming applied to the stability number of a graphPublication . Pacheco, Maria F.; Cardoso, Domingos M.; Luz, Carlos J.We deal with graphs whose stability number can be determined by a convex quadratic program and describe algorithmic techniques for the determination of maximum stable sets in such graphs.
- Determinação de conjuntos (0,2)-regulares em grafos e aplicaçõesPublication . Pacheco, Maria F.; Cardoso, Domingos M.; Luz, Carlos J.Um conjunto (kappa,tau)-regular num grafo é um subconjunto de vértices que induz um subgrafo kappa-regular com a seguinte propriedade: cada vértice não pertencente ao conjunto tem nele exactamente tau vizinhos. Neste trabalho apresenta-se um novo algoritmo para a determinação de conjuntos (0,2)-regulares em grafos linha com a aplicação na determinação de emparelhamentos máximos em grafos com recurso à programação quadrática convexa.
- 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 . 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.
- 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.
- Efficient domination through eigenvaluesPublication . Cardoso, Domingos M.; Lozin, Vadim V.; Luz, Carlos J.; Pacheco, Maria F.The paper begins with a new characterization of (k,τ)-regular sets. Then, using this result as well as the theory of star complements, we derive a simplex-like algorithm for determining whether or not a graph contains a (0,τ)-regular set. When τ = 1, this algorithm can be applied to solve the efficient dominating set problem which is known to be NP- complete. If −1 is not an eigenvalue of the adjacency matrix of the graph, this particular algorithm runs in polynomial time. However, although it doesn’t work in polynomial time in general, we report on its successful application to a vast set of randomly generated 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.