Publication
The poset structure of the regular exceptional graphs
| dc.contributor.author | Barbedo, Inês | |
| dc.contributor.author | Cardoso, Domingos M. | |
| dc.contributor.author | Rama, Paula | |
| dc.date.accessioned | 2014-10-17T15:51:32Z | |
| dc.date.available | 2014-10-17T15:51:32Z | |
| dc.date.issued | 2013 | |
| dc.description.abstract | An exceptional graph is a connected graph with least eigenvalue greater than or equal to -2 which is not a generalized line graph. It is shown that the set of regular exceptional graphs is partitioned in three layers. A (k,t)-regular set is a subset of the vertices of a graph, inducing a k-regular subgraph such that every vertex not in the subset has t neighbors in it. A new recursive construction of regular exceptional graphs is proposed, where each exceptional regular graph is constructed by a (0,2)-regular set extension. These extensions induce a partial order on the set on the exceptional graphs in each layer. Based on this construction, an algorithm to produce the regular exceptional graphs of the first and second layer is introduced and the corresponding poset is presented, using its Hasse diagram. The process of extending a graph is reduced to the construction of the incidence matrix of a combinatorial 1-design, considering several rules to prevent the production of isomorphic graphs. A generalization of this recursive procedure to the construction of families of regular graphs, where each regular graph is obtained by a (k,t)-regular extension defined by a k-regular graph H such that V(H) is a (k,t)-regular set of the extended regular graph, is introduced. Finally, some results on the multiplicity of the eigenvalue k-t are presented. | por |
| dc.description.sponsorship | supported by Portuguese funds through the CIDMA - Center for Research and Development in Mathematics and Applications, and the Portuguese Foundation for Science and Technology ("FCT–Fundação para a Ciência e a Tecnologia") | por |
| dc.identifier.citation | Barbedo, Inês; Cardoso, Domingos M.; Rama, Paula (2013). The poset structure of the regular exceptional graphs. In 26th Conference of the European Chapter on Combinatorial Optimization. Paris | por |
| dc.identifier.uri | http://hdl.handle.net/10198/10889 | |
| dc.language.iso | eng | por |
| dc.peerreviewed | yes | por |
| dc.subject | Regular graphs | por |
| dc.subject | Poset | por |
| dc.subject | 1-design | por |
| dc.subject | Exceptional graphs | por |
| dc.title | The poset structure of the regular exceptional graphs | por |
| dc.type | conference object | |
| dspace.entity.type | Publication | |
| oaire.citation.conferencePlace | Paris, França | por |
| oaire.citation.title | 26th Conference of the European Chapter on Combinatorial Optimization | por |
| person.familyName | Barbedo | |
| person.givenName | Inês | |
| person.identifier.ciencia-id | 681B-7253-50B1 | |
| person.identifier.orcid | 0000-0001-6350-9697 | |
| rcaap.rights | openAccess | por |
| rcaap.type | conferenceObject | por |
| relation.isAuthorOfPublication | 8a4e21c4-845a-4fb3-a772-bab297bae908 | |
| relation.isAuthorOfPublication.latestForDiscovery | 8a4e21c4-845a-4fb3-a772-bab297bae908 |