Idioma:

Extremal Threshold Graphs for Matchings and Independent Sets

Keough, L. ; Radcliffe, A. J.

Graphs and combinatorics, 2018-11, Vol.34 (6), p.1519-1537 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por

Título:
Extremal Threshold Graphs for Matchings and Independent Sets
Autor: Keough, L. ; Radcliffe, A. J.
Assuntos: Apexes ; Combinatorics ; Engineering Design ; Graph theory ; Graphs ; Mathematics ; Mathematics and Statistics ; Original Paper
É parte de: Graphs and combinatorics, 2018-11, Vol.34 (6), p.1519-1537
Descrição: Many extremal problems for graphs have threshold graphs as their extremal examples. For instance the current authors proved that for fixed k ≥ 1 , among all graphs on n vertices with e edges, some threshold graph has the fewest matchings of size k ; indeed either the lex graph or the colex graph is such an extremal example. In this paper we consider the problem of maximizing the number of matchings in the class of threshold graphs. We prove that the minimizers are what we call almost alternating threshold graphs . We also discuss a problem with a similar flavor: which threshold graph has the fewest independent sets. Here we are inspired by the result that among all graphs on n vertices and e edges the lex graph has the most independent sets.
Editor: Tokyo: Springer Japan
Idioma: Inglês

Voltar para lista de resultados

Anterior Resultado 8 Avançar Ir para próxima página