Florian Werner

collaborators

7 papers

math.CO2025

Leaf to leaf path lengths in trees of given degree sequence

Dieter Rautenbach, Johannes Scherer, Florian Werner

For a tree $T$ , let $l p (T)$ be the number of different lengths of leaf to leaf paths in $T$ . For a degree sequence $s$ of a tree, let $rad (s)$ be the minimum radius of a tree…

math.CO2025

Coloring by Pushing Vertices

Dieter Rautenbach, Laurin Schwartze, Florian Werner

Let $G$ be a graph of order $n$ , maximum degree at most $Δ$ , and no component of order $2$ . Inspired by the famous 1-2-3-conjecture, Bensmail, Marcille, and Orenga define a proper…

math.CO2024

An Optimization Approach to Degree Deviation and Spectral Radius

Dieter Rautenbach, Florian Werner

For a finite, simple, and undirected graph $G$ with $n$ vertices and average degree $d$ , Nikiforov introduced the degree deviation of $G$ as $s=\sum_{u\in V(G)}\left|d_G(u)-d\right…

math.CO2024

Degree Deviation and Spectral Radius

Dieter Rautenbach, Florian Werner

For a finite, simple, and undirected graph $G$ with $n$ vertices, $m$ edges, and largest eigenvalue $λ$ , Nikiforov introduced the degree deviation of $G$ as $s=\sum_{u\in V(G)}\lef…

cs.DM2024

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…

cs.DS2024

Induced Subforests and Superforests

Dieter Rautenbach, Florian Werner

Graph isomorphism, subgraph isomorphism, and maximum common subgraphs are classical well-investigated objects. Their (parameterized) complexity and efficiently tractable cases have…

cs.DS2024

Largest common subgraph of two forests

Dieter Rautenbach, Florian Werner

A common subgraph of two graphs $G_{1}$ and $G_{2}$ is a graph that is isomorphic to subgraphs of $G_{1}$ and $G_{2}$ . In the largest common subgraph problem the task is to determine a com…