The Number of Circles of a Maximum State of a Plane Graph with Applications

Acta Mathematicae Applicatae Sinica, English Series - 2021
Xian-an Jin1, Jun Ge2,1, Xiao-Sheng Cheng3, Yu-qing Lin4
1School of Mathematical Sciences, Xiamen University, Xiamen, China
2School of Mathematical Sciences & Laurent Mathematics Center, Sichuan Normal University, Chengdu, China
3School of Mathematics and Statistics, Huizhou University, Huizhou, Guangdong, China
4School of Electrical Engineering and Computer Science, The University of Newcastle, Callaghan, Australia

Tóm tắt

Motivated by the connection with the genus of the corresponding link and its application on DNA polyhedral links, in this paper, we introduce a parameter smax(G), which is the maximum number of circles of states of the link diagram D(G) corresponding to a plane (positive) graph G. We show that smax(G) does not depend on the embedding of G and if G is a 4-edge-connected plane graph then smax(G) is equal to the number of faces of G, which cover the results of S. Y. Liu and H. P. Zhang as special cases.

Từ khóa


Tài liệu tham khảo

Aigner, M. A Course in Enumeration. Springer Verlag, Berlin, 2007

Bollobás, B., Riordan, O. A polynomial of graphs on orientable surfaces. Proc. London Math. Soc., 83: 513–531 (2001)

Bollobás, B., Riordan, O. A polynomial of graphs on surfaces. Math. Ann., 323(1): 81–96 (2002)

Bondy, J.A., Murty, U.S.R. Graph Theory with Applications. American Elsevier Publishing Co., Inc., New York, 1976.

Cheng, X.-S., Jin, X. The braid index of complicated DNA polyhedral links. PLoS One, 7(11): e48968 (2012)

Cheng, X.-S., Liu, S.Y., Zhang, H.P., Qiu, W.-Y. Fabrication of a family of pyramidal links and their genus. MATCH Commun. Math. Comput. Chem., 63: 623–636 (2010)

Crowell, R.H. Genus of alternating link types. Ann. Math., 69: 258–275 (1959)

Endo, T. The link component number of suspended trees. Graphs and Combinatorics, 26: 483–490 (2010)

Gabai, D. Genera of the alternating links. Duke Math. J., 53: 677–681 (1986)

Godsil, C., Royle, G. Algebraic Graph Theory. Springer Verlag, New York, 2001

He, Y., Su, M., Fang, P., Zhang, C., Ribbe, A.E., Jiang, W., Mao, C. On the chirality of self-assembled DNA octahedra. Angew. Chem. Int. Ed., 49: 748–751 (2010)

He, Y., Ye, T., Su, M., Zhang, C., Ribbe, A. E., Jiang, W., Mao C. Hierarchical self-assembly of DNA into symmetric supramolecular polyhedra. Nature, 452: 198–202 (2008)

Hendrickson B. Conditions for unique graph realizations. SIAM J. Comput., 21(1): 65–84 (1992)

Jacobs, D. J., Hendrickson, B. An algorithm for two-dimensional rigidity percolation: the pebble game. J. Comp. Phys., 137: 346–365 (1997)

Jaeger, F. Tutte polynomials and link polynomials. Proc. Amer. Math. Soc., 103: 647–654 (1988)

Jiang, L., Jin, X., Deng, K. Determining the component number of links corresponding to triangular and honeycomb lattices. J. Knot Theory Ramifications, 21(2): 1250018 (2012)

Jin, X., Dong, F.M., Tay, E.G. Determining the component number of links corresponding to lattices. J. Knot Theory Ramifications, 18(12): 1711–1726 (2009)

Jin, X., Dong, F.M., Tay, E.G. On graphs determining links with maximal number of components via medial construction. Discrete Appl. Math., 157: 3099–3110 (2009)

Kim, D., Lee, J. Some invariants of pretzel links. Bull. Austral. Math. Soc., 75: 253–271 (2007)

Lin, C., Liu, Y., Yan, H. Designer DNA Nanoarchitectures. Biochemistry, 48(8): 1663–1674 (2009)

Lin, Y., Noble, S.D., Jin, X., Cheng, W. On plane graphs with link component number equal to the nullity. Discrete Appl. Math., 160: 1369–1375 (2012)

Liu, S.Y., Zhang, H.P. Genera of the links derived from 2-connected plane graphs. J. Knot Theory Ramifications, 21(14): 1250129 (2012)

Mphako, E.G. The component number of links from graphs. Proc. Edinb. Math. Soc., 45: 723–730 (2002)

Murasugi, K. On the genus of the alternating knot, I, II. J. Math. Soc. Jpn., 10: 94–105, 235–248 (1958)

Murasugi, K. On a certain numerical invariant of link types. Trans. Amer. Math. Soc., 117: 387–422 (1965)

Murasugi, K. Knot Theory and Its Applications. Birkhauser, Boston, Inc., Boston, MA, 1996

Murasugi, K., Stoimenow, A. The Alexander polynomial of planar even valence graphs. Adv. in Appl. Math., 31: 440–462 (2003)

Nakamura, T., Nakanishi, Y., Satoh, S., Tomiyama, Y. The state numbers of a virtual knot. J. Knot Theory Ramifications, 23(3): 1450016 (2014)

Pisanski, T., Tucker, T.W., Žitnik, A. Straight-ahead walks in Eulerian graphs. Discrete Math., 281: 237–246 (2004)

Sarmiento, I. Transition polynomials. Discrete Math., 302: 254–266 (2005)

Seifert, H. Über das Geschlecht von Knoten. Math. Ann., 110: 571–592 (1935)

Shank, H. The theory of left-right paths. In: A. Penfold Street, ed. by W.D. Wallis, Combinatorial Math. III, Lecture Notes in Math. 452, Springer, Berlin, 1975, 42–54

Yamada, S. The minimal number of Seifert circles equals the braid index of a link. Invent. Math., 89: 347–356 (1987)

Zhang, C., Ko, S. H., Su, M., Leng, Y., Ribbe, A. E., Jiang, W., Mao, C. Symmetry Controls the Face Geometry of DNA Polyhedra. J. Am. Chem. Soc., 131: 1413–1315 (2009)

Zhang, C., Su, M., He, Y., Zhao, X., Fang, P., Ribbe, A. E., Jiang, W., Mao, C. Conformational flexibility facilitates self-assembly of complex DNA nanostructures. Proc. Natl. Acad. Sci. U.S.A., 105: 10665–10669 (2008)

Thông tin
Thông tin xuất bản

Acta Mathematicae Applicatae Sinica, English Series

Thông tin tác giả