The extremal genus embedding of graphs

Details The extremal genus embedding of graphs The extremal genus embedding of graphs

2012-03-05

arxiv.org/abs/1203.0864v1

Mathematics

Combinatorics

Scientific paper

Let Wn be a wheel graph with n spokes. How does the genus change if adding a degree-3 vertex v, which is not in V (Wn), to the graph Wn? In this paper, through the joint-tree model we obtain that the genus of Wn+v equals 0 if the three neighbors of v are in the same face boundary of P(Wn); otherwise, {\deg}(Wn + v) = 1, where P(Wn) is the unique planar embedding of Wn. In addition, via the independent set, we provide a lower bound on the maximum genus of graphs, which may be better than both the result of D. Li & Y. Liu and the result of Z. Ouyang etc: in Europ. J. Combinatorics. Furthermore, we obtain a relation between the independence number and the maximum genus of graphs, and provide an algorithm to obtain the lower bound on the number of the distinct maximum genus embedding of the complete graph Km, which, in some sense, improves the result of Y. Caro and S. Stahl respectively.

Affiliated with

Also associated with

No associations

Rating

The extremal genus embedding of graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The extremal genus embedding of graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The extremal genus embedding of graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-132748