Nonstandard eulerian and hamiltonian graphs, and a coloring theorem for nonstandard graphs

• Autorzy: Zemanian A. H.

Warianty tytułu

PL

Eulerowskie i hamiltonowskie grafy niestandardowe oraz twierdzenie o kolorowaniu dla grafów niestandardowych

• Języki publikacji: EN

Abstrakty

EN

From any given sequence of finite or infinite graphs, a nonstandard graph can be constructed. The procedure is similar to an ultrapower construction of an internal set from a sequence of subsets of the real line, but now the individual entities are the nodes of the graphs instead of real numbers. The transfer principle can then be invoked to extend several graph-theoretic results to the nonstandard case. In this work, nonstandard versions of Eulerian graphs, Hamiltonian graphs, and a coloring theorem are established for nonstandard graphs.

PL

Z dowolnej sekwencji grafów skończonych lub nieskończonych można zbudować graf niestandardowy. Procedura w tym przypadku jest podobna do konstrukcji tzw. ultramocy zbioru wewnętrznego z sekwencji podzbiorów zbioru liczb rzeczywistych, gdzie teraz poszczególne wielkości są węzłami grafów, a nie liczbami rzeczywistymi. Wtedy zasada transferu może być zastosowana w celu rozszerzenia zakresu stosowalności wielu teoretycznych wyników dotyczących grafów standardowych na grafy niestandardowe. W tej pracy są rozpatrywane niestandardowe przypadki grafów Eulerowskich i Hamiltonowskich oraz twierdzenie o kolorowaniu dla przypadku grafów niestandardowych.

Słowa kluczowe

EN

nonstandard graphs; transfer principle; ultrapower constructions; Eulerian graphs; Hamiltonian graphs; graph-coloring theorem

PL

grafy niestandardowe; zasada transferu; konstrukcje ultramocy; graf eulerowski; graf hamiltonowski; twierdzenie o kolorowaniu grafów

• Wydawca: Wydawnictwa Uczelniane Akademii Techniczno-Rolniczej w Bydgoszczy
• Czasopismo: Zeszyty Naukowe. Telekomunikacja i Elektronika / Akademia Techniczno-Rolnicza w Bydgoszczy
• Rocznik: 2006
• Tom: z. 9
• Strony: 37--44
• Opis fizyczny: bibliogr. 7 poz.

Twórcy

autor

Zemanian A. H.

• Electrical Engineering Department State University of New York at Stony Brook Stony Brook, New York 11794-2350, USA

Bibliografia

• [1] Behzad M., Chartrand G., 1971. Introduction to the Theory of Graphs. Allyn and Bacon Inc. Boston.
• [2] Buckley F., Harary F., 1990. Distances in Graphs. Addison-Wesley Publishing Co. New York.
• [3] Goldblatt R., 1998. Lectures on the Hyperreals. Springer New York.
• [4] Mendelson E., 1992 Introduction to Mathematical Logic, Fourth Edition. Chapman Hall/CRC, Boca Raton Florida.
• [5] Wilson R.J., 1972 Introduction to Graph Theory. Academic Press New York.
• [6] Zemanian A.H., 2004. Graphs and Networks: Transfinite and Nonstandard. Birkhauser Boston.
• [7] Zemanian A.H., 2005. The Galaxies of Nonstandard Enlargements of Infinite and Transfinite Graphs: II. CEAS Technical Report 819, University at Stony Brook April.