The transition matroid of a 4-regular graph: an introduction. (English) Zbl 1319.05034
Summary: Given a 4-regular graph \(F\), we introduce a binary matroid \(M_\tau(F)\) on the set of transitions of \(F\). Parametrized versions of the Tutte polynomial of \(M_\tau(F)\) yield several well-known graph and knot polynomials, including the Martin polynomial, the homflypt polynomial, the Kauffman polynomial and the Bollobás-Riordan polynomial.
References:
| [1] | Aigner, M.; van der Holst, H., Interlacement polynomials, Linear Algebra Appl., 377, 11-30 (2004) · Zbl 1030.05071 |
| [2] | Arratia, R.; Bollobás, B.; Sorkin, G. B., The interlace polynomial: A new graph polynomial, (Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 2000) (2000), ACM: ACM New York), 237-245 · Zbl 0955.05066 |
| [3] | Arratia, R.; Bollobás, B.; Sorkin, G. B., A two-variable interlace polynomial, Combinatorica, 24, 567-584 (2004) · Zbl 1064.05139 |
| [4] | Arratia, R.; Bollobás, B.; Sorkin, G. B., The interlace polynomial of a graph, J. Combin. Theory Ser. B, 92, 199-233 (2004) · Zbl 1060.05062 |
| [5] | Beck, I., Cycle decomposition by transpositions, J. Combin. Theory Ser. A, 23, 198-207 (1977) · Zbl 0406.05003 |
| [6] | Beck, I.; Moran, G., Introducing disjointness to a sequence of transpositions, Ars Combin., 22, 145-153 (1986) · Zbl 0607.20002 |
| [7] | Bollobás, B.; Riordan, O., A Tutte polynomial for coloured graphs, Combin. Probab. Comput., 8, 45-93 (1999) · Zbl 0926.05017 |
| [8] | Bollobás, B.; Riordan, O., A polynomial invariant of graphs on orientable surfaces, Proc. Lond. Math. Soc., 83, 513-531 (2001) · Zbl 1015.05024 |
| [9] | Bollobás, B.; Riordan, O., A polynomial of graphs on surfaces, Math. Ann., 323, 81-96 (2002) · Zbl 1004.05021 |
| [10] | Bouchet, A., Caractérisation des symboles croisés de genre nul, C. R. Acad. Sci. Paris Sér. A-B, 274, A724-A727 (1972) · Zbl 0228.05104 |
| [11] | Bouchet, A., Greedy algorithm and symmetric matroids, Math. Program., 38, 147-159 (1987) · Zbl 0633.90089 |
| [12] | Bouchet, A., Isotropic systems, European J. Combin., 8, 231-244 (1987) · Zbl 0642.05015 |
| [13] | Bouchet, A., Reducing prime graphs and recognizing circle graphs, Combinatorica, 7, 243-254 (1987) · Zbl 0666.05037 |
| [14] | Bouchet, A., Unimodularity and circle graphs, Discrete Math., 66, 203-208 (1987) · Zbl 0647.05039 |
| [15] | Bouchet, A., Graphic presentation of isotropic systems, J. Combin. Theory Ser. B, 45, 58-76 (1988) · Zbl 0662.05014 |
| [16] | Bouchet, A., Representability of \(\Delta \)-matroids, (Combinatorics (Eger, 1987). Combinatorics (Eger, 1987), Colloq. Math. Soc. János Bolyai, vol. 52 (1988), North-Holland: North-Holland Amsterdam, New York), 167-182 · Zbl 0708.05013 |
| [17] | Bouchet, A., Maps and \(\Delta \)-matroids, Discrete Math., 78, 59-71 (1989) · Zbl 0719.05019 |
| [18] | Bouchet, A., Multimatroids. I. Coverings by independent sets, SIAM J. Discrete Math., 10, 626-646 (1997) · Zbl 0886.05042 |
| [19] | Brahana, H. R., Systems of circuits on two-dimensional manifolds, Ann. of Math., 23, 144-168 (1921) · JFM 48.0661.02 |
| [20] | Brijder, R.; Hoogeboom, H. J.; Traldi, L., The adjacency matroid of a graph, Electron. J. Combin., 20, #P27 (2013) · Zbl 1298.05210 |
| [21] | Champanerkar, A.; Kofman, I.; Stoltzfus, N., Graphs on surfaces and Khovanov homology, Algebr. Geom. Topol., 7, 1531-1540 (2007) · Zbl 1169.57004 |
| [22] | Chmutov, S., Generalized duality for graphs on surfaces and the signed Bollobás-Riordan polynomial, J. Combin. Theory Ser. B, 99, 617-638 (2009) · Zbl 1172.05015 |
| [23] | Chmutov, S.; Lando, S., Mutant knots and intersection graphs, Algebr. Geom. Topol., 7, 1579-1598 (2007) · Zbl 1158.57013 |
| [24] | Cohn, M.; Lempel, A., Cycle decomposition by disjoint transpositions, J. Combin. Theory Ser. A, 13, 83-89 (1972) · Zbl 0314.05005 |
| [25] | Courcelle, B., A multivariate interlace polynomial and its computation for graphs of bounded clique-width, Electron. J. Combin., 15, #R69 (2008) · Zbl 1181.05010 |
| [26] | de Fraysseix, H.; Ossona de Mendez, P., On a characterization of Gauss codes, Discrete Comput. Geom., 22, 287-295 (1999) · Zbl 0932.05024 |
| [27] | Edmonds, J., On the surface duality of linear graphs, J. Res. Natl. Bur. Stand., 69B, 121-123 (1965) · Zbl 0132.20604 |
| [28] | Ellis-Monaghan, J. A.; Moffatt, I., Twisted duality for embedded graphs, Trans. Amer. Math. Soc., 364, 1529-1569 (2012) · Zbl 1238.05067 |
| [29] | Ellis-Monaghan, J. A.; Moffatt, I., Graphs on Surfaces. Dualities, Polynomials, and Knots (2013), Springer: Springer New York · Zbl 1283.57001 |
| [31] | Ellis-Monaghan, J. A.; Sarmiento, I., Generalized transition polynomials, Congr. Numer., 155, 57-69 (2002) · Zbl 1021.05067 |
| [32] | Ellis-Monaghan, J. A.; Traldi, L., Parametrized Tutte polynomials of graphs and matroids, Combin. Probab. Comput., 15, 835-854 (2006) · Zbl 1108.05024 |
| [33] | Freyd, P.; Yetter, D.; Hoste, J.; Lickorish, W. B.R.; Millett, K. C.; Ocneanu, A., A new polynomial invariant of knots and links, Bull. Amer. Math. Soc., 12, 239-246 (1985) · Zbl 0572.57002 |
| [34] | Ghier, L., Double occurrence words with the same alternance graph, Ars Combin., 36, 57-64 (1993) · Zbl 0793.05124 |
| [35] | Godsil, C.; Royle, G., Algebraic Graph Theory (2001), Springer-Verlag: Springer-Verlag New York · Zbl 0968.05002 |
| [36] | Gordon, G.; McNulty, J., Matroids: A Geometric Introduction (2012), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 1253.05002 |
| [37] | Gross, J. L.; Tucker, T. W., Topological Graph Theory (2001), Dover: Dover Mineola · Zbl 0991.05001 |
| [38] | Jaeger, F., Graphes de cordes et espaces graphiques, European J. Combin., 4, 319-327 (1983) · Zbl 0542.05055 |
| [39] | Jaeger, F., On some algebraic properties of graphs, (Progress in Graph Theory (Waterloo, Ont., 1982) (1984), Academic Press: Academic Press Toronto), 347-366 · Zbl 0557.05034 |
| [40] | Jaeger, F., On Tutte polynomials and cycles of plane graphs, J. Combin. Theory Ser. B, 44, 127-146 (1988) · Zbl 0595.05033 |
| [41] | Jaeger, F., A combinatorial model for the homfly polynomial, European J. Combin., 11, 549-558 (1990), European J. Combin. 12 (1991) 89-90 (Erratum) · Zbl 0733.05039 |
| [42] | Jaeger, F., On transition polynomials of 4-regular graphs, (Cycles and Rays (Montreal, PQ, 1987). Cycles and Rays (Montreal, PQ, 1987), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 301 (1990), Kluwer Acad. Publ.: Kluwer Acad. Publ. Dordrecht), 123-150 · Zbl 0734.05053 |
| [43] | Jin, X.; Zhang, F., The Homfly and dichromatic polynomials, Proc. Amer. Math. Soc., 140, 1459-1472 (2012) · Zbl 1241.57004 |
| [44] | Jonsson, J., On the number of Euler trails in directed graphs, Math. Scand., 90, 191-214 (2002) · Zbl 1017.05067 |
| [45] | Kauffman, L. H., State models and the Jones polynomial, Topology, 26, 395-407 (1987) · Zbl 0622.57004 |
| [46] | Kauffman, L. H., An invariant of regular isotopy, Trans. Amer. Math. Soc., 318, 417-471 (1990) · Zbl 0763.57004 |
| [47] | Kauffman, L. H., Virtual knot theory, European J. Combin., 20, 663-691 (1999) · Zbl 0938.57006 |
| [48] | Kauffman, L. H., Knots and Physics (2013), World Scientific: World Scientific Singapore · Zbl 0749.57002 |
| [49] | Keir, J.; Richter, R. B., Walks through every edge exactly twice II, J. Graph Theory, 21, 301-309 (1996) · Zbl 0876.05022 |
| [50] | Kotzig, A., Eulerian lines in finite 4-valent graphs and their transformations, (Theory of Graphs (Proc. Colloq., Tihany, 1966) (1968), Academic Press: Academic Press New York), 219-230 · Zbl 0159.54201 |
| [51] | Las Vergnas, M., On Eulerian partitions of graphs, (Graph Theory and Combinatorics (Proc. Conf., Open Univ., Milton Keynes, 1978). Graph Theory and Combinatorics (Proc. Conf., Open Univ., Milton Keynes, 1978), Res. Notes in Math., vol. 34 (1979), Pitman: Pitman Boston, Mass.-London), 62-75 · Zbl 0438.05040 |
| [52] | Las Vergnas, M., Eulerian circuits of 4-valent graphs imbedded in surfaces, (Algebraic Methods in Graph Theory, Vol. I, II (Szeged, 1978). Algebraic Methods in Graph Theory, Vol. I, II (Szeged, 1978), Colloq. Math. Soc. János Bolyai, vol. 25 (1981), North-Holland: North-Holland Amsterdam, New York), 451-477 · Zbl 0472.05043 |
| [53] | Las Vergnas, M., Le polynôme de Martin d’un graphe Eulérien, Ann. Discrete Math., 17, 397-411 (1983) · Zbl 0537.05040 |
| [54] | Lauri, J., On a formula for the number of Euler trails for a class of digraphs, Discrete Math., 163, 307-312 (1997) · Zbl 0870.05049 |
| [55] | Listing, J. B., Vorstudien zur Topologie (1848), Vandenhoeck und Ruprecht: Vandenhoeck und Ruprecht Göttingen |
| [56] | Macris, N.; Pulé, J. V., An alternative formula for the number of Euler trails for a class of digraphs, Discrete Math., 154, 301-305 (1996) · Zbl 0862.05079 |
| [58] | Mellor, B., A few weight systems arising from intersection graphs, Michigan Math. J., 51, 509-536 (2003) · Zbl 1058.57008 |
| [59] | Mohar, B.; Thomassen, C., Graphs on Surfaces (2001), The Johns Hopkins U. Press: The Johns Hopkins U. Press Baltimore · Zbl 0979.05002 |
| [60] | Moran, G., Chords in a circle and linear algebra over GF(2), J. Combin. Theory Ser. A, 37, 239-247 (1984) · Zbl 0552.05001 |
| [61] | Oxley, J. G., Matroid Theory (2011), Oxford Univ. Press: Oxford Univ. Press Oxford · Zbl 1254.05002 |
| [62] | Penrose, R., Applications of negative dimensional tensors, (Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) (1971), Academic Press: Academic Press London), 221-244 · Zbl 0216.43502 |
| [63] | Przytycki, J. H.; Traczyk, P., Invariants of links of Conway type, Kobe J. Math., 4, 115-139 (1987) · Zbl 0655.57002 |
| [64] | Read, R. C.; Rosenstiehl, P., On the Gauss crossing problem, (Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Colloq. Math. Soc. János Bolyai, vol. 18 (1978), North-Holland: North-Holland Amsterdam, New York), 843-876 · Zbl 0391.05017 |
| [65] | Richter, R. B., Walks through every edge exactly twice, J. Graph Theory, 18, 751-755 (1994) · Zbl 0809.05040 |
| [66] | Soboleva, E., Vassiliev knot invariants coming from Lie algebras and 4-invariants, J. Knot Theory Ramifications, 10, 161-169 (2001) · Zbl 0998.57034 |
| [67] | Stahl, S., On the product of certain permutations, European J. Combin., 8, 69-72 (1987) · Zbl 0614.05023 |
| [68] | Thistlethwaite, M. B., A spanning tree expansion of the Jones polynomial, Topology, 26, 297-309 (1987) · Zbl 0622.57003 |
| [69] | Traldi, L., A dichromatic polynomial for weighted graphs and link polynomials, Proc. Amer. Math. Soc., 106, 279-286 (1989) · Zbl 0713.57003 |
| [70] | Traldi, L., Parallel connections and coloured Tutte polynomials, Discrete Math., 290, 291-299 (2005) · Zbl 1069.05021 |
| [71] | Traldi, L., Binary nullity, Euler circuits and interlacement polynomials, European J. Combin., 32, 944-950 (2011) · Zbl 1227.05168 |
| [72] | Traldi, L., On the linear algebra of local complementation, Linear Algebra Appl., 436, 1072-1089 (2012) · Zbl 1236.05107 |
| [73] | Traldi, L., On the interlace polynomials, J. Combin. Theory Ser. B, 103, 184-208 (2013) · Zbl 1257.05070 |
| [74] | Traldi, L., Interlacement in 4-regular graphs: a new approach using nonsymmetric matrices, Contrib. Discrete Math., 9, 85-97 (2014) · Zbl 1317.05092 |
| [75] | Traldi, L., Binary matroids and local complementation, European J. Combin., 45, 21-40 (2015) · Zbl 1304.05015 |
| [76] | Tutte, W. T., Graph Theory (1984), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0554.05001 |
| [77] | Welsh, D. J.A., Matroid Theory (2010), Dover: Dover Mineola · Zbl 0343.05002 |
| [78] | (White, N., Theory of Matroids (1986), Cambridge Univ. Press: Cambridge Univ. Press Cambridge) · Zbl 0579.00001 |
| [79] | (White, N., Combinatorial Geometries (1987), Cambridge Univ. Press: Cambridge Univ. Press Cambridge) · Zbl 0626.00007 |
| [80] | (White, N., Matroid Applications (1992), Cambridge Univ. Press: Cambridge Univ. Press Cambridge) · Zbl 0742.00052 |
| [81] | Whitney, H., On the abstract properties of linear dependence, Amer. J. Math., 57, 509-533 (1935) · JFM 61.0073.03 |
| [82] | Zaslavsky, T., Strong Tutte functions of matroids and graphs, Trans. Amer. Math. Soc., 334, 317-347 (1992) · Zbl 0781.05012 |
| [83] | Zulli, L., A matrix for computing the Jones polynomial of a knot, Topology, 34, 717-729 (1995) · Zbl 0844.57010 |
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.
