科研之友
微信
新浪微博
Facebook
分享链接
摘要
This note provides a new perspective, i.e., graph embeddings on the decycling number del(G) (Beineke and Vandell in J Graph Theory 25:59-77, 1997) of a graph G. For this point, it is shown that del(G) = gamma(M)(G) + xi(G) for any cubic graph G and vertical bar S vertical bar = beta(G)+m(S)/k - 1 for any decycling set S of a k-regular graph G, where gamma(M)(G), xi(G), beta(G) and m(S) = c(G - S) + vertical bar E(S)vertical bar - 1 (c(G - S) is the number of components of G -S and vertical bar E(S)vertical bar is the number of edges in a subgraph G[S]) are, respectively, the maximum genus, the Betti deficiency (Xuong in J Combin Theory Ser B 26:217-225, 1979), the cycle rank (Harary in Graph theory, Academic Press, New York, 1967) and the margin number of G. Meanwhile, we further confirm that (1) a cubic graph G (G not equal K-4) has a vertex partition (V-1, V-2) such that V-1 is an independent set and V-2 induces a forest and (2) a k-regular graph G with del(G) = beta(G) + m(S)/k - 1 (m(S) <= 2) has a vertex partition (S, G - S) such that G[S] contains at most two edges andG-S induces a forest, where S is the smallest decycling set of G. Resorting to the above vertex partitions, we get the adjacent vertex distinguishing (AVD) total chromatic numbers of some families of graphs, and these results verify Zhang's conjecture (Zhang in Sci China Ser A 48:289-299, 2005) that every graph with maximum degree Delta has an AVD-total (Delta + 3)-coloring.
