Xuong tree

In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, a Xuong tree is a <a href="/facts/Spanning_tree/qQPN9taR">spanning tree</a> 
 
 
 
 T
 
 
 {\displaystyle T}
 
 of a given graph 
 
 
 
 G
 
 
 {\displaystyle G}
 
 with the property that, in the remaining graph 
 
 
 
 G
 −
 T
 
 
 {\displaystyle G-T}
 
, the number of <a href="/facts/Connected_component_(graph_theory)/5owVSXtY">connected components</a> with an odd number of edges is as small as possible.
They are named after Nguyen Huy Xuong, who used them to characterize the <a href="/facts/Graph_embedding/IyBA3ttM">cellular embeddings</a> of a given graph having the largest possible <a href="/facts/Genus_(mathematics)/o1Yhf8ty">genus</a>.
According to Xuong's results, if 
 
 
 
 T
 
 
 {\displaystyle T}
 
 is a Xuong tree
and the numbers of edges in the components of 
 
 
 
 G
 −
 T
 
 
 {\displaystyle G-T}
 
 are 
 
 
 
 
 m
 
 1
 
 
 ,
 
 m
 
 2
 
 
 ,
 …
 ,
 
 m
 
 k
 
 
 
 
 {\displaystyle m_{1},m_{2},\dots ,m_{k}}
 
, then the maximum genus of an embedding of 
 
 
 
 G
 
 
 {\displaystyle G}
 
 is 
 
 
 
 
 
 ∑
 
 i
 =
 1
 
 
 k
 
 
 ⌊
 
 m
 
 i
 
 
 
 /
 
 2
 ⌋
 
 
 
 {\displaystyle \textstyle \sum _{i=1}^{k}\lfloor m_{i}/2\rfloor }
 
.
Any one of these components, having 
 
 
 
 
 m
 
 i
 
 
 
 
 {\displaystyle m_{i}}
 
 edges, can be partitioned into 
 
 
 
 ⌊
 
 m
 
 i
 
 
 
 /
 
 2
 ⌋
 
 
 {\displaystyle \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 <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a>, by a transformation to a more general computational problem on <a href="/facts/Matroid/5bLcGlRF">matroids</a>, the <a href="/facts/Matroid_parity_problem/7r8TLTQp">matroid parity problem</a> for <a href="/facts/Linear_matroid/bYHY9rx1">linear matroids</a>.

Xuong tree open-in-new

Xuong tree