Browsing by Author "Rama, Paula"
Now showing 1 - 4 of 4
Results Per Page
Sort Options
- In search of a poset structure to the regular exceptional graphsPublication . Barbedo, Inês; Cardoso, Domingos M.; Rama, PaulaA (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. An exceptional graph is a connected graph with least eigenvalue greater than or equal to -2 which is not a generalized line graph, and it is shown that the set of regular exceptional graphs is partitioned in three layers. The idea of a recursive construction of regular exceptional graphs is proposed in [1]. With a new technique we prove that all regular exceptional graphs from the 1st and 2nd layer could be produced by this technique. The new recursive technique is based on the construction of families of regular graphs, where each regular graph is obtained by a (k,t)-extension defined by a k- regular graph H such that V(H) is a (k,t)-regular set of the extended regular graph. The process of extending a graph is reduced to the construction of the incidence matrix of a combinatorial 1-design, and these extensions induce a partial order. Considering several rules to reduce the production of isomorphic graphs, each exceptional regular graph is constructed by a (0,2)-extension. Based on this construction, an algorithm to produce the regular exceptional graphs of the 1st and 2nd layer is introduced and the corresponding poset is presented, using its Hasse diagram.
- A recursive construction of the regular exceptional graphs with least eigenvalue –2Publication . Barbedo, Inês; Cardoso, Domingos M.; Cvetković, Dragoš; Rama, Paula; Simić, SlobodanIn spectral graph theory a graph with least eigenvalue −2 is exceptional if it is connected, has least eigenvalue greater than or equal to −2, and it is not a generalized line graph. A (κ,τ)-regular set S of a graph is a vertex subset, inducing a κ-regular subgraph such that every vertex not in S has τ neighbors in S. We present a recursive construction of all regular exceptional graphs as successive extensions by regular sets.
- The construction of the poset of regular execeptional graphs using equitable partitionsPublication . Barbedo, Inês; Cardoso, Domingos M.; Rama, PaulaAn 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 regular exceptional graph of the first and the second layer is constructed by a (0,2)-regular set extension. In this talk we present an algorithm based on this recursive construction and show that this technique induces a partial order relation on the set of regular exceptional graphs. 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, and we show that each regular exceptional graph has an equitable partition which, by this construction technique, is extended with a new element, the set of the additional vertices. The recursive construction is generalized to the construction of arbitrary families of regular graphs, by extending a regular graph G with another regular graph H such that V(H) is a (k,t)-regular set of the regular graph produced. This technique is used to construct the exceptional regular graphs of the third layer. The Hasse diagrams of the posets of the three layers are presented.
- The poset structure of the regular exceptional graphsPublication . Barbedo, Inês; Cardoso, Domingos M.; Rama, PaulaAn 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.