Crossing numbers are from Leighton's seminal work »Complexity issues in VLSI« a fundamental concept for studying complexity of electronic circuits. However, the minor crossing number turns out to be a better approach to minimizing the number of crossings in a circuit, as it considers vertices with the same electric potential as equivalent. We generalize the three lower bound techniques: the Crossing Lemma, the bisection method and the embedding method into the context of the minor crossing number. We also point out relations of the minor crossing number to string graphs.
COBISS.SI-ID: 15636057
We describe in this work the NZ-flows of the strong product of graphs. For the strong product of graphs we obtain either 2, or 3, or 4 NZ-flow. We have 2 NZ-flow whenever both factors of the product are Eulerian, # NZ-flow if we have a K4 tree and 3 NZ-flow otherwise. We use construction method that imply the polinomial algorithm.
COBISS.SI-ID: 15616089
This paper shows several constructions and theorems with a goal towards classifying the minor-minimal graphs with minimum degree at least k. The main results of the paper are twofold, on one hand, describing a series of operations for constructing minor minimal graphs with minimum degree k starting from the respective equivalents with minimum degree k-1, on the other hand, proving a richness in structure these graphs can posess. The final part of the paper where connections between min degree, connectivity, treewidth and pathwidth are discussed for complete multipartite graphs.
COBISS.SI-ID: 15813209
Complex networks with a huge amount of data, present one of the most recent phenomena of informational society. In this monograph complex networks are presented from various points of view, where particular chapters were written by distinguished scientists from corresponding areas. Members of our project group have contributed a chapter on geodetic sets in graphs. Besides the survey of main results on geodetic sets that were published in last eight years, we added some new findings and pointed out possibilities for future research.
COBISS.SI-ID: 15720793
We prove that the edges of every graph of bounded (Euler) genus can be partitioned into any prescribed number k of pieces such that contracting any piece results in a graph of bounded tree-width, where the bound depends on k. This decomposition result parallels an analogous, simpler result for edge deletions instead of contractions, obtained recently by Baker, Eppstein and others. It generalizes a similar result for compression (a variant of contraction) in planar graphs (Klein 2005). Our decomposition result is a powerful tool for obtaining PTASs for arbitrary contraction-closed problems.
COBISS.SI-ID: 15802457