کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4625741 | 1631769 | 2016 | 4 صفحه PDF | دانلود رایگان |
In this paper we investigate the relation between odd components of co-trees and graph embeddings. We show that any graph G must share one of the following two conditions: (a) for each integer h such that G may be embedded on Sh, the sphere with h handles, there is a spanning tree T in G such that h=12(β(G)−ω(T)), where β(G) and ω(T) are, respectively, the Betti number of G and the number of components of G−E(T)G−E(T) having odd number of edges; (b) for every spanning tree T of G, there is an orientable embedding of G with exact ω(T)+1ω(T)+1 faces. This extends Xuong and Liu’s theorem [9,13] to some other (possible) genera. Infinitely many examples show that there are graphs which satisfy (a) but (b). Those make a correction of a result of Archdeacon [2, Theorem 1].
Journal: Applied Mathematics and Computation - Volume 286, 5 August 2016, Pages 228–231