×

Some results on the lexicographic product of vertex-transitive graphs. (English) Zbl 1234.05192

Summary: Many large graphs can be constructed from existing smaller graphs by using graph operations, for example, the Cartesian product and the lexicographic product. Many properties of such large graphs are closely related to those of the corresponding smaller ones. In this short note, we give some properties of the lexicographic products of vertex-transitive and of edge-transitive graphs. In particular, we show that the lexicographic product of Cayley graphs is a Cayley graph.

MSC:

05C76 Graph operations (line graphs, products, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Broere, I.; Hattingh, J. H., Products of circulant graphs, Quaest. Math., 13, 191-216 (1990) · Zbl 0744.05058
[2] Sheldon, B.; Akers, B. K., A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 38, 4, 555-566 (1989) · Zbl 0678.94026
[3] Alspach, B.; Parsons, T. D., A construction for vertex-transitive graphs, Canad. J. Math., 34, 307-318 (1982) · Zbl 0467.05032
[4] Potoc˘nik, P.; S˘ajna, M.; Verret, G., Mobility of vertex-transitive graphs, Discrete Math., 307, 579-591 (2007) · Zbl 1110.05046
[5] Sanders, Robin S., Products of circulant graphs are metacirculant, J. Combin. Theory Ser. B, 197-206 (2002) · Zbl 1035.05050
[6] Sabidussi, G., Vertex-transitive graphs, Monatsh. Math., 68, 426-438 (1964) · Zbl 0136.44608
[7] Larose, B.; Laviolette, F.; Tardif, C., On normal Cayley graphs and hom-idempotent graphs, European J. Combin., 19, 867-881 (1998) · Zbl 0916.05032
[8] Ngo, D. T., On the isomorphism problem for a family of cubic metacirculant graphs, Discrete Math., 151, 231-242 (1996) · Zbl 0858.05077
[9] Nedela, R.; S˘koviera, M., Which generalized Petersen graphs are Cayley?, J. Graph Theory, 19, 1-11 (1995) · Zbl 0812.05026
[10] Xu, J.-M., The Theory of Interconnection Networks (2007), Academic Publishers: Academic Publishers Beijing, China, (In Chinese)
[11] Feder, T., Stable networks and product graphs, Mem. Amer. Math. Soc., 116 (1995) · Zbl 0875.68397
[12] Sanders, Robin S.; George, J. C., Results concerning the automorphism group of the tensor product \(G \otimes K_n\), J. Combin. Math. Combin. Comput., 24, 119-127 (1997) · Zbl 0881.05056
[13] Bondy, J. A.; Murty, U. S.R., Graph Theory with Application (1976), North-Holland: North-Holland Amsterdam · Zbl 1134.05001
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.