Graph Bases and Diagram Commutativity
Tóm tắt
Given two cycles A and B in a graph, such that
$$A\cap B$$
is a non-trivial path, the connected sum
$$A\hat{+} B$$
is the cycle whose edges are the symmetric difference of E(A) and E(B). A special kind of cycle basis for a graph, a connected sum basis, is defined. Such a basis has the property that a hierarchical method, building successive cycles through connected sum, eventually reaches all the cycles of the graph. It is proved that every graph has a connected sum basis. A property is said to be cooperative if it holds for the connected sum of two cycles when it holds for the summands. Cooperative properties that hold for the cycles of a connected sum basis will hold for all cycles in the graph. As an application, commutativity of a groupoid diagram follows from commutativity of a connected sum basis for the underlying graph of the diagram. An example is given of a noncommutative diagram with a (non-connected sum) basis of cycles which do commute.
Tài liệu tham khảo
Diestel, R.: Graph Theory, Graduate Texts in Mathematics, vol. 173, 3rd edn. Springer, Berlin (2005)
Dixon, E.T., Goodman, S.E.: An algorithm for the longest cycle problem. Networks 6, 139–146 (1976)
Eppstein, D.: StackExchange, April 20, 2015 (on-line discussion). http://cstheory.stackexchange.com/questions/31203/what-is-the-best-way-to-find-an-induced-cycle-basis-of-a-graph
Galluccio, A., Loebl, M.: \((p, q)\)-odd digraphs. J. Graph Theory 23(2), 175–184 (1996)
Hammack, R.H., Kainen, P.C.: Robust cycle bases do not exist for \(K_{n, n}\) if \(n \ge 8\). Discrete Appl. Math. 235, 206–211 (2018)
Harary, F.: Graph Theory. Addison-Wesley, Reading (1969)
Kainen, P.C.: On robust cycle bases. Electron. Notes Discret. Math. 11, 430–437 (2002) [Proc. 9th Quadr. Conf. on Graph Theory, Comb., Algorithms and Appl., ed. by Y. Alavi et al., 2000)]
Kainen, P.C.: Isolated squares in hypercubes and robustness of commutativity. Cahiers de topologie et géom. diff. catég 43(3), 213–220 (2002)
Kainen, P.C.: Graph cycles and diagram commutativity. Diagrammes 67–68, 177–238 (2012) (Supplem.)
Kainen, P.C.: Cycle construction and geodesic cycles with application to the hypercube. Ars Math. Contemp. 9(1), 27–43 (2015)
Klemm, K., Stadler, P.F.: Statistics of cycles in large networks. Phys. Rev. E 73, 025101(R) (2006)
Klemm, K., Stadler, P.F.: A note on fundamental, non-fundamental, and robust cycle bases. Discrete Appl. Math. 157, 2432–2438 (2009)
Lin, Y.J.: Connected sum construction of constant \(Q\)-curvature maniolds in higher dimensions. Differ. Geom. Appl. 40, 290–320 (2015)
Loebl, M., Matamala, M.: Some remarks on cycles in graphs and digraphs. Discret. Math. 233(1–3), 175–182 (2001)
Mac Lane, S.: Categories for the Working Mathematician, 2nd edn., Graduate Texts in Mathematics (Book 5). Springer, New York (1998)
Milnor, J.: A unique decomposition theorem for 3-manifolds. Am. J. Math. 84, 1–7 (1962)
OEIS Foundation Inc.: The On-Line encyclopedia of integer sequences. http://oeis.org/A085408 (2018)
Ostermeier, P.-J., Hellmuth, M., Klemm, K., Leydold, J., Stadler, P.F.: A note on quasi-robust cycle bases. Ars Math. Contemp. 2, 231–240 (2009)
Spanier, E.H.: Algebraic Topology. McGraw-Hill, New York (1966)
Wall, C.T.C.: Classification problems in differential topology, V. Invent. Math. 1, 355–374 (1966) [corrigendum, ibid 2, 306 (1966)]
White, A.T.: Graphs of Groups on Surfaces. Elsevier, Amsterdam (2001)
Whitney, H.: Non-separable and planar graphs. Trans. AMS 34, 339–362 (1932)