Edge-transitive products. (English) Zbl 1339.05340
Summary: This paper concerns finite, edge-transitive direct and strong products, as well as infinite weak Cartesian products. We prove that the direct product of two connected, non-bipartite graphs is edge-transitive if and only if both factors are edge-transitive and at least one is arc-transitive, or one factor is edge-transitive and the other is a complete graph with loops at each vertex. Also, a strong product is edge-transitive if and only if all factors are complete graphs. In addition, a connected, infinite non-trivial Cartesian product graph \(G\) is edge-transitive if and only if it is vertex-transitive and if \(G\) is a finite weak Cartesian power of a connected, edge- and vertex-transitive graph \(H\), or if \(G\) is the weak Cartesian power of a connected, bipartite, edge-transitive graph \(H\) that is not vertex-transitive.
MSC:
| 05C76 | Graph operations (line graphs, products, etc.) |
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
References:
| [1] | Chen, J., Li, C.H., Seress, Á.: A family of half-transitive graphs. Electron. J. Comb. 20(1), 10 (2013) · Zbl 1266.05053 |
| [2] | Dörfler, W.: Primfaktorzerlegung und Automorphismen des Kardinalproduktes von Graphen. Glasnik Mat. 9, 15-27 (1974) · Zbl 0284.05124 |
| [3] | Feigenbaum, J., Schäffer, A.A.: Finding prime factors of strong direct product graphs in polynomial time. Discrete Math. 109, 77-102 (1992) · Zbl 0786.68076 · doi:10.1016/0012-365X(92)90280-S |
| [4] | Giudici, M., Potočnik, P., Verret, G.: Semiregular automorphisms of edge-transitive graphs. J. Algebr. Comb. 40, 961-972 (2014) · Zbl 1304.05059 · doi:10.1007/s10801-014-0515-8 |
| [5] | Godsil, C., Royle, G.: Algebraic Graph Theory. Springer, New York (2001) · Zbl 0968.05002 · doi:10.1007/978-1-4613-0163-9 |
| [6] | Hammack, R., Imrich, W., Klavžar, S.: Handbook of Product Graphs, 2nd edn. CRC Press, Boca Raton (2011) · Zbl 1283.05001 |
| [7] | Hammack, R., Imrich, W.: On Cartesian skeletons of graphs. Ars Math. Contemp. 2, 191-205 (2009) · Zbl 1190.05099 |
| [8] | Imrich, W.: Automorphismen und das kartesische Produkt von Graphen, Österreich. Akad. Wiss. Math. Natur. Kl. S. B. II 177, 203-214 (1969) · Zbl 0183.28502 |
| [9] | Imrich, W.: Embedding graphs into Cartesian products. Ann. N. Y. Acad. Sci. 576, 266-274 (1989) · Zbl 0792.05044 · doi:10.1111/j.1749-6632.1989.tb16407.x |
| [10] | Imrich, W., Iranmanesh, A., Klavžar, S., Soltani, A.: Edge-transitive lexicographic and Cartesian products, Discuss. Math. Graph Theory (2016) · Zbl 1350.05145 |
| [11] | Li, C.H., Heng, Z.H.: Finite vertex-biprimitive edge-transitive tetravalent graphs. Discrete Math. 317, 33-43 (2014) · Zbl 1279.05032 · doi:10.1016/j.disc.2013.11.006 |
| [12] | Li, F., Wang, W., Xu, Z., Zhao, H.: Some results on the lexicographic product of vertex-transitive graphs. Appl. Math. Lett. 24, 1924-1926 (2011) · Zbl 1234.05192 · doi:10.1016/j.aml.2011.05.021 |
| [13] | Liu, G.X., Lu, Z.P.: On edge-transitive cubic graphs of square-free order. Eur. J. Comb. 45, 41-46 (2015) · Zbl 1304.05026 · doi:10.1016/j.ejc.2014.10.005 |
| [14] | Miller, D.J.: Weak Cartesian product of graphs. Colloq. Math. 21, 55-74 (1970) · Zbl 0195.54301 |
| [15] | Miller, D.J.: The automorphism group of a product of graphs. Proc. Am. Math. Soc. 25, 24-28 (1970) · Zbl 0194.25302 · doi:10.1090/S0002-9939-1970-0262116-3 |
| [16] | Sabidussi, G.: The composition of graphs. Duke Math. J. 26, 693-696 (1959) · Zbl 0095.37802 · doi:10.1215/S0012-7094-59-02667-5 |
| [17] | Sabidussi, G.: Vertex-transitive graphs. Mon. Hefte. Math. 68, 426-438 (1964) · Zbl 0136.44608 · doi:10.1007/BF01304186 |
| [18] | Watkins, M.E.: Edge-transitive strips. Discrete Math. 95, 359-372 (1991) · Zbl 0756.05093 · doi:10.1016/0012-365X(91)90347-5 |
| [19] | Weichsel, P.M.: The Kronecker product of graphs. Proc. Am. Math. Soc. 13, 47-52 (1962) · Zbl 0102.38801 · doi:10.1090/S0002-9939-1962-0133816-6 |
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.
