Decomposition of graphs into copies of 2P3

• Autorzy: Bryś K.

Warianty tytułu

PL

Dekompozycja grafów na kopie 2P3

• Języki publikacji: EN

Abstrakty

EN

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.

PL

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.

Słowa kluczowe

EN

decomposition of graphs; isomorfic graphs

PL

dekompozycja grafów; grafy izomorficzne

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 1998
• Tom: Vol. 18,
• Strony: 9--32
• Opis fizyczny: Bibliogr. 8 poz., rys.

Twórcy

autor

Bryś K.

• Politechnika Warszawska, Instytut Matematyki