Xuong tree

File:Xuong tree.svg

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.{{r|bw}}

They are named after Nguyen Huy Xuong, who used them to characterize the cellular embeddings of a given graph having the largest possible genus.{{r|x}}

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$ .{{r|bw|x}}

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.{{r|s}}

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.{{r|bw|x}}

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.{{r|bw|fgm}}

References

{{reflist|refs=

{{citation

| last1 = Beineke | first1 = Lowell W. | author1-link = L. W. Beineke

| last2 = Wilson | first2 = Robin J. | author2-link = Robin Wilson (mathematician)

| doi = 10.1017/CBO9781139087223

| isbn = 978-0-521-80230-7

| mr = 2581536

| page = 36

| publisher = Cambridge University Press, Cambridge

| series = Encyclopedia of Mathematics and its Applications

| title = Topics in topological graph theory

| volume = 128

| year = 2009}}

{{citation

| last1 = Furst | first1 = Merrick L.

| last2 = Gross | first2 = Jonathan L.

| last3 = McGeoch | first3 = Lyle A.

| doi = 10.1145/44483.44485

| issue = 3

| journal = Journal of the ACM

| mr = 963159

| pages = 523–534

| title = Finding a maximum-genus graph imbedding

| volume = 35

| year = 1988| s2cid = 17991210

| doi-access = free

}}

{{Citation

| last = Sumner | first = David P. | authorlink = David Sumner

| doi = 10.2307/2039666

| mr = 0323648

| journal = Proceedings of the American Mathematical Society

| pages = 8–12

| title = Graphs with 1-factors

| volume = 42

| year = 1974

| issue = 1

| publisher = American Mathematical Society

| jstor = 2039666}}

{{citation

| last = Xuong | first = Nguyen Huy

| doi = 10.1016/0095-8956(79)90058-3

| hdl =

| issue = 2

| journal = Journal of Combinatorial Theory

| mr = 532589

| pages = 217–225

| series = Series B

| title = How to determine the maximum genus of a graph

| volume = 26

| year = 1979| doi-access = free

}}

Category:Spanning tree

Category:Topological graph theory