Graphs with the Maximum or Minimum Number of 1-Factors
Discrete Mathematics, February 2010
Nathan W. Kahl, Ph.D. Department of Mathematics and Computer Science
Daniel Gross, Ph.D.Department of Mathematics and Computer Science
John T Saccoman, Jr. Ph.D.Department of Mathematics and Computer Science
Recently Alon and Friedland have shown that graphs which are the union of complete regular bipartite graphs have the maximum number of 1-factors over all graphs with the same degree sequence. We identify two families of graphs that have the maximum number of 1-factors over all graphs with the same number of vertices and edges: the almost regular graphs which are unions of complete regular bi-partite graphs, and complete graphs with a matching removed. The first family is determined using Alon and Friedland's bound. For the second family, we show that a graph transformation which is known to increase network reliability also increases the number of 1-factors. In fact, more is true: this graph transformation increases the number of k-factors for all k > 1, and \in reverse" also shows that in general, threshold graphs have the fewest k-factors. We are then able to determine precisely which threshold graphs have the fewest 1-factors. We conjecture that the same graphs have the fewest k-factors for all k > 2 as well.