Geodesic
Edge-Transitive Lexicographic and Cartesian Products
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 857-865.

Voir la notice de l'article provenant de la source Library of Science

In this note connected, edge-transitive lexicographic and Cartesian products are characterized. For the lexicographic product G ◦ H of a connected graph G that is not complete by a graph H, we show that it is edge-transitive if and only if G is edge-transitive and H is edgeless. If the first factor of G ∘ H is non-trivial and complete, then G ∘ H is edge-transitive if and only if H is the lexicographic product of a complete graph by an edgeless graph. This fixes an error of Li, Wang, Xu, and Zhao [11]. For the Cartesian product it is shown that every connected Cartesian product of at least two non-trivial factors is edge-transitive if and only if it is the Cartesian power of a connected, edge- and vertex-transitive graph.
Keywords: edge-transitive graph, vertex-transitive graph, lexicographic product of graphs, Cartesian product of graphs 
@article{DMGT_2016_36_4_a6,
     author = {Imrich, Wilfried and Iranmanesh, Ali and Klav\v{z}ar, Sandi and Soltani, Abolghasem},
     title = {Edge-Transitive {Lexicographic} and {Cartesian} {Products}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {857--865},
     publisher = {mathdoc},
     volume = {36},
     number = {4},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a6/}
}
TY  - JOUR
AU  - Imrich, Wilfried
AU  - Iranmanesh, Ali
AU  - Klavžar, Sandi
AU  - Soltani, Abolghasem
TI  - Edge-Transitive Lexicographic and Cartesian Products
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 857
EP  - 865
VL  - 36
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a6/
LA  - en
ID  - DMGT_2016_36_4_a6
ER  - 
%0 Journal Article
%A Imrich, Wilfried
%A Iranmanesh, Ali
%A Klavžar, Sandi
%A Soltani, Abolghasem
%T Edge-Transitive Lexicographic and Cartesian Products
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 857-865
%V 36
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a6/
%G en
%F DMGT_2016_36_4_a6
Imrich, Wilfried; Iranmanesh, Ali; Klavžar, Sandi; Soltani, Abolghasem. Edge-Transitive Lexicographic and Cartesian Products. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 857-865. http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a6/

[1] H. Abdo and D. Dimitrov, The irregularity of graphs under graph operations, Discuss. Math. Graph Theory 34 (2014) 263-278. doi: 10.7151/dmgt.1733

[2] J. Chen, C.H. Li and Á. Seress, A family of half-transitive graphs, Electron. J. Combin. 20 (1) (2013) #P56.

[3] E. Dobson, A. Hujdurovič, M. Milanič and G. Verret, Vertex-transitive CIS graphs, European J. Combin. 44 (2015) 87-98. doi: 10.1016/j.ejc.2014.09.007

[4] C. Godsil and G. Royle, Algebraic Graph Theory (Springer-Verlag, New York, 2001). doi: 10.1007/978-1-4613-0163-9

[5] T. Gologranc, G. Mekiš and I. Peterin, Rainbow connection and graph products, Graphs Combin. 30 (2014) 591-607. doi: 10.1007/s00373-013-1295-y

[6] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs (Second Edition, CRC Press, Boca Raton, FL, 2011).

[7] W. Imrich, Automorphismen und das kartesische Produkt von Graphen, Österreich. Akad. Wiss. Math.-Natur. Kl. S.-B. II 177 (1969) 203-214.

[8] W. Imrich, Embedding graphs into Cartesian products, Ann. N.Y. Acad. Sci. 576 (1989) 266-274. doi: 10.1111/j.1749-6632.1989.tb16407.x

[9] B. Keszegh, B. Patkós and X. Zhu, Nonrepetitive colorings of lexicographic product of paths and other graphs, Discrete Math. Theor. Comput. Sci. 16 (2014) 97-110.

[10] K. Kutnar and D. Marušič, Recent trends and future directions in vertex-transitive graphs, Ars Math. Contemp. 1 (2008) 112-125.

[11] F. Li, W. Wang, Z. Xu and H. Zhao, Some results on the lexicographic product of vertex-transitive graph, Appl. Math. Lett. 24 (2011) 1924-1926. doi: 10.1016/j.aml.2011.05.021

[12] C.H. Li, Z.P. Lu and J. Pan, Finite vertex-primitive edge-transitive metacirculants, J. Algebraic Combin. 40 (2014) 785-804. doi: 10.1007/s10801-014-0507-8

[13] J. Meng, Connectivity of vertex and edge transitive graphs, Discrete Appl. Math. 127 (2003) 601-613. doi: 10.1016/S0166-218X(02)00391-8

[14] D.J. Miller, The automorphism group of a product of graphs, Proc. Amer. Math. Soc. 25 (1970) 24-28. doi: 10.1090/S0002-9939-1970-0262116-3

[15] G. Sabidussi, The composition of graphs, Duke Math. J. 26 (1959) 693-696. doi: 10.1215/S0012-7094-59-02667-5

[16] G. Sabidussi, Graph multiplication, Math. Z. 72 (1959/1960) 446-457.

[17] V.G. Vizing, The Cartesian product of graphs, Vyčisl. Sistemy 9 (1963) 30-43, in Russian.

[18] M.E. Watkins, Connectivity of transitive graphs, J. Combin. Theory 8 (1970) 23-29. doi: 10.1016/S0021-9800(70)80005-9

[19] M.E. Watkins, Edge-transitive strips, Discrete Math. 95 (1991) 359-372. doi: 10.1016/0012-365X(91)90347-5

[20] J.-X. Zhou and Y.-Q. Feng, Edge-transitive dihedral or cyclic covers of cubic symmetric graphs of order 2P, Combinatorica 34 (2014) 115-128. doi: 10.1007/s00493-014-2834-8

[21] Mathematics Stack Exchange, accessed on December 28, 2015. http://math.stackexchange.com/questions/287369