扇图在曲面上嵌入的分类

图在曲面上嵌入的分类就是确定图在同一曲面上(不等价的)嵌入的数目.本文,利用刘彦佩提出的嵌入的联树模型,得到了双极图与扇图的关联曲面之间的关系,进而由已知结论的双极图的亏格分布和完全亏格分布推导出扇图的亏格分布和完全亏格分布,并给出了扇图在亏格为1-4的不可定向曲面上嵌入的个数的显式.     

类圈图的亏格分布

一个图 G 的亏格分布是指序列{g_k}, g_k表示 G 嵌入亏格为 k 的闭的可定向曲面的数目. 该文给出了标准类圈图的亏格分布的递推公式, 并得到类圈图的嵌入多项式的计算公式.     

K_(1,4)梯图的可定向嵌入亏格分布

本文主要运用刘彦佩提出的联树嵌入法研究一类新图-K_(1,4)梯图W_n的可定向嵌入亏格分布,并通过进一步递推化简,得到了K_(1,4)梯图在小亏格上的嵌入亏格多项式显式,以及在其他亏格上的简单递推式,使其在可定向亏格上的嵌入个数更容易地得出.     

多重圈梯图在射影平面上的嵌入个数

图在不同亏格曲面上的嵌入个数常常有相关关系,因此,分析一些图类在小亏格曲面上的嵌入个数对最终确定图的亏格分布和完全亏格分布有着重要意义,本文利用嵌入的联树模型得出了多重圈梯图在射影平面上的嵌入个数.     

叉梯有向图在可定向曲面上的亏格多项式

虽然一些关于图的亏格分布的结果已经知道,但关于有向图的结果却很少.本文第二作者发现了计算图的嵌入多项式的联树法,这篇文章将此方法推广到计算有向图的嵌入多项式.得到了一类新的四正则叉梯有向图在可定向曲面上的亏格多项式.这些结果为解决Bonnington提出的第三个问题奠定了基础.     

两类四正则图的完全亏格分布

一个图G的完全亏格多项式表征了图G的亏格(可定向,不可定向)分布情况.本文利用刘彦佩提出的嵌入的联树模型,得出了两类新的四正则图的完全亏格多项式,并推导出已有结果的两类图的完全亏格多项式.此处的结果形式更为简单.     

圈梯形图序列的嵌入

本文主要研究确定圈梯形图序列和莫比乌斯梯形图序列(由梯形图类生成的图)的亏格分布.首先利用运算矩阵讨论梯形图类的亏格分布,然后利用加边规则,在梯形图类上加边,得到圈梯形图序列或莫比乌斯梯形图序列,进而得到圈梯形图序列(莫比乌斯梯形图序列)的亏格分布.另外,还验证了经典梯图亏格分布的渐近正态性.     

项链图在曲面上的嵌入

Gross,Klein和Rieper(1993)计算了项链图的亏格分布,其后,Chen,Liu和Wang(2006)以及Yang,Liu(2007)分别给出了项链图嵌入分布的递推式和显式.本文给出项链图嵌入分布的多项式显式.从计数角度,此式比上述两个表达式更为简洁.     

D_3□P_n的亏格分布北大核心CSCD

D_32□P_n为双极图D_3与路P_n的笛卡尔积图.本文引入了一种新的加边运算,结合图的部分亏格分布,得到了笛卡尔积图D_3□P_n的亏格分布的递推表达式.     

曲面上图的拉普拉斯谱半径

本文研究了图嵌入到给定紧致曲面上的拉普拉斯谱半径,确定了将顶点数为n、最大度为△的图分别嵌入到亏格为g的定向曲面和亏格为h的不可定向曲面上的新上界.     

Embedding Distributions and Chebyshev Polynomials

The history of genus distributions began with J. Gross et?al. in 1980s. Since then, a lot of study has given to this parameter, and the explicit formulas are obtained for various kinds of graphs. In this paper, we find a new usage of Chebyshev polynomials in the study of genus distribution, using the overlap matrix, we obtain homogeneous recurrence relation for rank distribution polynomial, which can be solved in terms of Chebyshev polynomials of the second kind. The method here can find explicit formula for embedding distribution of some other graphs. As an application, the well known genus distributions of closed-end ladders and cobblestone paths (Furst et?al. in J Combin Ser B 46:22–36, 1989) are derived. The explicit formula for non-orientable embedding distributions of closed-end ladders and cobblestone paths are also obtained.     

The genus polynomials of cross-ladder digraphs in orientable surfaces

Some results about the genus distributions of graphs are known,but little is known about those of digraphs.In this paper,the method of joint trees initiated by Liu is generalized to compute the embedding genus distributions of digraphs in orientable surfaces.The genus polynomials for a new kind of 4-regular digraphs called the cross-ladders in orientable surfaces are obtained.These results are close to solving the third problem given by Bonnington et al.     

The Total Embedding Distributions of Cacti and Necklaces

Total embedding distributions have been known for only a few classes of graphs. In this paper the total embedding distributions of the cacti and the necklaces are obtained. Furthermore we obtain the total embedding distributions of all graphs with maximum genus 1 by using the method of this paper.     

Total embedding distributions of Ringel ladders

The total embedding distributions of a graph consists of the orientable embeddings and non-orientable embeddings and are known for only a few classes of graphs. The orientable genus distribution of Ringel ladders is determined in [E.H. Tesar, Genus distribution of Ringel ladders, Discrete Mathematics 216 (2000) 235–252] by E.H. Tesar. In this paper, using the overlap matrix, we obtain nonhomogeneous recurrence relation for rank distribution polynomial, which can be solved by the Chebyshev polynomials of the second kind. The explicit formula for the number of non-orientable embeddings of Ringel ladders is obtained. Also, the orientable genus distribution of Ringel ladders is re-derived.     

Genus polynomials and crosscap‐number polynomials for ring‐like graphs

An H‐linear graph is obtained by transforming a collection of copies of a fixed graph H into a chain. An H‐ring‐like graph is formed by binding the two end‐copies of H in such a chain to each other. Genus polynomials have been calculated for bindings of several kinds. In this paper, we substantially generalize the rules for constructing sequences of H‐ring‐like graphs from sequences of H‐linear graphs, and we give a general method for obtaining a recursion for the genus polynomials of the graphs in a sequence of ring‐like graphs. We use Chebyshev polynomials to obtain explicit formulas for the genus polynomials of several such sequences. We also give methods for obtaining recursions for partial genus polynomials and for crosscap‐number polynomials of a bar‐ring of a sequence of disjoint graphs.     

Genus distributions of star-ladders

Star-ladder graphs were introduced by Gross in his development of a quadratic-time algorithm for the genus distribution of a cubic outerplanar graph. This paper derives a formula for the genus distribution of star-ladder graphs, using overlap matrix and Chebyshev polynomials.     

Counterexamples to a conjecture by Gross,Mansour and Tucker on partial-dual genus polynomials of ribbon graphs

Gross, Mansour and Tucker introduced the partial-dual orientable genus polynomial and the partial-dual Euler genus polynomial. They computed these two partial-dual genus polynomials of four families of ribbon graphs, posed some research problems and made some conjectures. In this paper, we introduce the notion of signed interlace sequences of bouquets and obtain the partial-dual Euler genus polynomials for all ribbon graphs with the number of edges less than 4 and the partial-dual orientable genus polynomials for all orientable ribbon graphs with the number of edges less than 5 in terms of signed interlace sequences. We check all the conjectures and find a counterexample to the Conjecture 3.1 in their paper: There is no orientable ribbon graph having a non-constant partial-dual genus polynomial with only one non-zero coefficient. Motivated by this counterexample, we further find an infinite family of counterexamples to the conjecture.     

Graph presentations for moments of noncentral Wishart distributions and their applications

We provide formulas for the moments of the real and complex noncentral Wishart distributions of general degrees. The obtained formulas for the real and complex cases are described in terms of the undirected and directed graphs, respectively. By considering degenerate cases, we give explicit formulas for the moments of bivariate chi-square distributions and 2 × 2 Wishart distributions by enumerating the graphs. Noting that the Laguerre polynomials can be considered to be moments of a noncentral chi-square distributions formally, we demonstrate a combinatorial interpretation of the coefficients of the Laguerre polynomials.