Randomly kCn graphs

• Autorzy: Híc P. , Pokorný M.
• Języki publikacji: EN

Abstrakty

EN

A graph G is said to be a randomly H graph if and only if any subgraph of G without isolated vertices, which is isomorphic to a subgraph of H, can be extended to a subgraph H₁ of G such that H₁ is isomorphic to H. The problem of characterization of randomly H graphs, where H is r-regular graph on p vertices, was given by Tomasta and Tomová. In general, the characterization of such graphs seems to be difficult. However, there exist several results for the case r = 2. Chartrand, Oellermann, and Ruiz characterized randomly C_n graphs. Híc and Pokorný characterized randomly 2Cn graphs, as well as randomly C_n U C_m graphs, where n ≠ m. In this paper, the problem of randomly H graphs, where H = kC_n , k > 2 is discussed.

• Wydawca: Wydawnictwo Uniwersytetu Humanistyczno-Przyrodniczego im. Jana Długosza w Częstochowie
• Czasopismo: Scientific Issues of Jan Długosz University in Częstochowa. Mathematics
• Rocznik: 2007
• Tom: Vol. 12
• Strony: 41--48
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Híc P.

• Department of Mathematics and Computer Science Trnava University, Faculty of Education Priemyselná 4, P.O.BOX 9, 91843 Trnava, Slovak Republic

autor

Pokorný M.

• Department of Mathematics and Computer Science Trnava University, Faculty of Education Priemyselná 4, P.O.BOX 9, 91843 Trnava, Slovak Republic

Bibliografia

• [1] Y. Alavi, D.R. Lick,_S. Tian. Randomly complete n-partite graphs. Math. Slovaca, 39, 241-250, 1989.
• [2] G. Chartrand, O.R. Oellermann, S. Ruiz. Randomly H-graphs. Math. Slovaca, 36, 129-136, 1986.
• [3] G. A. Dirac, C. Thomasen. Graphs in which every finite path is contained in a circuit. Math. Ann., 203, 65-75, 1973.
• [4] F. Harary. Graph Theory. Addison-Wesley Publishing Company, Reading. MA, 1969.
• [5] P. Híc. A characterization of K r,s-closed graphs. Math. Slovaca, 39, 353-359, 1989.
• [6] P. Híc. A note on randomly complete n-partite graphs. Math. Slovaca 42, 407-410, 1992.
• [7] P. Híc, M. Pokorný, Randomly 2Cn graphs. Tatra Mountains Mathematical Publications, 35, in print.
• [8] P. Hic, M. Pokorný. Randomly CnUCm graphs. Annales Academiae Paedagogicae Cracoviensis Studia Mathematica, Instytut Matematyki, Academia Pedagogiczna w Krakowie, Krakow, 2007, in print.
• [9] P. Tomasta, E. Tomová. On H-closed graphs. Czech. Math. J., 38, 113, 404-419, 1988.