Publication
Determination of (0,2)-regular sets in graphs
| dc.contributor.author | Pacheco, Maria F. | |
| dc.contributor.author | Cardoso, Domingos M. | |
| dc.contributor.author | Luz, Carlos J. | |
| dc.date.accessioned | 2014-10-01T09:36:46Z | |
| dc.date.available | 2014-10-01T09:36:46Z | |
| dc.date.issued | 2013 | |
| dc.description.abstract | 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. | por |
| dc.identifier.citation | 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 | por |
| dc.identifier.uri | http://hdl.handle.net/10198/10660 | |
| dc.language.iso | eng | por |
| dc.peerreviewed | yes | por |
| dc.publisher | Universidade de Aveiro | por |
| dc.subject | (0,2)-Regular sets | por |
| dc.subject | Main eigenvalues | por |
| dc.subject | Maximum matching | por |
| dc.title | Determination of (0,2)-regular sets in graphs | por |
| dc.type | conference poster | |
| dspace.entity.type | Publication | |
| oaire.citation.conferencePlace | Aveiro | por |
| oaire.citation.title | Research Day - Universidade de Aveiro | por |
| person.familyName | Pacheco | |
| person.givenName | Maria F. | |
| person.identifier.ciencia-id | F319-DAC3-8F15 | |
| person.identifier.orcid | 0000-0001-7915-0391 | |
| person.identifier.scopus-author-id | 36802474600 | |
| rcaap.rights | openAccess | por |
| rcaap.type | conferenceObject | por |
| relation.isAuthorOfPublication | e56596ca-3238-4fde-ace1-abb363a222e8 | |
| relation.isAuthorOfPublication.latestForDiscovery | e56596ca-3238-4fde-ace1-abb363a222e8 |