| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 736.85 KB | Adobe PDF |
Advisor(s)
Abstract(s)
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.
Description
Keywords
Regular graphs Poset 1-design Exceptional graphs
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