Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Dekompozycja grafów na kopie 2P3
Języki publikacji
Abstrakty
Let P3 be a path with 3 vertices. We denote by 2P3 disjoint union of 2 copies of P3. Graph G admits a 2P3-decomposition if the set of edges of G can be partitioned into subsets generating graphs isomorphic to 2P3. The trivial necessary conditions for the existence of a 2P3-decomposition of a graph G are that number of edges e(G) is divisible by 4 and there exists a P3-decomposition π such that each vertex of G is contained in at most e(G)/4 elements of π. If e(G) is large enough, then there are only some families of graphs for which these two conditions are not sufficient.
Niech P3 będzie drogą o 3 wierzchołkach. Przez 2P3 oznaczmy rozłączną sumę dwóch kopii P3. Graf G posiada 2P3-dekompozycję jeśli zbiór krawędzi grafu G można podzielić na podzbiory indukujące grafy izomorficzne z 2P3. Trywialnymi warunkami koniecznymi dla istnienia 2P3-dekompozycji grafu G są podzielność przez 4 liczby krawędzi oznaczanej przez e(G) oraz istnienie P3-dekompozycji π takiej, że każdy wierzchołek w G jest zawarty w co najwyżej e(G)/4 elementach π. Jeśli e(G) jest wystarczająco duża, to tylko dla pewnych rodzin grafów powyższe dwa warunki nie są wystarczające.
Czasopismo
Rocznik
Tom
Strony
9--32
Opis fizyczny
Bibliogr. 8 poz., rys.
Twórcy
autor
- Politechnika Warszawska, Instytut Matematyki
Bibliografia
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-AGH9-0001-0006