Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: decomposition of graphs

Sortuj według:

Ogranicz wyniki do:

Decomposition of graphs into copies of 2P3

Bryś K.

Opuscula Mathematica

1998

Vol. 18,

9-32

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.