Exponentially many maximum genus embeddings and genus embeddings for complete graphs

There are many results on the maximum genus, among which most are written for the existence of values of such embeddings, and few attention has been paid to the estimation of such embeddings and their applications. In this paper we study the number of maximum genus embeddings for a graph and find an exponential lower bound for such numbers. Our results show that in general case, a simple connected graph has exponentially many distinct maximum genus embeddings. In particular, a connected cubic graph G of order n always has at least distinct maximum genus embeddings, where α and m denote, respectively, the number of inner vertices and odd components of an optimal tree T. What surprise us most is that such two extremal embeddings (i.e., the maximum genus embeddings and the genus embeddings) are sometimes closely related with each other. In fact, as applications, we show that for a sufficient large natural number n, there are at least many genus embeddings for complete graph K _n with n ≡ 4, 7, 10 (mod12), where C is a constance depending on the value of n of residue 12. These results improve the bounds obtained by Korzhik and Voss and the methods used here are much simpler and straight. This work was supported by the National Natural Science Foundation of China (Grant No. 10671073), Science and Technology commission of Shanghai Municipality (Grant No. 07XD14011) and Shanghai Leading Academic Discipline Project (Grant No. B407)     

Cubic one-regular graphs of order twice a square-free integer

A graph is one-regular if its automorphism group acts regularly on the set of its arcs.Let n be a square-free integer.In this paper,we show that a cubic one-regular graph of order 2n exists if and only if n=3~tp1p2…p_s≥13,where t≤1,s≥1 and p_i's are distinct primes such that 3|(P_i—1). For such an integer n,there are 2~(s-1) non-isomorphic cubic one-regular graphs of order 2n,which are all Cayley graphs on the dihedral group of order 2n.As a result,no cubic one-regular graphs of order 4 times an odd square-free integer exist.     

Adjacent strong edge colorings and total colorings of regular graphs

It is conjectured that χas(G) = χt(G) for every k-regular graph G with no C5 component (k 2). This conjecture is shown to be true for many classes of graphs, including: graphs of type 1; 2-regular, 3-regular and (|V (G)| - 2)-regular graphs; bipartite graphs; balanced complete multipartite graphs; k-cubes; and joins of two matchings or cycles.     

Integral formula of Minkowski type and new characterization of the Wulff shape

Given a positive function F on S^n which satisfies a convexity condition, we introduce the r-th anisotropic mean curvature Mr for hypersurfaces in R^n＋1 which is a generalization of the usual r-th mean curvature Hr. We get integral formulas of Minkowski type for compact hypersurfaces in R^n＋1. We give some new characterizations of the Wulff shape by the use of our integral formulas of Minkowski type, in case F=1 which reduces to some well-known results.     

Admissible wavelets on the Siegel domain of type one

LetSp(n, R) be the sympletic group, and letK _n * be its maximal compact subgroup. ThenG=Sp(n,R)/K _n * can be realized as the Siegel domain of type one. The square-integrable representation ofG gives the admissible wavelets AW and wavelet transform. The characterization of admissibility condition in terms of the Fourier transform is given. The Bergman kernel follows from the viewpoint of coherent state. With the Laguerre polynomials, Hermite polynomials and Jacobi polynomials, two kinds of orthogonal bases for AW are given, and they then give orthogonal decompositions ofL ²-space on the Siegel domain of type one ℒ(ℋ _n , |y| *dxdy). Project supported in part by the National Natural Science Foundation of China (Grant No. 19631080).     

Up-embeddability via girth and the degree-sum of adjacent vertices

Let G be a simple graph of order n and girth g. For any two adjacent vertices u and v of G, if d _G (u) + d _G (v) ⩾ n − 2g + 5 then G is up-embeddable. In the case of 2-edge-connected (resp. 3-edge-connected) graph, G is up-embeddable if d _G (u) + d _G (v) ⩾ n − 2g + 3 (resp. d _G (u) + d _G (v) ⩾ n − 2g −5) for any two adjacent vertices u and v of G. Furthermore, the above three lower bounds are all shown to be tight. This work was supported by National Natural Science Foundation of China (Grant No. 10571013)     

The analysis of a nested dissection algorithm

Summary Nested dissection is an algorithm invented by Alan George for preserving sparsity in Gaussian elimination on symmetric positive definite matrices. Nested dissection can be viewed as a recursive divide-and-conquer algorithm on an undirected graph; it usesseparators in the graph, which are small sets of vertices whose removal divides the graph approximately in half. George and Liu gave an implementation of nested dissection that used a heuristic to find separators. Lipton and Tarjan gave an algorithm to findn ^1/2-separators in planar graphs and two-dimensional finite element graphs, and Lipton, Rose, and Tarjan used these separators in a modified version of nested dissection, guaranteeing bounds ofO (n logn) on fill andO(n ^3/2) on operation count. We analyze the combination of the original George-Liu nested dissection algorithm and the Lipton-Tarjan planar separator algorithm. This combination is interesting because it is easier to implement than the Lipton-Rose-Tarjan version, especially in the framework of existïng sparse matrix software. Using some topological graph theory, we proveO(n logn) fill andO(n ^3/2) operation count bounds for planar graphs, twodimensional finite element graphs, graphs of bounded genus, and graphs of bounded degree withn ^1/2-separators. For planar and finite element graphs, the leading constant factor is smaller than that in the Lipton-Rose-Tarjan analysis. We also construct a class of graphs withn ^1/2-separators for which our algorithm does not achieve anO(n logn) bound on fill.The work of this author was supported in part by the Hertz Foundation under a graduate fellowship and by the National Science Foundation under Grant MCS 82-02948The work of this author was supported in part by the National Science Foundation under Grant MCS 78-26858 and by the Office of Naval Research under Contract N00014-76-C-0688     

Asymptotic distributions of non-central studentized statistics

Let X1,...,Xn be independent and identically distributed random variables and Wn = Wn(X1,...,Xn) be an estimator of parameter θ.Denote Tn =(Wn - θ0)/sn,where sn2 is a variance estimator of Wn.In this paper a general result on the limiting distributions of the non-central studen-tized statistic Tn is given.Especially,when s2n is the jacknife estimate of variance,it is shown that the limit could be normal,a weighted χ2 distribution,a stable distribution,or a mixture of normal and stable distribution.Applicati...     

Quadrilateral embeddings of bipartite graphs

Current graphs and a theorem of White are used to show the existence of almost complete regular bipartite graphs with quadrilateral embeddings conjectured by Pisanski. Decompositions of K_n and K_{n, n} into graphs with quadrilateral embeddings are discussed, and some thickness results are obtained. Some new genus results are also obtained.     

Disproof of a conjecture in graph reconstruction theory

In his thesis [3] B. D. Thatte conjectured that ifG=G ₁,G ₂,...G _n is a sequence of finitely many simple connected graphs (isomorphic graphs may occur in the sequence) with the same number of vertices and edges then their shuffled edge deck uniquely determines the graph sequence (up to a permutation). In this paper we prove that there are such sequences of graphs with the same shuffled edge deck.This research was partially supported by Hungarian National Foundation of Scientific Research Grant no. 1812     

EMBEDDINGS OF ONE KIND OF GRAPHS

The purpose of this paper is to display a new kind of simple graphs which belong to B. inwhich any graph has its orientable genus n,n≥3. Furthermore, for any integer k,1≤k≤n,there exists a graph B^kn of B. such that the non-orientable genus of B^kn is k.     

Minimum genus embeddings of the complete graph

In this paper,the problem of construction of exponentially many minimum genus embeddings of complete graphs in surfaces are studied.There are three approaches to solve this problem.The first approach is to construct exponentially many graphs by the theory of graceful labeling of paths;the second approach is to find a current assignment of the current graph by the theory of current graph;the third approach is to find exponentially many embedding(or rotation) schemes of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph.According to this three approaches,we can construct exponentially many minimum genus embeddings of complete graph K_(12s+8) in orientable surfaces,which show that there are at least 10/3×(200/9)~s distinct minimum genus embeddings for K_(12s+8) in orientable surfaces.We have also proved that K_(12s+8) has at least 10/3×(200/9)~s distinct minimum genus embeddings in non-orientable surfaces.     

A generalization of curve genus for ample vector bundles. I

A new genus g = g (X, ?) is defined for the pairs (X, ?S)that consist of n-dimensional compact complex manifolds X and ample vector bundles ? of rank r less than n on X. In case r = n-1g is equal to curve genus. Above pairs (X,?) with g less than two are classified. For spanned ? it is shown that g is greater than or equal to the irregularity of X, and its equality condition is given.     

Loop-Erased Random Walk on Finite Graphs and the Rayleigh Process

Let (G _n ) _n=1^∞ be a sequence of finite graphs, and let Y _t be the length of a loop-erased random walk on G _n after t steps. We show that for a large family of sequences of finite graphs, which includes the case in which G _n is the d-dimensional torus of size-length n for d≥4, the process (Y _t ) _t=0^∞, suitably normalized, converges to the Rayleigh process introduced by Evans, Pitman, and Winter. Our proof relies heavily on ideas of Peres and Revelle, who used loop-erased random walks to show that the uniform spanning tree on large finite graphs converges to the Brownian continuum random tree of Aldous. Supported in part by NSF Grant DMS-0504882.     

On the average crosscap number II: Bounds for a graph

The bounds are obtained for the average crosscap number. Let G be a graph which is not a tree. It is shown that the average crosscap number of G is not less thanβ(G)-1/2β(G)-1β(G) and not larger thanβ(G). Furthermore, we also describe the structure of the graphs which attain the bounds of the average crosscap number.     

Existence of three HMOLS of type 2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript><Emphasis Type="Italic">u</Emphasis><Superscript>1</Superscript>

A Latin squares of order v with ni missing sub-Latin squares （holes） of order hi （1 〈= i 〈 k）, which are disjoint and spanning （i.e. ∑k i=l1 nihi = v）, is called a partitioned incomplete Latin squares and denoted by PILS. The type of PILS is defined by （h1n1 h2n2…hknk ）. If any two PILS inaset of t PILS of type T are orthogonal, then we denote the set by t-HMOLS（T）. It has been proved that 3-HMOLS（2n31） exist for n ≥6 with 11 possible exceptions. In this paper, we investigate the existence of 3-HMOLS（2nu1） with u ≥ 4, and prove that 3-HMOLS（2~u1） exist if n ≥ 54 and n ≥7/4u ＋ 7.     

Hardy-Sobolev type inequalities on the H-type group

Motivated by the idea of Badiale and Tarantello who have found Hardy-Sobolev inequalities on Rⁿ, a class of Hardy-Sobolev type inequalities on H-type groups is proved via a new representation formula for functions. Extremal functions realizing equality in the inequalities are discussed by refined Concentration-Compactness principles. Finally, some sharp constants for Hardy type inequalities are given. The project supported by National Natural Science Foundation of China, Grant No. 10371099.     

Fundamental cycles and graph embeddings

In this paper, we investigate fundamental cycles in a graph G and their relations with graph embeddings. We show that a graph G may be embedded in an orientable surface with genus at least g if and only if for any spanning tree T , there exists a sequence of fundamental cycles C1, C2, . . . , C2g with C2i-1 ∩ C2i≠ф for 1≤ i ≤g. In particular, among β(G) fundamental cycles of any spanning tree T of a graph G, there are exactly 2γM (G) cycles C1, C2, . . . , C2γM (G) such that C2i-1 ∩ C2i≠ф for 1 ≤i≤γM (G), w...     

Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue). Their data structure, theFibonacci heap (or F-heap) supports arbitrary deletion inO(logn) amortized time and other heap operations inO(1) amortized time. In this paper we use F-heaps to obtain fast algorithms for finding minimum spanning trees in undirected and directed graphs. For an undirected graph containingn vertices andm edges, our minimum spanning tree algorithm runs inO(m logβ (m, n)) time, improved fromO(mβ(m, n)) time, whereβ(m, n)=min {i|log⁽ⁱ⁾ n ≦m/n}. Our minimum spanning tree algorithm for directed graphs runs inO(n logn + m) time, improved fromO(n log n +m log log log_(m/n+2) n). Both algorithms can be extended to allow a degree constraint at one vertex. Research supported in part by National Science Foundation Grant MCS-8302648. Research supported in part by National Science Foundation Grant MCS-8303139. Research supported in part by National Science Foundation Grant MCS-8300984 and a United States Army Research Office Program Fellowship, DAAG29-83-GO020.     

Up-Embeddability of a Graph by Order and Girth

Let G be a connected graph of order n and girth g. If d_G(u) + d_G(v) ≥ n − 2g + 5 for any two non-adjacent vertices u and v, then G is up-embeddable. Further more, the lower bound is best possible. Similarly the result of k-edge connected simple graph with girth g is also obtained, k = 2,3. Partially supported by the Postdoctoral Seience Foundation of Central South University and NNSFC under Grant No. 10751013.