共查询到20条相似文献,搜索用时 654 毫秒
1.
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. 相似文献
2.
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. 相似文献
3.
4.
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. 相似文献
5.
《Advances in Applied Mathematics》2011,47(1-4):226-246
We show combinatorially that the higher-order matching polynomials of several families of graphs are d-orthogonal polynomials. The matching polynomial of a graph is a generating function for coverings of a graph by disjoint edges; the higher-order matching polynomial corresponds to coverings by paths. Several families of classical orthogonal polynomials—the Chebyshev, Hermite, and Laguerre polynomials—can be interpreted as matching polynomials of paths, cycles, complete graphs, and complete bipartite graphs. The notion of d-orthogonality is a generalization of the usual idea of orthogonality for polynomials and we use sign-reversing involutions to show that the higher-order Chebyshev (first and second kinds), Hermite, and Laguerre polynomials are d-orthogonal. We also investigate the moments and find generating functions of those polynomials. 相似文献
6.
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. 相似文献
7.
Gross,Klein和Rieper(1993)计算了项链图的亏格分布,其后,Chen,Liu和Wang(2006)以及Yang,Liu(2007)分别给出了项链图嵌入分布的递推式和显式.本文给出项链图嵌入分布的多项式显式.从计数角度,此式比上述两个表达式更为简洁. 相似文献
8.
Omran Ahmadi 《Finite Fields and Their Applications》2011,17(5):473-480
We generalize Carlitz? result on the number of self-reciprocal monic irreducible polynomials over finite fields by showing that similar explicit formula holds for the number of irreducible polynomials obtained by a fixed quadratic transformation. Our main tools are a combinatorial argument and Hurwitz genus formula. 相似文献
9.
两类四正则图的完全亏格分布 总被引:3,自引:2,他引:1
一个图G的完全亏格多项式表征了图G的亏格(可定向,不可定向)分布情况.本文利用刘彦佩提出的嵌入的联树模型,得出了两类新的四正则图的完全亏格多项式,并推导出已有结果的两类图的完全亏格多项式.此处的结果形式更为简单. 相似文献
10.
基于距离正则图的交叉点排列,给出了三类距离正则图的谱分布,讨论了一维整数格Z的距离矩阵与第一类切比雪夫多项式之间的关系,体现出研究图的谱分布的量子概率技巧. 相似文献
11.
The Total Embedding Distributions of Cacti and Necklaces 总被引:5,自引:0,他引:5
Yi Chao CHEN Yah Pei LIU Tao WANG 《数学学报(英文版)》2006,22(5):1583-1590
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. 相似文献
12.
利用初等方法研究Chebyshev多项式的性质,建立了广义第二类Chebyshev多项式的一个显明公式,并得到了一些包含第一类Chebyshev多项式,第一类Stirling数和Lucas数的恒等式. 相似文献
13.
In this work, the relations between ladder surface sets and cross surface sets are found. The embedding genus distribution of ladders can be obtained by using the genus distribution of cross type surface sets. 相似文献
14.
15.
Satoshi Kuriki Yasuhide Numata 《Annals of the Institute of Statistical Mathematics》2010,62(4):645-672
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. 相似文献
16.
In the first part we expose the notion of continued fractions in the matrix case. In this paper we are interested in their connection with matrix orthogonal polynomials.
In the second part matrix continued fractions are used to develop the notion of matrix Chebyshev polynomials. In the case of hermitian coefficients in the recurrence formula, we give the explicit formula for the Stieltjes transform, the support of the orthogonality measure and its density. As a corollary we get the extension of the matrix version of the Blumenthal theorem proved in [J. Approx. Theory 84 (1) (1996) 96].
The third part contains examples of matrix orthogonal polynomials. 相似文献
17.
In this paper a method is given to calculate the explicit expressions of embedding genus distribution for ladder type graphs
and cross type graphs. As an example, we refind the genus distribution of the graph J
n
which is the first class of graphs studied for genus distribution where its genus depends on n.
This work was supported National Natural Science Foundation of China (Grant Nos. 10571013, 60433050) and the State Key Development
Program of Basic Research of China (Grant No. 2004CB318004) 相似文献
18.
It is known that the chromatic polynomial and flow polynomial of a graph are two important evaluations of its Tutte polynomial, both of which contain much information of the graph. Much research is done on graphs determined entirely by their chromatic polynomials and Tutte polynomials, respectively. Oxley asked which classes of graphs or matroids are determined by their chromatic and flow polynomials together. In this paper, we found several classes of graphs with this property. We first study which graphic parameters are determined by the flow polynomials. Then we study flow-unique graphs. Finally, we show that several classes of graphs, ladders, Möbius ladders and squares of n-cycle are determined by their chromatic polynomials and flow polynomials together. A direct consequence of our theorem is a result of de Mier and Noy [A. de Mier, M. Noy, On graphs determined by their Tutte polynomial, Graphs Comb. 20 (2004) 105-119] that these classes of graphs are Tutte polynomial unique. 相似文献
19.
The Kirchhoff Matrix Tree Theorem provides an efficient algorithm for determiningt(G), the number of spanning trees of any graphG, in terms of a determinant. However for many special classes of graphs, one can avoid the evaluation of a determinant, as there are simple, explicit formulas that give the value oft(G). In this work we show that many of these formulas can be simply derived from known properties of Chebyshev polynomials. This is demonstrated for wheels, fans, ladders, Moebius ladders, and squares of cycles. The method is then used to derive a new spanning tree formula for the complete prismR n (m) =K m ×C n . It is shown that $$2^{\left( {\begin{array}{*{20}c} n \\ 2 \\ \end{array} } \right)\left( {1 - \frac{1}{{r - 1}} + o\left( 1 \right)} \right)} $$ whereT n (x) is then th order Chebyshev polynomial of the first kind. 相似文献
20.
A new explicit formula for the integrals of shifted Chebyshev polynomials of any degree for any fractional-order in terms of shifted Chebyshev polynomials themselves is derived. A fast and accurate algorithm is developed for the solution of linear multi-order fractional differential equations (FDEs) by considering their integrated forms. The shifted Chebyshev spectral tau (SCT) method based on the integrals of shifted Chebyshev polynomials is applied to construct the numerical solution for such problems. The method is then tested on examples. It is shown that the SCT yields better results. 相似文献