Structure Of Short Cycles In Graphs And Some Related Topics

In the first part of this paper, we study short cycles in embedded graphs. Finding short cycles plays an important role in many fields such as topological graph theory where people usually need to find some types of short cycles which describe how well a graph is embedded into a given surface. For instance if the length of shortest noncontractible cycles is long enough, then the embedded graph will share many important properties with planar graphs [37]. In the graph coloring theory, people always give a restriction of shortest cycles which may result in a desired coloring of graphs. For instance, if the edge width of an embedded graph is large enough, then the graph may be properly colored with5colors [38]. Let C1be the set of fundamental cycles of breadth-first-search trees in a graph G, and let C2be the set of the sums of two cycles in C1. Then we show the following:(1) C=C1∪C2(have O(n6) elements, n=|y(G)|) contains a shortest Ⅱ-twosided cycle in a Ⅱ-embedded graph G. This implies the existence of a polynomially bounded algorithm to find a shortest II-twosided cycle in an embedded graph and thus solves an open problem of Mohar and Thomassen [25p.112].(2) C contains all the possible shortest even cycles in a graph G. Therefore, there are at most polynomially many (O(n6)) shortest even cycles in any graph.(3) Let Co be the set of all the shortest cycles of a graph G. Then Co is a subset of C. Furthermore, many types of shortest cycles are contained in Co ((?) C). Infinitely many examples show that there are exponentially many shortest odd cycles, shortest Ⅱ-onesided cycles and shortest Ⅱ-twosided cycles in some (embedded) graphs.In the second part of this paper, we study the number of1-factors and edge-colorings of the Mobius ladder graphs.(In the history of solving of the famous Heawood Conjecture in coloring graphs on general surfaces, all the triangular embeddings for the complete graph Kn are "men-made"(i.e., in-duced from current graphs with few indexes). One may asks that what does these triangulations look like? One may readily see that a Mobius ladder graph is a underline graph of a type of current graph by Youngs). We find exact formulae for such numbers and show that there are exponentially many1-factors and edge-colorings in such graphs. As applications, we show that every "men-made" triangular embedding for K12m+7by the current graphs by these of Youngs and Ringel permits exponentially many " Grunbaum col-oring"(i.e.,3-edge-colored triangulations in such a way that each triangle receives three distinct colors).In the third part of this paper, we study monochromatic matchings of any2-edge-coloring K2s+t-1·Cockayne and Lorimer[8] showed that in any2-edge-coloring K2s+t-1(s≥t≥1)there exists an s-matching receiving the same color (people call such matchings monochromatic matchings) or a t-matching having another color. In this paper we show that the number of such monochromatic matchings may be exponentially many, and thus improve above result of Cockayne and Lorimer. We show that in any2-edge-coloring of K2s+t-1(s≥t≥1) there either exist at least2[s/2]many s-matchings with the same color or2[t/2] many t-matchings with another color. In addition we show that in any2-edge-coloring of K2S+t-1(s≥t≥1) there are either at least2[t/2]f(n) many s-matchings receiving the same color or at least2[t/2] many t-matchings of another color, where f(n)=(2n-1)!!, and n=s-t. These not only generalize a Ramsey number by Erdos et al [13] and Gerencser et al [15] but also improve a lower bound of the number of such matching by the present authors [5]. In the fourth part of this paper, a weighted graph embedded in a surface is called LEW-embedded if every noncontractible cycle is longer than every facial walk. A fundamental graph result of Whitney [44] says that a3-connected planar graph has a unique embedding on the sphere. Tutte [41] obtained Whitney’s uniqueness theorem from a combinatorial description of the facial cycles in3-connected planar graphs. In order to gereralizing these results to higher surfaces, Thomassen studied almost every aspect of LEW-embedding of unweighted graphs, and successfully extend Whitney’s theories to higher surfaces in the case of LEW-embedding. In this process, Thomassen also showed that there exist a polynomially bounded algorithm which, for any3-connected graph G, describes an LEW-embedding of G or tells that G has no LEW-embedding. But how about the weighted graph? Mohar and Thomassen asked an open problem [25p.134-135]:Do there exist polynomially bounded algorithms for the following problems:(a) Given is a graph G embedded in a surface S. Does G have an LEW-weight function?(b) Does a given graph G have an embedding which admits an LEW-weight function? We study the LEW-embeddability of weighted grads graph G(a,b)(a≥2, b≥2) and the Mobius ladder graph Gn(n≥4) and show that such two types of weighted graphs have no LEW-embeddings. Based on these two kinds of graphs we construct weighted graphs which are strongly embedded in Sn and Nn and permit no LEW-embeddings in the same surface they embedded. Our results show:for any surface E, there exist a type of graphs, s.t., these graphs have no weighted LEW-embeddings. And thus give an approach of problem (a) and (b).