Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
The Merino-Welsh conjecture holds for series-parallel graphs
Noble S., Royle G.  European Journal of Combinatorics 38 24-35, 2014. Type: Article
Date Reviewed: Aug 20 2014

Orientation is an assignment of direction to each edge of an undirected graph. When none of the directed edges is in a cycle, the orientation is called acyclic. When every directed edge is in some cycle, the orientation is called totally cyclic.

A spanning tree of an undirected graph is a connected subgraph, including all its vertices, but containing no cycles. The number of spanning trees seems to have a relationship with the numbers of acyclic and totally cyclic orientations of the graph. Yet, proof of such a relation for a general graph is still elusive.

The Merino-Welsh conjecture, the subject of this paper, suggests that the maximum of the numbers of acyclic and totally cyclic orientations will always be greater than or equal to the number of spanning trees of a bridgeless and loopless graph. It is an interesting problem to prove, and the authors have done an excellent job in establishing it for a special class of graphs.

Starting with an engaging introduction, where the background material is quickly presented along with examples, the authors lead us into lemmas in section 2, which explore the characteristics of a minimal counterexample to the conjecture. The discussion moves onto two terminal series parallel (TTSP) graphs in section 3. Duality that respects the terminals, called sp-duality, is introduced. Lemmas that track the relations between the parameters of interest through the series/parallel connection are rendered.

The core contributions of the paper are outlined in section 4. The multiplicative form of the Merino-Welsh conjecture is where the difficulty is, and the replaceability of a TTSP graph by another is defined in terms of this form. Further, a TTSP graph is called reducible if it can be replaced by another with fewer edges. Extendibility is defined based on the series/parallel class of each edge. By making use of lemmas on these concepts, a procedure to systematically construct all series-parallel graphs is provided and leads to the desired result. Surprisingly, all of the extendable and irreducible TTSP graphs can be shown in a short list, as demonstrated in a table in the paper.

Overall, this is an impressive paper with an absorbing substantiation of the combinatorics involved.

Reviewer:  Paparao Kavalipati Review #: CR142633 (1411-0976)
Bookmark and Share
  Editor Recommended
Featured Reviewer
Combinatorics (G.2.1 )
Graph Theory (G.2.2 )
Would you recommend this review?
Other reviews under "Combinatorics": Date
An introduction to Catalan numbers
Roman S.,  Springer, New York, NY, 2015. 121 pp. Type: Book (978-3-319221-43-4)
Apr 4 2016
New complete Latin squares of odd order
Ollis M.  European Journal of Combinatorics 4135-46, 2014. Type: Article
May 20 2015
ReCombinatorics: the algorithmics of ancestral recombination graphs and explicit phylogenetic networks
Gusfield D.,  The MIT Press, Cambridge, MA, 2014. 600 pp. Type: Book (978-0-262027-52-6)
Jan 8 2015

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2017 ThinkLoud, Inc.
Terms of Use
| Privacy Policy