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 Combinatorics38 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
Applied combinatorics with problem solving
Jackson B., Thoro D., Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992. Type: Book (9780201129083)
Feb 1 1993
Parallel generation of permutations and combinations
Chen G., Chern M. BIT 26(3): 277-283, 1986. Type: Article
Jul 1 1988
Network design with non simultaneous flows
Lucertini M. (ed), Paletta G., Springer-Verlag New York, Inc., New York, NY, 1984. Type: Book (9780387818160)
Jun 1 1985

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy