Total Embedding Distributions of Circular Ladders. Issue 1 (9th August 2012)

• Record Type: Journal Article
• Authors: Chen, Yichao; Gross, Jonathan L.; Mansour, Toufik
• Is Part Of: Journal of graph theory. Volume 74:Issue 1(2013)
• Page Start: 32
• Page End: 57
• Publication Date: 2012-08-09
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21690
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>The <italic>total embedding polynomial</italic> of a graph <italic>G</italic> is the bivariate polynomial <disp-formula content-type="mathematics" id="jgt21690-disp-0001"><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg25t7frqw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="block" altimg="urn:x-wiley:03649024:media:jgt21690:jgt21690-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi mathvariant="double-struck">I</mml:mi><mml:mi>G</mml:mi></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>x</mml:mi><mml:mo>, </mml:mo><mml:mi>y</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:munderover><mml:mo>∑</mml:mo><mml:mrow><mml:mi>i</mml:mi><mml:mo>=</mml:mo><mml:mn>0</mml:mn></mml:mrow><mml:mi>∞</mml:mi></mml:munderover><mml:msub><mml:mi>a</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:msup><mml:mi>x</mml:mi><mml:mi>i</mml:mi></mml:msup><mml:mspace width="0.16em" /><mml:mo>+</mml:mo><mml:mspace width="0.16em" /><mml:munderover><mml:mo>∑</mml:mo><mml:mrow><mml:mi>j</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>∞</mml:mi></mml:munderover><mml:msub><mml:mi>b</mml:mi><mml:mi>j</mml:mi></mml:msub><mml:msup><mml:mi>y</mml:mi><mml:mi>j</mml:mi></mml:msup><mml:mo>, </mml:mo></mml:mrow></mml:math></disp-formula>where <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg25t7fsgj" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21690:jgt21690-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>a</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:math> is the number of embeddings, for <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg25t7fsf0" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21690:jgt21690-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>i</mml:mi><mml:mo>=</mml:mo><mml:mn>0</mml:mn><mml:mo>, </mml:mo><mml:mn>1</mml:mn><mml:mo>, </mml:mo><mml:mo>...</mml:mo><mml:mo>, </mml:mo></mml:mrow></mml:math> into the orientable surface <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg25t7fspv" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21690:jgt21690-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>S</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:math>, and <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg25t7fsjn" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21690:jgt21690-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>b</mml:mi><mml:mi>j</mml:mi></mml:msub></mml:math> is the number of embeddings, for <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg25t7fs41" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21690:jgt21690-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>j</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn><mml:mo>, </mml:mo><mml:mn>2</mml:mn><mml:mo>, </mml:mo><mml:mo>...</mml:mo><mml:mo>, </mml:mo></mml:mrow></mml:math> into the nonorientable surface <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg25t7fs1c" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21690:jgt21690-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>N</mml:mi><mml:mi>j</mml:mi></mml:msub></mml:math>. The sequence <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg25t7fscw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21690:jgt21690-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mrow><mml:mo>{</mml:mo><mml:msub><mml:mi>a</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mspace width="0.16em" /><mml:mo>|</mml:mo><mml:mspace width="0.16em" /><mml:mi>i</mml:mi><mml:mo>≥</mml:mo><mml:mn>0</mml:mn><mml:mo>}</mml:mo></mml:mrow><mml:mo>⋃</mml:mo><mml:mrow><mml:mo>{</mml:mo><mml:msub><mml:mi>b</mml:mi><mml:mi>j</mml:mi></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mspace width="0.16em" /><mml:mo>|</mml:mo><mml:mspace width="0.16em" /><mml:mi>j</mml:mi><mml:mo>≥</mml:mo><mml:mn>1</mml:mn><mml:mo>}</mml:mo></mml:mrow></mml:mrow></mml:math> is called the <italic>total embedding distribution</italic> of the graph <italic>G</italic>; it is known for relatively few classes of graphs, compared to the <italic>genus distribution</italic><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg25t7fs87" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21690:jgt21690-math-0009" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>{</mml:mo><mml:msub><mml:mi>a</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mspace width="0.16em" /><mml:mo>|</mml:mo><mml:mspace width="0.16em" /><mml:mi>i</mml:mi><mml:mo>≥</mml:mo><mml:mn>0</mml:mn><mml:mo>}</mml:mo></mml:mrow></mml:math>. The <italic>circular ladder</italic> graph <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg25t7fqsg" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21690:jgt21690-math-0010" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>C</mml:mi><mml:msub><mml:mi>L</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow></mml:math> is the Cartesian product <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg25t7fqqc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21690:jgt21690-math-0011" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>K</mml:mi><mml:mn>2</mml:mn></mml:msub><mml:mo>□</mml:mo><mml:msub><mml:mi>C</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow></mml:math> of the complete graph on two vertices and the cycle graph on <italic>n</italic> vertices. In this article, we derive a closed formula for the total embedding distribution of circular ladders.</p> </abstract>