Zobrazeno 1 - 10
of 534
pro vyhledávání: '"Yeo, Anders"'
An oriented graph $D$ is converse invariant if, for any tournament $T$, the number of copies of $D$ in $T$ is equal to that of its converse $-D$. El Sahili and Ghazo Hanna [J. Graph Theory 102 (2023), 684-701] showed that any oriented graph $D$ with
Externí odkaz:
http://arxiv.org/abs/2407.17051
It is well-known and easy to show that even the following version of the directed travelling salesman problem is NP-complete: Given a strongly connected complete digraph $D=(V,A)$, a cost function $w: A\rightarrow \{0,1\}$ and a natural number $K$; d
Externí odkaz:
http://arxiv.org/abs/2403.07597
A bisection in a graph is a cut in which the number of vertices in the two parts differ by at most 1. In this paper, we give lower bounds for the maximum weight of bisections of edge-weighted graphs with bounded maximum degree. Our results improve a
Externí odkaz:
http://arxiv.org/abs/2401.10074
In 1981, Bermond and Thomassen conjectured that for any positive integer $k$, every digraph with minimum out-degree at least $2k-1$ admits $k$ vertex-disjoint directed cycles. In this short paper, we verify the Bermond-Thomassen conjecture for triang
Externí odkaz:
http://arxiv.org/abs/2311.13369
In order to coordinate players in a game must first identify a target pattern of behaviour. In this paper we investigate the difficulty of identifying prominent outcomes in two kinds of binary action coordination problems in social networks: pure coo
Externí odkaz:
http://arxiv.org/abs/2311.03195
We introduce and study a new optimization problem on digraphs, termed Maximum Weighted Digraph Partition (MWDP) problem. We prove three complexity dichotomies for MWDP: on arbitrary digraphs, on oriented digraphs, and on symmetric digraphs. We demons
Externí odkaz:
http://arxiv.org/abs/2307.01109
For a vertex $x$ of a digraph, $d^+(x)$ ($d^-(x)$, resp.) is the number of vertices at distance 1 from (to, resp.) $x$ and $d^{++}(x)$ is the number of vertices at distance 2 from $x$. In 1995, Seymour conjectured that for any oriented graph $D$ ther
Externí odkaz:
http://arxiv.org/abs/2306.03493
We investigate the difficulty of finding economically efficient solutions to coordination problems on graphs. Our work focuses on two forms of coordination problem: pure-coordination games and anti-coordination games. We consider three objectives in
Externí odkaz:
http://arxiv.org/abs/2305.07124
We obtain lower and upper bounds for the maximum weight of a directed cut in the classes of weighted digraphs and weighted acyclic digraphs as well as in some of their subclasses. We compare our results with those obtained for the maximum size of a d
Externí odkaz:
http://arxiv.org/abs/2304.10202
Autor:
Gutin, Gregory, Yeo, Anders
A graph $H$ is a clique graph if $H$ is a vertex-disjoin union of cliques. Abu-Khzam (2017) introduced the $(a,d)$-{Cluster Editing} problem, where for fixed natural numbers $a,d$, given a graph $G$ and vertex-weights $a^*:\ V(G)\rightarrow \{0,1,\do
Externí odkaz:
http://arxiv.org/abs/2210.07722