A note on delta-wye-delta reductions of plane graphs

Downloadable Content

Download this item
Abstract
  • A connected plane graph G with two distinguished vertices can be reduced to a single edge between these two vertices using certain local transformations, including series/parallel reductions and wye-delta and delta-wye transformations. Moreover a reduction consisting of these transformations can be found algorithmically in polynomial time. It follows that if an invariant of plane graphs is known to be #P-hard to compute then the invariant must be fundamentally incompatible with these local transformations in some way. We discuss two examples: polynomial invariants of knots and links and the reliability of plane networks.
TitleA note on delta-wye-delta reductions of plane graphs
CreatorTraldi, Lorenzo
PublisherCongressus Numerantium
Academic DepartmentMathematics
DivisionNatural Sciences
OrganizationLafayette College
Date Issued2002
Date Available2023-06-14
TypeArticle
LanguageEnglish
Bibliographic CitationTraldi, L. (2002) "A note on delta-wye-delta reductions of plane graphs." Congressus Numerantium 158: 213-220.
Standard IdentifierHandle 10385/sq87bw21w
Permalinkhttp://hdl.handle.net/10385/sq87bw21w
Rights Statement In Copyright In Copyright
Contains
File Traldi-CongressusNumerantium-vol158-2002.pdf Uploaded 2023-06-14 Public Download

Member of Collection

Faculty Publications

View Collection