Misplaced Pages

Xuong tree

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
A Xuong tree. Only one component of the non-tree edges (the red component) has an odd number of edges, the minimum possible for this graph.

In graph theory, a Xuong tree is a spanning tree 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 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 {\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 polynomial time, by a transformation to a more general computational problem on matroids, the matroid parity problem for linear matroids.

References

  1. ^ Beineke, Lowell W.; Wilson, Robin J. (2009), Topics in topological graph theory, Encyclopedia of Mathematics and its Applications, vol. 128, Cambridge University Press, Cambridge, p. 36, doi:10.1017/CBO9781139087223, ISBN 978-0-521-80230-7, MR 2581536
  2. ^ Xuong, Nguyen Huy (1979), "How to determine the maximum genus of a graph", Journal of Combinatorial Theory, Series B, 26 (2): 217–225, doi:10.1016/0095-8956(79)90058-3, MR 0532589
  3. Sumner, David P. (1974), "Graphs with 1-factors", Proceedings of the American Mathematical Society, 42 (1), American Mathematical Society: 8–12, doi:10.2307/2039666, JSTOR 2039666, MR 0323648
  4. Furst, Merrick L.; Gross, Jonathan L.; McGeoch, Lyle A. (1988), "Finding a maximum-genus graph imbedding", Journal of the ACM, 35 (3): 523–534, doi:10.1145/44483.44485, MR 0963159, S2CID 17991210
Categories: