Total embedding distributions of Ringel ladders

被引：12
作者：
Chen, Yichao [1 ]
Ou, Lu [1 ]
Zou, Qian [1 ]
机构：
[1] Hunan Univ, Coll Math & Econometr, Changsha 410082, Hunan, Peoples R China
来源：
DISCRETE MATHEMATICS | 2011年 / 311卷 / 21期
基金：
美国国家科学基金会;
关键词：
Graph embedding; Ringel ladders; Overlap matrix; Chebyshev polynomials; REGION DISTRIBUTIONS; GENUS DISTRIBUTIONS; GRAPH; BOUQUETS;
D O I：
10.1016/j.disc.2011.07.020
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
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. (C) 2011 Elsevier B.V. All rights reserved.
引用
收藏
页码：2463 / 2474
页数：12
相关论文
共 16 条
  • [1] Total Embedding Distributions of Circular Ladders
    Chen, Yichao
    Gross, Jonathan L.
    Mansour, Toufik
    JOURNAL OF GRAPH THEORY, 2013, 74 (01) : 32 - 57
  • [2] Genus distribution of Ringel ladders
    Tesar, EH
    DISCRETE MATHEMATICS, 2000, 216 (1-3) : 235 - 252
  • [3] Embedding Distributions and Chebyshev Polynomials
    Chen, Yichao
    Mansour, Toufik
    Zou, Qian
    GRAPHS AND COMBINATORICS, 2012, 28 (05) : 597 - 614
  • [4] Genus distributions of star-ladders
    Chen, Yichao
    Gross, Jonathan L.
    Mansour, Toufik
    DISCRETE MATHEMATICS, 2012, 312 (20) : 3059 - 3067
  • [5] The total embedding distributions of cacti and necklaces
    Chen, Yi Chao
    Liu, Yan Pei
    Wang, Tao
    ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2006, 22 (05) : 1583 - 1590
  • [6] The Total Embedding Distributions of Cacti and Necklaces
    Yi Chao CHEN College of Mathematics and Econometrics
    ActaMathematicaSinica(EnglishSeries), 2006, 22 (05) : 1583 - 1590
  • [7] Total embedding distributions for bouquets of circles
    Kwak, JH
    Shim, SH
    DISCRETE MATHEMATICS, 2002, 248 (1-3) : 93 - 108
  • [8] The Total Embedding Distributions of Cacti and Necklaces
    Yi Chao Chen
    Yan Pei Liu
    Tao Wang
    Acta Mathematica Sinica, 2006, 22 : 1583 - 1590
  • [9] Embedding Exchanged Hypercubes into Rings and Ladders
    Fan, Weibei
    Fan, Jianxi
    Lin, Cheng-Kuan
    Han, Zhijie
    Li, Peng
    Wang, Ruchuan
    ALGORITHMS AND ARCHITECTURES FOR PARALLEL PROCESSING, ICA3PP 2018, PT II, 2018, 11335 : 3 - 17
  • [10] Embedding Distributions and Chebyshev Polynomials
    Yichao Chen
    Toufik Mansour
    Qian Zou
    Graphs and Combinatorics, 2012, 28 : 597 - 614
12