×

zbMATH — the first resource for mathematics

On recognition of strong graph bundles. (English) Zbl 0984.05068
Summary: Graph bundles generalize the notions of covering graphs and graph products. Recently, an algorithm for recognition of graph bundles over triangle free bases with respect to the Cartesian product was found. Here we study the relationship between strong and Cartesian graph bundles. An algorithm for recognition of graphs which have a representation as a graph bundle with connected fibre over a triangle free base with respect to the strong product of graphs is given.

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
05C62 Graph representations (geometric and intersection representations, etc.)
PDF BibTeX XML Cite
Full Text: EuDML
References:
[1] ABELLO J.-FELLOWS M. R.-STILLWELL J. C.: On the complexity and combinatorics of covering finite complexes. Australas. J. Combin. 4 (1991), 103-112. · Zbl 0763.05035
[2] HUSEMOLLER D.: Fibre Bundles. (3rd, Springer, Berlin, 1993. · Zbl 0794.55001
[3] DÖRFLER W.-IMRICH W.: Über das starke Produkt von endlichen Graphen. Österreich. Akad. Wiss. Math.-Natur. Kl. Sitzungsber. II 178 (1969), 247-262. · Zbl 0194.56202
[4] FEDER T.: Product graph representations. J. Graph Theory 16 (1992), 467-488. · Zbl 0766.05092
[5] FEIGENBAUM J.-SCHÄFFER A. A.: Recognizing composite graphs is equivalent to testing graph isomorphism. SIAM J. Comput. 15 (1986), 619-627. · Zbl 0602.68033
[6] FEIGENBAUM J.-HERSHBERGER J.-SCHÄFFER A. A.: A polynomial time algorithm for finding the prime factors of Cartesian-product graphs. Discrete Appl. Math. 12 (1985), 123-138. · Zbl 0579.68028
[7] FEIGENBAUM J.-SCHÄFFER A. A.: Finding the prime factors of strong direct product graphs in polynomial time. Discrete Math. 109 (1992), 77-102. · Zbl 0786.68076
[8] IMRICH W.: Embedding graphs into Cartesian products. Graph Theory and Applications: East and west. Proceedings of the first China-USA international conference, held in Jinan, China, June 9-20, 1986 (M. F. Capobianco et al., Ann. New York Acad. Sci. 576 (1989), 266-274. · Zbl 0792.05044
[9] IMRICH W.-ŽEROVNIK J.: Factoring Cartesian-product graphs. J. Graph Theory 18 (1994), 557-567. · Zbl 0811.05054
[10] IMRICH W.-PISANSKI T.-ŽEROVNIK J.: Recognizing Cartesian graph bundles. Discrete Math. 167/168 (1997), 393-403. · Zbl 0876.05094
[11] IMRICH W.-IZBICKI H.: Associative products of graphs. Monatsh. Math. 80 (1975), 277-281. · Zbl 0328.05136
[12] KLAVŽAR S.-MOHAR B.: Coloring graph bundles. J. Graph Theory 19 (1995), 145-155. · Zbl 0815.05029
[13] KLAVŽAR S.-MOHAR B.: The chromatic numbers of graph bundles over cycles. Discrete Math. 138 (1995), 301-314. · Zbl 0818.05035
[14] KWAK J. H.-LEE J.: Isomorphism classes of graph bundles. Canad. J. Math. 42 (1990), 747-761. · Zbl 0739.05042
[15] KWAK J. H.-LEE J.: Characteristic polynomials of some graph Bundles II. Linear and Multilinear Algebra 32 (1992), 61-73. · Zbl 0755.05078
[16] MCKENZIE R.: Cardinal multiplication of structures with a reflexive relation. Fund. Math. LXX (1971), 59-101. · Zbl 0228.08002
[17] MOHAR B.-PISANSKI T.-ŠKOVIERA M.: The maximum genus of graph bundles. European J. Combin. 9 (1988), 301-314. · Zbl 0642.05019
[18] PISANSKI T.-SHAWE-TAYLOR J.-VRABEC J.: Edge-colorability of graph bundles. J. Combin. Theory Ser. B 35 (1983), 12-19. · Zbl 0505.05034
[19] PISANSKI T.-VRABEC J.: Graph bundles. Unpublished manuscript 1982.
[20] SABIDUSSI G.: Graph multiplication. Math. Z. 72 (1960), 446-457. · Zbl 0093.37603
[21] SOHN M. Y.-LEE J.: Characteristic polynomials of some weighted graph bundles and its application to links. Internat. J. Math. Math. Sci. 17 (1994), 504-510. · Zbl 0808.05073
[22] WINKLER P. M.: Factoring a graph in polynomial time. European J. Combin. 8 (1987), 209-212. · Zbl 0625.05050
[23] ZMAZEK B.-ŽEROVNIK J.: Recognizing weighted directed Cartesian graph bundles. Discuss. Math. · Zbl 0966.05049
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.