Kronecker Products and Local Joins of Graphs

Farzan, M. ; Waller, D. A.

Canadian journal of mathematics, Tome 29 (1977) no. 2, pp. 255-269

Résumé

When studying the category raph of finite graphs and their morphisms, Ave can exploit the fact that this category has products, [we define these ideas in detail in § 2]. This categorical product of graphs is usually called their Kronecker product, though it has been approached by various authors in various ways and under various names, including tensor product, cardinal product, conjunction and of course categorical product (see for example [6; 7; 11 ; 14; 17 and 23]).

Détail

DOI : 10.4153/CJM-1977-027-1

Bibliographie

[1] 1. Biggs, N. L., Algebraic graph theory (Cambridge University Press, 1974). Google Scholar

[2] 2. Cvetkovic, D. M., The spectral method for determining the number of trees, Publ. Inst. Math. Beograd. 11 (25) (1971), 135–141. Google Scholar

[3] 3. Cvetkovic, D. M. Graphs and their spectra, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz. 354-356 (1971), 1–50. Google Scholar

[4] 4. Dôrfler, W., Uber die X-summe von gerichteten Graphen, Arch. Math. 22 (1971), 24–36. Google Scholar

[5] 5. Dôrfler, W. Automorphism von X-summen von graphen, Czech. Math. J. 22 (97) (1971), 381–389. Google Scholar

[6] 6. Dôrfler, W. Zum Kroneckerprodukt von endlichen Graphen, Glasnik Mat. Ser. Ill 6 (16) (1971), 217–229. Google Scholar

[7] 7. Farzan, M., Matrix methods in graph theory, Thesis, University of Wales, Swansea 1974. Google Scholar

[8] 8. Finck, H.-J. and Grohmann, G., Vollstandiger Produkt, chromatische Zahl und characteriches Polynom regularer Graphen I, Wiss. Z. Techn. Hochsch. Ilmenau 11 (1965), 1–3. Google Scholar

[9] 9. Friedman, B., Eigenvalues of composite matrices, Proc. Camb. Phil. Soc. 57 (1961), 37–49. Google Scholar

[10] 10. Harary, F., Graph theory (Addison Wesley, 1969). Google Scholar

[11] 11. Hedetniemi, S. T., Homomorphisms of graphs and automata, Univ. of Michigan Technical Report, 03105–44-T, (1966). Google Scholar

[12] 12. Hemminger, R. L., The group of an X-join of graphs, J. Comb. Theory 5 (1968), 408–418. Google Scholar

[13] 13. Herrlich, H. and Strecker, G. E., Category theory (Allyn and Bacon, 1973). Google Scholar

[14] 14. Miller, D. J., The categorical product of graphs, Can. J. Math. 20 (1968), 1511–1521. Google Scholar

[15] 15. Sabidussi, G., Graph derivatives, Math. Zeitschr. 76 (1961), 385–401. Google Scholar

[16] 16. Sabidussi, G. The lexicographic product of graphs, Duke Math. J. 28 (1961), 573–578. Google Scholar

[17] 17. Sampathkumar, E., On tensor product graphs, J. Australian Math. Soc. 20 (Series A) (1975), 268–273. Google Scholar

[18] 18. Schwenk, A. J., Computing the characteristic polynomial of a graph, Springer Lecture Notes 406, 153–172. Google Scholar

[19] 19. Sumner, D. P., Graphs indecomposable with respect to the X-join, Discrete Math. 6 (1973), 281–298. Google Scholar

[20] 20. Waller, D. A., Eigenvalues of graphs and operations, in Combinatorics (eds. V. Mavron and T. McDonough), London Math. Soc. Lecture Notes 13, Cambridge U.P., 177–183. Google Scholar

[21] 21. Waller, D. A. Regular eigenvalues of graphs and enumeration of spanning trees, Proc. Colloquio Internazionale sulle Teorie Combinatorie, Rome 1973, I, 313–320. Google Scholar

[22] 22. Waller, D. A. Double covers of graphs, Bull. Australian Math. Soc. 14 (1976), 233–248. Google Scholar

[23] 23. Weichsel, P. M., The Kronecker product of graphs, Proc. Amer. Math. Soc. 13 (1962), 47–52. Google Scholar