Xuong tree

In graph theory, a Xuong tree is a spanning tree T of a given graph G with the property that, in the remaining graph G-T , the number of connected components with an odd number of edges is as small as possible.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In graph theory, a Xuong tree is a spanning tree T of a given graph G with the property that, in the remaining graph G-T , the number of connected components with an odd number of edges is as small as possible. They are named after Nguyen Huy Xuong, who used them to characterize the cellular embeddings of a given graph having the largest possible genus.

According to Xuong's results, if T is a Xuong tree and the numbers of edges in the components of G-T are m_1,m_2,\dots, m_k , then the maximum genus of an embedding of G is \textstyle\sum_{i=1}^k\lfloor m_i/2\rfloor . Any one of these components, having m_i edges, can be partitioned into \lfloor m_i/2\rfloor edge-disjoint two-edge paths, with possibly one additional left-over edge.

An embedding of maximum genus may be obtained from a planar embedding of the Xuong tree by adding each two-edge path to the embedding in such a way that it increases the genus by one. A Xuong tree, and a maximum-genus embedding derived from it, may be found in any graph in polynomial time, by a transformation to a more general computational problem on matroids, the matroid parity problem for linear matroids.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1329719589 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001329719589 · captured 2025-12-27 · not yet sealed in the ledger · verify the chain · version history

Cite this page as: encyclopegia.org, “Xuong tree”, snapshot enwiki-001329719589. https://encyclopegia.org/a/xuong-tree

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.