Paper Info
Title
Extremal Threshold Graphs for Matchings and Independent Sets.
Abstract
Many extremal problems for graphs have threshold graphs as their extremal examples. For instance the current authors proved that for fixed \(k\ge 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.
Year
DOI
Venue
2018
10.1007/s00373-018-1941-5
Graphs and Combinatorics
Keywords
Field
DocType
Threshold graphs, Independent sets, Matchings, Almost alternating graphs, Extremal graph theory, 05C35
Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Threshold graph,Mathematics
Journal
Volume
Issue
ISSN
34
6
0911-0119
Citations 
PageRank 
References 
0
0.34
2
Authors
2
Name
Order
Citations
PageRank
Lauren Keough101.01
A. j. Radcliffe28115.68