Johannes Pardey

activity

20202023

most citedMaximizing the Mostar index for bipartite graphs and split graphs

2 citations · 3 across the 14 of their papers we have counts for

collaborators

15 papers

math.CO2023

Mostar index and bounded maximum degree

Michael A. Henning, Johannes Pardey, Dieter Rautenbach +1

Došlić et al. defined the Mostar index of a graph $G$ as $M o (G) = uv \in E (G) \sum ∣ n_{G} (u, v) - n_{G} (v, u) ∣$ , where, for an edge $uv$ of $G$ , the term $n_{G} (u, v)$ denotes the number…

math.CO2023

Vertex degrees close to the average degree

Johannes Pardey, Dieter Rautenbach

Let $G$ be a finite, simple, and undirected graph of order $n$ and average degree $d$ . Up to terms of smaller order, we characterize the minimal intervals $I$ containing $d$ that a…

math.CO2022★ 1 cited

Bounding the Mostar index

Štefko Miklavič, Johannes Pardey, Dieter Rautenbach +1

math.CO2022★ 2 cited

Maximizing the Mostar index for bipartite graphs and split graphs

Štefko Miklavič, Johannes Pardey, Dieter Rautenbach +1

Došlić et al.~defined the Mostar index of a graph $G$ as $uv \in E (G) \sum ∣ n_{G} (u, v) - n_{G} (v, u) ∣$ , where, for an edge $uv$ of $G$ , the term $n_{G} (u, v)$ denotes the number of ve…

math.CO2022

Majority Edge-Colorings of Graphs

Felix Bock, Rafał Kalinowski, Johannes Pardey +3

We propose the notion of a majority $k$ -edge-coloring of a graph $G$ , which is an edge-coloring of $G$ with $k$ colors such that, for every vertex $u$ of $G$ , at most half the edge…

math.CO2022

Relating the independence number and the dissociation number

Felix Bock, Johannes Pardey, Lucia D. Penso +1

The independence number $α (G)$ and the dissociation number $diss (G)$ of a graph $G$ are the largest orders of induced subgraphs of $G$ of maximum degree at most $0$ and at mo…

math.CO2022

A bound on the dissociation number

Felix Bock, Johannes Pardey, Lucia D. Penso +1

The dissociation number $diss (G)$ of a graph $G$ is the maximum order of a set of vertices of $G$ inducing a subgraph that is of maximum degree at most $1$ . Computing the dis…

math.CO2022

Relating dissociation, independence, and matchings

Felix Bock, Johannes Pardey, Lucia D. Penso +1

A dissociation set in a graph is a set of vertices inducing a subgraph of maximum degree at most $1$ . Computing the dissociation number $diss (G)$ of a given graph $G$ , define…

math.CO2021

Diameter, edge-connectivity, and $C_{4}$ -freeness

Vanessa Hiebeler, Johannes Pardey, Dieter Rautenbach

Improving a recent result of Fundikwa, Mazorodze, and Mukwembi, we show that $d \leq (2 n - 3) /5$ for every connected $C_{4}$ -free graph of order $n$ , diameter $d$ , and edge-connectivit…

math.CO2021

Factorially many maximum matchings close to the Erdős-Gallai bound

Stéphane Bessy, Johannes Pardey, Lucas Picasarri-Arrieta +1

A classical result of Erdős and Gallai determines the maximum size $m (n, ν)$ of a graph $G$ of order $n$ and matching number $ν n$ . We show that $G$ has factorially many maximum matc…

math.CO2021

Unbalanced spanning subgraphs in edge labeled complete graphs

Stéphane Bessy, Johannes Pardey, Lucas Picasarri-Arrieta +1

Let $K$ be a complete graph of order $n$ . For $d \in (0, 1)$ , let $c$ be a $\pm 1$ -edge labeling of $K$ such that there are $d (2 n)$ edges with label $+ 1$ , and let $G$ be a sp…

math.CO2021

Almost color-balanced perfect matchings in color-balanced complete graphs

Johannes Pardey, Dieter Rautenbach

For a graph $G$ and a not necessarily proper $k$ -edge coloring $c : E (G) \to {1, \dots, k}$ , let $m_{i} (G)$ be the number of edges of $G$ of color $i$ , and call $G$ {\it color-balance…

math.CO2021

Efficiently finding low-sum copies of spanning forests in zero-sum complete graphs via conditional expectation

Johannes Pardey, Dieter Rautenbach

For a fixed positive $ε$ , we show the existence of a constant $C_{ε}$ with the following property: Given a $\pm 1$ -edge-labeling $c : E (K_{n}) \to {- 1, 1}$ of the complete graph $K_{n}$ wi…

math.CO2021

Zero-sum copies of spanning forests in zero-sum complete graphs

Elena Mohr, Johannes Pardey, Dieter Rautenbach

For a complete graph $K_{n}$ of order $n$ , an edge-labeling $c : E (K_{n}) \to {- 1, 1}$ satisfying $c (E (K_{n})) = 0$ , and a spanning forest $F$ of $K_{n}$ , we consider the problem to minimize…

math.CO2020

Exponential Independence in Subcubic Graphs

Stéphane Bessy, Johannes Pardey, Dieter Rautenbach

A set $S$ of vertices of a graph $G$ is exponentially independent if, for every vertex $u$ in $S$ , $$\sum\limits_{v\in S\setminus \{ u\}}\left(\frac{1}{2}\right)^{{\rm dist}_{(G,S)…

Mostar index and bounded maximum degree

Vertex degrees close to the average degree

Bounding the Mostar index

Maximizing the Mostar index for bipartite graphs and split graphs

Majority Edge-Colorings of Graphs

Relating the independence number and the dissociation number

A bound on the dissociation number

Relating dissociation, independence, and matchings

Diameter, edge-connectivity, and C4​-freeness

Factorially many maximum matchings close to the Erdős-Gallai bound

Unbalanced spanning subgraphs in edge labeled complete graphs

Almost color-balanced perfect matchings in color-balanced complete graphs

Efficiently finding low-sum copies of spanning forests in zero-sum complete graphs via conditional expectation

Zero-sum copies of spanning forests in zero-sum complete graphs

Exponential Independence in Subcubic Graphs

Diameter, edge-connectivity, and $C_{4}$ -freeness