Niektóre właściwości grafów dobrze pokrytych

• Autorzy: Guze S.

Warianty tytułu

EN

Selected properties of the well-covered graphs

• Języki publikacji: PL

Abstrakty

PL

W artykule zostały podane podstawowe definicje z teorii grafów. Zdefiniowano zbiór niezależny, liczbę niezależnego dominowania oraz liczbę niezależności. Wprowadzono także pojęcie grafu dobrze pokrytego oraz opisano jego podstawowe właściwości. W dalszej części przedstawiono właściwości grafów dobrze pokrytych o obwodzie co najmniej 5 i grafów dobrze pokrytych, które nie zawierają cykli długości 4 i 5 jako podgrafów. Omawiane pojęcia i właściwości zilustrowane zostały przykładami.

EN

The elementary definitions of graph theory were given. An independent vertex set, an independent domination number and a number of independenies number were defined. The definition of a well-covered graph and its basic properties were introduced. Further, properties of well-covered graphs with girth at least 5 and not included cycles of lengths neither 4 nor 5 as their subgraphs were described. Considered notions and properties were illustrated by examples.

Słowa kluczowe

PL

matematyka; teoria grafów

EN

mathematics; graph theory

• Wydawca: Wydawnictwo Uniwersytetu Morskiego w Gdyni
• Czasopismo: Prace Wydziału Nawigacyjnego Akademii Morskiej w Gdyni
• Rocznik: 2006
• Tom: Z. 19
• Strony: 36--50
• Opis fizyczny: Bibliogr. 15 poz., rys.

Twórcy

autor

Guze S.

• Katedra Matematyki, Akademia Morska w Gdyni

Bibliografia

• 1. Berge C., Some common properties for regularizable graphs, edge critical and B-graphs, in ''Theory and Practice of Combinatorics'' (A. Rosa and G. Sabidussi, Eds.), special edition of Ann. Discrete Math. 60, 31-44 (1982).
• 2. Campbell S.R., Ellingham M.N., Royle G.F., A characterization of well-covered cubic graphs, Journal of Combinatorial Mathematics and Combinatorial Computing 13, 193-212 (1993).
• 3. Dean N., Zito J., Well-covered graphs and extendability, Discrete Mathematics 126, 67-80 (1994).
• 4. Finbow A., Hartnell B., A game related to covering by stars, Ars Combin. A 16, 189-198 (1983).
• 5. Finbow A., Hartnell B., Nowakowski R.J., A characterization of well-covered graphs of girth 5 or greater, Journal of Combinatorial Theory, B 57, 44-68 (1993).
• 6. Finbow A., Hartnell B., Nowakowski R.J., A characterization of well-covered graphs that contain neither 4- nor 5 – cycles, Journal of Graph Theory, 18, 713-721 (1994).
• 7. Guze S., Grafy dobrze pokryte, praca magisterska, Wydział Matematyki, Fizyki i Informatyki, Uniwersytet Gdański, Gdańsk (2004).
• 8. Levit V., Mandrescu E., Well covered and König-Egervary graphs, Congressus Numerantium 130, 209-218 (1998).
• 9. Lewin M., Matching-perfect and cover-perfect graphs, Israel Journal of Mathmetics 18, 345-347 (1974).
• 10. Plummer M.D., Some covering concepts in graph, J. Combin. Theory 8, 91-98 (1980).
• 11. Plummer M.D., Well-covered graphs: a survey, Quaestiones Mathematicae 16, 253-287 (1993).
• 12. Randerath B., Vestergaard P.D., Well-covered graphs and factors, Discrete Math. (2002).
• 13. Ravidra G., Well-covered graphs, J. Combin. Inform. System Sci. 2, 20-21 (1977).
• 14. Staples J.A., On some subclasses of well-covered graph, Ph. D. disseration, Vanderbilt University, 1975.
• 15. Staples J.A., On some subclasses of well-covered graphs, Journal of Graph Theory 3, 197-204 (1979).