کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648703 | 1342426 | 2010 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Graphs with the maximum or minimum number of 1-factors Graphs with the maximum or minimum number of 1-factors](/preview/png/4648703.png)
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 bipartite graphs, and complete graphs with a matching removed. The first family is determined using the Alon and Friedland 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 kk-factors for all k≥1k≥1, and “in reverse” also shows that in general, threshold graphs have the fewest kk-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 kk-factors for all k≥2k≥2 as well.
Journal: Discrete Mathematics - Volume 310, Issue 4, 28 February 2010, Pages 687–691