Genus distribution of \(P_3 \mathop\square P_n\). (English) Zbl 1248.05047
Summary: We derive a recursion for the genus distribution of the graph family \(P_{3}\mathop\square P_{n}\), with the aid of a modified collection of double-root partials. We introduce a new kind of production, which corresponds to a surgical operation more complicated than the vertex- or edge-amalgamation operations used in our earlier work.
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C75 | Structural characterization of families of graphs |
| 05C76 | Graph operations (line graphs, products, etc.) |
Keywords:
genus distribution; mesh graphs; embeddings; partials and productions; Cartesian product; treewidthReferences:
| [1] | (Beineke, L. W.; Wilson, R. J.; Gross, J. L.; Tucker, T. W., Topics in Topological Graph Theory (2009), Cambridge University Press) · Zbl 1170.05003 |
| [2] | Bodlaender, H. L., A partial \(k\)-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci., 209, 1-45 (1998) · Zbl 0912.68148 |
| [3] | Chen, J.; Gross, J. L.; Rieper, R. G., Overlap matrices and total imbedding distributions, Discrete Math., 128, 73-94 (1994) · Zbl 0798.05017 |
| [4] | Chen, Y. C.; Liu, Y. P.; Wang, T., The total embedding distributions of cacti and necklaces, Acta Math. Sin. (Engl. Ser.), 22, 1583-1590 (2006) · Zbl 1100.05027 |
| [5] | Chen, Y.; Mansour, T.; Zou, Q., Embedding distributions of generalized fan graphs, Canad. Math. Bull. (2011), Online 31, August |
| [6] | Furst, M. L.; Gross, J. L.; Statman, R., Genus distribution for two classes of graphs, J. Combin. Theory Ser. B, 46, 22-36 (1989) · Zbl 0669.05028 |
| [7] | Gross, J. L., Genus distribution of graphs under surgery: adding edges and splitting vertices, New York J. Math., 16, 161-178 (2010) · Zbl 1198.05029 |
| [8] | Gross, J. L., Genus distributions of cubic outerplanar graphs, J. Graph Algorithms Appl., 15, 295-316 (2011) |
| [9] | Gross, J. L., Genus distributions of graph amalgamations: self-pasting at root vertices, Australas. J. Combin., 49, 19-38 (2011) · Zbl 1228.05128 |
| [10] | J.L. Gross, Embeddings of cubic Halin graphs: a surface-by-surface inventory, Manuscript, p. 20. Available at: http://www.cs.columbia.edu/ gross/research/Halin(Bled)-opt.pdf; J.L. Gross, Embeddings of cubic Halin graphs: a surface-by-surface inventory, Manuscript, p. 20. Available at: http://www.cs.columbia.edu/ gross/research/Halin(Bled)-opt.pdf |
| [11] | J.L. Gross, Embeddings of graphs of fixed treewidth and bounded degree, Manuscript, p. 28.; J.L. Gross, Embeddings of graphs of fixed treewidth and bounded degree, Manuscript, p. 28. · Zbl 1306.05162 |
| [12] | Gross, J. L.; Furst, M. L., Hierarchy for imbedding-distribution invariants of a graph, J. Graph Theory, 11, 205-220 (1987) · Zbl 0643.05026 |
| [13] | Gross, J. L.; Khan, I. F.; Poshni, M. I., Genus distribution of graph amalgamations: pasting at root-vertices, Ars Combin., 94, 33-53 (2010) · Zbl 1240.05059 |
| [14] | Gross, J. L.; Robbins, D. P.; Tucker, T. W., Genus distributions for bouquets of circles, J. Combin. Theory Ser. B, 47, 292-306 (1989) · Zbl 0688.05038 |
| [15] | Gross, J. L.; Tucker, T. W., Topological Graph Theory (2001), Dover, Wiley, (1987) · Zbl 0991.05001 |
| [16] | Khan, I. F.; Poshni, M. I.; Gross, J. L., Genus distribution of graph amalgamations: pasting when one root has arbitrary degree, Ars Math. Contemp., 3, 121-138 (2010) · Zbl 1213.05054 |
| [17] | I.F. Khan, M.I. Poshni, J.L. Gross, Genus distribution of graphs: self-pasting and edge-addition when one root has arbitrary degree (in preparation).; I.F. Khan, M.I. Poshni, J.L. Gross, Genus distribution of graphs: self-pasting and edge-addition when one root has arbitrary degree (in preparation). · Zbl 1213.05054 |
| [18] | Kwak, J. H.; Lee, J., Genus polynomials of dipoles, Kyungpook Math. J., 33, 115-125 (1993) · Zbl 0786.05045 |
| [19] | Kwak, J. H.; Shim, S. H., Total embedding distributions for bouquets of circles, Discrete Math., 248, 93-108 (2002) · Zbl 0993.05057 |
| [20] | Mohar, B.; Thomassen, C., Graphs on Surfaces (2001), Johns Hopkins Press · Zbl 0979.05002 |
| [21] | Mull, B. P., Enumerating the orientable 2-cell imbeddings of complete bipartite graphs, J. Graph Theory, 30, 77-90 (1999) · Zbl 0916.05036 |
| [22] | Poshni, M. I.; Khan, I. F.; Gross, J. L., Genus distribution of graphs under edge-amalgamations, Ars Math. Contemp., 3, 69-86 (2010) · Zbl 1221.05095 |
| [23] | Poshni, M. I.; Khan, I. F.; Gross, J. L., Genus distribution of 4-regular outerplanar graphs, Electron. J. Combin., 18, #P212 (2011) · Zbl 1230.05113 |
| [24] | Poshni, M. I.; Khan, I. F.; Gross, J. L., Genus distribution of graphs under self-edge-amalgamations, Ars Math. Contemp., 5, 127-148 (2012) · Zbl 1242.05075 |
| [25] | Stahl, S., Region distributions of graph embeddings and Stirling numbers, Discrete Math., 82, 57-78 (1990) · Zbl 0706.05027 |
| [26] | Stahl, S., Permutation-partition pairs III: embedding distributions of linear families of graphs, J. Combin. Theory Ser. B, 52, 191-218 (1991) · Zbl 0671.05032 |
| [27] | Stahl, S., Bounds for the average genus of the vertex amalgamation of graphs, Discrete Math., 142, 235-245 (1995) · Zbl 0828.05025 |
| [28] | Tesar, E. H., Genus distribution of Ringel ladders, Discrete Math., 216, 235-252 (2000) · Zbl 0955.05029 |
| [29] | Visentin, T. I.; Wieler, S. W., On the genus distribution of \((p, q, n)\)-dipoles, Electron. J. Combin., 14 (2007), Art. No. R12 · Zbl 1114.05049 |
| [30] | Wan, L. X.; Liu, Y. P., Orientable embedding distributions by genus for certain types of graphs, Ars Combin., 79, 97-105 (2006) · Zbl 1141.05319 |
| [31] | Wan, L. X.; Liu, Y. P., Orientable embedding genus distribution for certain types of graphs, J. Combin. Theory Ser. B, 47, 19-32 (2008) · Zbl 1127.05028 |
| [32] | White, A. T., Graphs of Groups on Surfaces (2001), North-Holland · Zbl 0378.05028 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
