On the linear algebra of local complementation. (English) Zbl 1236.05107
Summary: We explore the connections between the linear algebra of symmetric matrices over \(GF(2)\) and the circuit theory of 4-regular graphs. In particular, we show that the equivalence relation on simple graphs generated by local complementation can also be generated by an operation defined using inverse matrices.
MSC:
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 05B20 | Combinatorial aspects of matrices (incidence, Hadamard, etc.) |
References:
| [1] | R. Arratia, B. Bollobás, G.B. Sorkin, The interlace polynomial: a new graph polynomial, in: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 2000), ACM, New York, 2000, pp. 237-245.; R. Arratia, B. Bollobás, G.B. Sorkin, The interlace polynomial: a new graph polynomial, in: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 2000), ACM, New York, 2000, pp. 237-245. · Zbl 0955.05066 |
| [2] | 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 |
| [3] | Arratia, R.; Bollobás, B.; Sorkin, G. B., A two-variable interlace polynomial, Combinatorica, 24, 567-584 (2004) · Zbl 1064.05139 |
| [4] | Balister, P. N.; Bollobás, B.; Cutler, J.; Pebody, L., The interlace polynomial of graphs at −1, European J. Combin., 23, 761-767 (2002) · Zbl 1017.05076 |
| [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] | 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 |
| [8] | Bouchet, A., Unimodularity and circle graphs, Discrete Math., 66, 203-208 (1987) · Zbl 0647.05039 |
| [9] | Bouchet, A., Reducing prime graphs and recognizing circle graphs, Combinatorica, 7, 243-254 (1987) · Zbl 0666.05037 |
| [10] | Bouchet, A., Circle graph obstructions, J. Combin. Theory Ser. B, 60, 107-144 (1994) · Zbl 0793.05116 |
| [11] | Bouchet, A., Multimatroids I. Coverings by independent sets, SIAM J. Discrete Math., 10, 626-646 (1997) · Zbl 0886.05042 |
| [12] | Bouchet, A., Multimatroids. II. Orthogonality, minors and connectivity, Electron. J. Combin., 5, #R8 (1998) · Zbl 0885.05050 |
| [13] | Bouchet, A., Multimatroids III. Tightness and fundamental graphs, European J. Combin., 22, 657-677 (2001) · Zbl 0982.05034 |
| [14] | Bouchet, A., Multimatroids. IV. Chain-group representations, Linear Algebra Appl., 277, 271-289 (1998) · Zbl 0932.05019 |
| [15] | Brahana, H. R., Systems of circuits on two-dimensional manifolds, Ann. Math., 23, 144-168 (1921) · JFM 48.0661.02 |
| [16] | Brijder, R.; Hoogeboom, H. J., Maximal pivots on graphs with an application to gene assembly, Discrete Appl. Math., 158, 1977-1985 (2010) · Zbl 1215.05143 |
| [17] | R. Brijder, H.J. Hoogeboom, The group structure of pivot and loop complementation on graphs and set systems, European J. Combin., in press.; R. Brijder, H.J. Hoogeboom, The group structure of pivot and loop complementation on graphs and set systems, European J. Combin., in press. · Zbl 1230.05197 |
| [18] | Brijder, R.; Hoogeboom, H. J., Nullity invariance for pivot and the interlace polynomial, Linear Algebra Appl., 435, 277-288 (2011) · Zbl 1226.05152 |
| [19] | Cohn, M.; Lempel, A., Cycle decomposition by disjoint transpositions, J. Combin. Theory Ser. A, 13, 83-89 (1972) · Zbl 0314.05005 |
| [20] | Ellis-Monaghan, J. A.; Sarmiento, I., Generalized transition polynomials, Congr. Numer., 155, 57-69 (2002) · Zbl 1021.05067 |
| [21] | Fleischner, H., Eulerian Graphs and Related Topics, Part 1, Annals of Discrete Mathematics, vol. 1 (1990), North-Holland Publishing Co.: North-Holland Publishing Co. Amsterdam, pp. 45 · Zbl 0792.05091 |
| [22] | Fleischner, H., Eulerian Graphs and Related Topics, Part 1, Annals of Discrete Mathematics, vol. 2 (1991), North-Holland Publishing Co.: North-Holland Publishing Co. Amsterdam, pp. 50 · Zbl 0792.05092 |
| [23] | de Fraysseix, H., A characterization of circle graphs, European J. Combin., 5, 223-238 (1984) · Zbl 0551.05056 |
| [24] | F. Genest, Graphes eulériens et complémentarité locale, Ph.D. Thesis, Université de Montréal, 2001.; F. Genest, Graphes eulériens et complémentarité locale, Ph.D. Thesis, Université de Montréal, 2001. |
| [25] | Genest, F., Circle graphs and the cycle double cover conjecture, Discrete Math., 309, 3714-3725 (2009) · Zbl 1229.05168 |
| [26] | Glantz, R.; Pelillo, M., Graph polynomials from principal pivoting, Discrete Math., 306, 3253-3266 (2006) · Zbl 1125.05073 |
| [27] | Godsil, C.; Royle, G., Algebraic Graph Theory (2001), Springer-Verlag: Springer-Verlag Berlin, Heidelberg, and New York · Zbl 0968.05002 |
| [28] | D.P. Ilyutko, Framed 4-valent graphs: Euler tours, Gauss circuits and rotating circuits, Mat. Sb., in press.; D.P. Ilyutko, Framed 4-valent graphs: Euler tours, Gauss circuits and rotating circuits, Mat. Sb., in press. |
| [29] | D.P. Ilyutko, An equivalence between the set of graph-knots and the set of homotopy classes of looped graphs, J. Knot Theory Ramifications, in press.; D.P. Ilyutko, An equivalence between the set of graph-knots and the set of homotopy classes of looped graphs, J. Knot Theory Ramifications, in press. · Zbl 1239.57015 |
| [30] | 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 |
| [31] | 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 |
| [32] | Jonsson, J., On the number of Euler trails in directed graphs, Math. Scand., 90, 191-214 (2002) · Zbl 1017.05067 |
| [33] | Keir, J.; Richter, R. B., Walks through every edge exactly twice II, J. Graph Theory., 21, 301-309 (1996) · Zbl 0876.05022 |
| [34] | 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 |
| [35] | Las Vergnas, M., Le polynôme de Martin d’un graphe Eulérien, Ann. Discrete Math., 17, 397-411 (1983) · Zbl 0537.05040 |
| [36] | 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 |
| [37] | 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 |
| [38] | P. Martin, Enumérations eulériennes dans les multigraphes et invariants de Tutte-Grothendieck, Thèse, Grenoble, 1977.; P. Martin, Enumérations eulériennes dans les multigraphes et invariants de Tutte-Grothendieck, Thèse, Grenoble, 1977. |
| [39] | Mellor, B., A few weight systems arising from intersection graphs, Michigan Math. J., 51, 509-536 (2003) · Zbl 1058.57008 |
| [40] | Moran, G., Chords in a circle and linear algebra over \(GF(2)\), J. Combin. Theory Ser. A, 37, 239-247 (1984) · Zbl 0552.05001 |
| [41] | C.St.J.A. Nash-Williams, Acyclic detachments of graphs, in: Graph Theory and Combinatorics (Proc. Conf., Open Univ., Milton Keynes, 1978), Res. Notes in Math., 34, Pitman, Boston, 1979, pp. 87-97.; C.St.J.A. Nash-Williams, Acyclic detachments of graphs, in: Graph Theory and Combinatorics (Proc. Conf., Open Univ., Milton Keynes, 1978), Res. Notes in Math., 34, Pitman, Boston, 1979, pp. 87-97. · Zbl 0464.05042 |
| [42] | R.C. Read, P. Rosenstiehl, On the Gauss crossing problem, in: Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), vol. II, Colloq. Math. Soc. János Bolyai, 18, North-Holland, Amsterdam, New York, 1978, pp. 843-876.; R.C. Read, P. Rosenstiehl, On the Gauss crossing problem, in: Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), vol. II, Colloq. Math. Soc. János Bolyai, 18, North-Holland, Amsterdam, New York, 1978, pp. 843-876. · Zbl 0391.05017 |
| [43] | Richter, R. B., Walks through every edge exactly twice, J. Graph Theory, 18, 751-755 (1994) · Zbl 0809.05040 |
| [44] | Soboleva, E., Vassiliev knot invariants coming from Lie algebras and 4-invariants, J. Knot Theory Ramifications, 10, 161-169 (2001) · Zbl 0998.57034 |
| [45] | Stahl, S., On the product of certain permutations, European J. Combin., 8, 69-72 (1987) · Zbl 0614.05023 |
| [46] | Traldi, L.; nullity, Binary, Euler circuits and interlacement polynomials, European J. Combin., 32, 944-950 (2011) · Zbl 1227.05168 |
| [47] | L. Traldi, On the interlace polynomials. Preprint: arXiv:1008.0091v4; L. Traldi, On the interlace polynomials. Preprint: arXiv:1008.0091v4 · Zbl 1257.05070 |
| [48] | Tsatsomeros, M. J., Principal pivot transforms: properties and applications, Linear Algebra Appl., 307, 151-165 (2000) · Zbl 0998.15006 |
| [49] | A.W. Tucker, A combinatorial equivalence of matrices, in: Combinatorial Analysis (Proc. Symposia Appl. Math., vol. X), Amer. Math. Soc., Providence, 1960, pp. 129-140.; A.W. Tucker, A combinatorial equivalence of matrices, in: Combinatorial Analysis (Proc. Symposia Appl. Math., vol. X), Amer. Math. Soc., Providence, 1960, pp. 129-140. · Zbl 0096.00701 |
| [50] | 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.
