×

A note introducing Cayley graphs generated by graph packings. (English) Zbl 1081.05044

A class of vertex-transitive graphs containing the Kneser graph as a special case is constructed. The class is based on the notion of packing of graphs: Two graphs \(G\) and \(H\) are packable into a complete graph \(K_n\) if and only if \(G\) is isomorphic to a subgraph of \(\overline H\). If \(G=H\), then the packing is called a 2-packing. Cayley graphs of type PP are Calyey graphs with “packing permutations”. The authors investigate relations between subclasses of the constructed graphs. Hamiltonicity properties are in the center of the further investigations. For example, Cayley graphs of type PP generated by graphs \(G=K_{1,m}\cap NK_1\) are Hamiltonian and each edge belongs to some Hamiltonian cycle.

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C45 Eulerian and Hamiltonian graphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite