4 papers
Cutwidth and Crossings
Johannes Rauch, Dieter Rautenbach
We provide theoretical insights around the cutwidth of a graph and the One-Sided Crossing Minimization (OSCM) problem. OSCM was posed in the Parameterized Algorithms and Computatio…
Forest Cuts in Sparse Graphs
Vsevolod Chernyshev, Johannes Rauch, Dieter Rautenbach
We propose the conjecture that every graph of order with less than edges has a vertex cut that induces a forest. Maximal planar graphs do not have such vertex cuts a…
Degree Deviation and Spectral Radius
Dieter Rautenbach, Florian Werner
For a finite, simple, and undirected graph with vertices, edges, and largest eigenvalue , Nikiforov introduced the degree deviation of as $s=\sum_{u\in V(G)}\lef…
Complexity of Deciding the Equality of Matching Numbers
Guilherme C. M. Gomes, Bruno P. Masquio, Paulo E. D. Pinto +4
A matching is said to be disconnected if the saturated vertices induce a disconnected subgraph and induced if the saturated vertices induce a 1-regular graph. The disconnected and…