A note introducing Cayley graphs and group-coset graphs generated by graph packings

• Autorzy: Rosiek R. , Woźniak M.
• Języki publikacji: EN

Abstrakty

EN

The aim of this paper is to construct a class of vertex-transitive graphs that includes the Kneser graphs as a special case. The class will be based on the notion of packing of graphs. Certain families of graphs within this class will be examined more closely, and some of their properties, such as hamiltonicity, will be investigated.

Słowa kluczowe

EN

Cayley graphs; hamiltonicity; packing of graphs

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2004
• Tom: Vol. 24, no. 2
• Strony: 203--221
• Opis fizyczny: Bibliogr. 12 poz., rys.

Twórcy

autor

Rosiek R.

• ADEO ul. Śliczna 36, 31-444 Cracow, Poland

autor

Woźniak M.

• AGH University of Science and Technology Faculty of Applied Mathematics al. Mickiewicza 30, 30-059 Cracow, Poland

Bibliografia

• [1] Bollobas B.: Extremal Graph Theory. London, Academic Press 1978.
• [2] Burns D., Schuster S.: Every (p,p — 2) graph is contained in its complement. J. Graph Theory 1 (1977), 277-279.
• [3] Hillis D.: The connection machine. New York, MIT Press 1985.
• [4] Jackson B.: Hamilton cycles in regular 2-connected graphs. J. Comb. Theory (B) 29 (1980), 27-46.
• [5] Leighton F. T.: Introduction to parallel algorithms and architecture. Morgan Kaufmann, 1992.
• [6] Rumeur de J.: Communications dans les reseaux de processeurs. Paris, Masson 1994.
• [7] Sabidussi G.: Vertex-transitive graphs. Monatsh. Math. 68 (1964), 426-438.
• [8] Woźniak M.: Packing of Graphs. Dissertationes Mathematicae 362 (1997), 1-78.
• [9] Woźniak M.: Wprowadzenie do problemów komunikacji w grafach. Kraków, Wydawnictwa AGH 1999.
• [10] Woźniak M.: Packing of graphs and permutations — a survey. Discrete Math. 276 (2004), 379-391.
• [11] Yap H.P.: Some Topics In Graph Theory. London Mathematical Society, Lectures Notes Series 108, Cambridge, Cambridge University Press 1986.
• [12] Yap H.P.: Packing of graphs — a survey. Discrete Math. 72 (1988), 395-404.