Lokalna nieregularność grafów, multigrafów i digrafów

Abstract

W pracy zajmujemy się zagadnieniami związanymi z lokalną nieregularnością grafów. Mówimy, że graf jest lokalnie nieregularny, jeśli każde dwa sąsiednie wierzchołki mają różne stopnie. Praca dotyczy zarówno hipotez dla których znane są już częściowe rezultaty, jak na przykład hipotezy o lokalnej nieregularności grafów, czy też hipotezy (2,2), jak i nowych postawionych niedawno w pracach mojego współautorstwa. W pierwszej części stawiamy hipotezę o rozkładnie multigrafu powstałego z grafu G przez podwojenie wszystkich krawędzi G na dwa multigrafy lokalnie nieregularne i dowodzimy ją dla wybranych klas grafów. Ponadto zajmujemy się ograniczeniami górnymi na liczbę lokalnie nieregularnych multigrafów występujących w rozkładzie dowolnego takiego multigrafu i wybranych klas multigrafów. W następnej części dowodzimy wzmocnioną wersję hipotezy (2,2), dla wybranych klas grafów. W kolejnej części pracy formujemy nowy problem dotyczący lokalnej nieregularności grafów związany z hipotezą (2,2) i hipotezą o lokalnej nieregularności grafów, jak również prezentujemy jego częściowe rozwiązanie. W ostatniej części rozważamy dwa nowe sposoby definiowania lokalnie nieregularnego digrafu, formujemy dwie hipotezy dotyczące rozkładów digrafów na digrafy lokalnie nieregularne i dowodzimy szereg rezultatów dla poparcia tych hipotez.

In this dissertation we investigate concepts related to the local irregularity of graphs. We say that a graph is locally irregular if every two adjacent vertices have different degrees. The dissertation deals not only with conjectures for which partial results are known, such as the Local Irregularity Conjecture and the (2,2)-Conjecture, but also with new conjectures which was recently stated in papers of my co-authorship. In the first part, we establish a conjecture about the decomposition of a multigraph obtained from a graph G by doubling all edges of G into two locally irregular multigraphs and prove it for selected graph classes. Furthermore, we deal with upper bounds on the number of locally irregular multigraphs occurring in the decomposition of any such multigraph and selected classes of multigraphs. In the next part, we prove the strengthened version of the (2,2)-Conjecture, for selected classes of graphs. In the subsequent part of the dissertation, we present a new problem about the local irregularity of graphs related to the (2,2)-Conjecture and the Local Irregularity Conjecture, as well as present its partial solution. In the last part, we consider two new methods of defining a locally irregular digraph, formulate two conjectures about the decomposition of digraphs into locally irregular digraphs and prove some results which support these conjectures.