Zobrazeno 1 - 10
of 296
pro vyhledávání: '"Araújo, Júlio"'
A good edge-labeling (gel for short) of a graph $G$ is a function $\lambda: E(G) \to \mathbb{R}$ such that, for any ordered pair of vertices $(x, y)$ of $G$, there do not exist two distinct increasing paths from $x$ to $y$, where ``increasing'' means
Externí odkaz:
http://arxiv.org/abs/2408.15181
In this paper, we study two graph convexity parameters: iteration time and general position number. The iteration time was defined in 1981 in the geodesic convexity, but its computational complexity was so far open. The general position number was de
Externí odkaz:
http://arxiv.org/abs/2305.00467
Publikováno v:
In Applied Mathematics and Computation 15 February 2025 487
A blocking set in a graph $G$ is a subset of vertices that intersects every maximum independent set of $G$. Let ${\sf mmbs}(G)$ be the size of a maximum (inclusion-wise) minimal blocking set of $G$. This parameter has recently played an important rol
Externí odkaz:
http://arxiv.org/abs/2102.03404
In the Maximum Minimal Vertex Cover (MMVC) problem, we are given a graph $G$ and a positive integer $k$, and the objective is to decide whether $G$ contains a minimal vertex cover of size at least $k$. Motivated by the kernelization of MMVC with para
Externí odkaz:
http://arxiv.org/abs/2102.02484
In this work, we introduce a new graph convexity, that we call Cycle Convexity, motivated by related notions in Knot Theory. For a graph $G=(V,E)$, define the interval function in the Cycle Convexity as $I_{cc}(S) = S\cup \{v\in V(G)\mid \text{there
Externí odkaz:
http://arxiv.org/abs/2012.05656
An orientation $D$ of a graph $G=(V,E)$ is a digraph obtained from $G$ by replacing each edge by exactly one of the two possible arcs with the same end vertices. For each $v \in V(G)$, the indegree of $v$ in $D$, denoted by $d^-_D(v)$, is the number
Externí odkaz:
http://arxiv.org/abs/2011.14719
Let $D$ be an orientation of a simple graph. Given $u,v\in V(D)$, a directed shortest $(u,v)$-path is a $(u,v)$-geodesic. $S \subseteq V(D)$ is convex if, for every $u,v \in S$, the vertices in each $(u,v)$-geodesic and in each $(v,u)$-geodesic are i
Externí odkaz:
http://arxiv.org/abs/1911.10240