Encontrados 10 documentos, a visualizar página 1 de 1
In search of a poset structure to the regular exceptional graphs
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 ...
The poset structure of the regular exceptional graphs
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 ex...
The construction of the poset of regular execeptional graphs using equitable pa...
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 ...
Algorithmic strategies for the recognition of graphs with convex
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 ...
Algorithmic strategies for the recognition of graphs with convex quadratic stab...
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 ...
Recognition of graphs with convex quadratic stability number
Pacheco, Maria F.; Cardoso, Domingos M.A stable set of a graph is a set of mutually non-adjacent vertices. The determination of a maximum size stable set, which is called maximum stable set, and the determination of its size, which is called stability number, are central combinatorial optimization problems. However, given a nonnegative integer k, to determine if a graph G has a stable set of size k is NP-complete. In this paper we deal with graphs f...
Graphs with convex quadratic stability number
Pacheco, Maria F.; Cardoso, Domingos M.The main results about graphs with convex quadratic stability number (that is, graphs for which the stability number can be determined by convex quadratic programming) are surveyed including the most recently obtained. Furthermore, a few algorithmic techniques for the recognition of this type of graphs in particular families are presented.
Reconhecimento de grafos com número de estabilidade quadrático convexo
Pacheco, Maria F.; Cardoso, Domingos M.São apresentados os principais e mais recentes resultados sobre grafos com número de estabilidade quadrático convexo (que são grafos cujo número de estabilidade pode ser determinado através de técnicas de programação quadrática convexa) e descritas algumas estratégias algorítmicas para o reconhecimento de grafos deste tipo em famílias particulares.
Efficient edge domination in regular graphs
Cardoso, Domingos M.; Cerdeira, J.Orestes; Delorme, Charles; Silva, Pedro C.An induced matching of a graph G is a matching having no two edges joined by an edge. An efficient edge dominating set of G is an induced matching M such that every other edge of G is adjacent to some edge in M. We relate maximum induced matchings and efficient edge dominating sets, showing that efficient edge dominating sets are maximum induced matchings, and that maximum induced matchings on regular graphs wi...
Graphs with least eigenvalue -2 attaining a convex quadratic upper bound for th...
Cardoso, Domingos M.; Cvetkovic, D.In this paper we study the conditions under which the stability number of line graphs, generalized line graphs and exceptional graphs attains a convex quadratic programming upper bound. In regular graphs this bound is reduced to the well known Hoffman bound. Some vertex subsets inducing subgraphs with regularity properties are analyzed. Based on an observation concerning the Hoffman bound a new construction of ...
| Financiadores do RCAAP | |||||||
|
|
|
|
|
|
||