Zobrazeno 1 - 10
of 103
pro vyhledávání: '"Picouleau, Christophe"'
An antimagic labelling of a graph is a bijection from the set of edges to $\{1, 2, \ldots , m\}$, such that all vertex-sums are pairwise distinct, where the vertex-sum of a vertex is the sum of labels on the edges incident to it. We say a graph is an
Externí odkaz:
http://arxiv.org/abs/2408.11931
Given a 3-uniform hypergraph H, its 2-intersection graph G has for vertex set the hyperedges of H and ee' is an edge of G whenever e and e' have exactly two common vertices in H. Di Marco et al. prove that deciding wether a graph G is the 2-intersect
Externí odkaz:
http://arxiv.org/abs/2305.13932
A set $S\subseteq V$ of a graph $G=(V,E)$ is a dominating set if each vertex has a neighbor in $S$ or belongs to $S$. Dominating Set is the problem of deciding, given a graph $G$ and an integer $k\geq 1$, if $G$ has a dominating set of size at most $
Externí odkaz:
http://arxiv.org/abs/2304.09701
Publikováno v:
In Theoretical Computer Science 27 June 2024 1001
Perfect Matching-Cut is the problem of deciding whether a graph has a perfect matching that contains an edge-cut. We show that this problem is NP-complete for planar graphs with maximum degree four, for planar graphs with girth five, for bipartite fi
Externí odkaz:
http://arxiv.org/abs/2011.03318
We study the following problem: for given integers $d,k$ and graph $G$, can we obtain a graph with diameter $d$ via at most $k$ edge deletions ? We determine the computational complexity of this and related problems for different values of $d$.
Externí odkaz:
http://arxiv.org/abs/2010.00273
Given a graph $G$ and a non trivial partition $(V_1,V_2)$ of its vertex-set, the satisfaction of a vertex $v\in V_i$ is the ratio between the size of it's closed neighborhood in $V_i$ and the size of its closed neighborhood in $G$. The worst ratio ov
Externí odkaz:
http://arxiv.org/abs/2007.12434
Given a graph $G=(V,E)$, $S\subseteq V$ is a dominating set if every $v\in V\setminus S$ is adjacent to an element of $S$. The Minimum Dominating Set problem asks for a dominating set with minimum cardinality. It is well known that its decision versi
Externí odkaz:
http://arxiv.org/abs/2002.12232
We prove that the Minimum Dominating Set problem is polynomial for the class of (claw, P8)-free graphs.
Externí odkaz:
http://arxiv.org/abs/2001.07554
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.