Nekatere s pakiranji povezane lastnosti grafov - Božović, Dragana (visokošolska dela, 2020)
In this dissertation, different problems related to packings are presented. The dissertation consists of four parts. In the first part, we focus on graphs with the unique packing of maximum cardinality. We first present several general properties for such graphs. Later two characterizations of trees with the unique maximum packing are presented. The second part introduces the concept of incidence dimension, which is directly related to the packing of a graph. We determine the formula for its calculation and prove that the problem of finding the incidence dimension of a graph is NP-complete in the general case. The third part is devoted to the packing chromatic number of the lexicographic product of graphs. Its lower and upper bounds are determined. The improved upper bound for the case where the first factor in the product is isomorphic to a path on $n$ vertices is also presented. The last section deals with the efficient open domination of digraph products. We characterize the efficient open domination direct and lexicographic products of digraphs. Among Cartesian products, those whose first factor is a directed path, a directed cycle, or a single-source star are characterized. Characterization of the efficient open domination strong product digraphs for which the underlying graph of both factors is unicyclic is also presented.
Keywords: dimenzija incidenčnosti; Disertacije; enolično največje pakiranje; generator incidenčnosti; Grafi; Lastnosti; leksikografski produkt grafov; pakirna množica; pakirno kromatično število; produkti usmerjenih grafov; učinkovita odprta dominacija; usmerjeni grafi