ﻻ يوجد ملخص باللغة العربية
A path in an(a) edge(vertex)-colored graph is called emph{a conflict-free path} if there exists a color used on only one of its edges(vertices). An(A) edge(vertex)-colored graph is called emph{conflict-free (vertex-)connected} if there is a conflict-free path between each pair of distinct vertices. We call the graph $G$ emph{strongly conflict-free connected }if there exists a conflict-free path of length $d_G(u,v)$ for every two vertices $u,vin V(G)$. And the emph{strong conflict-free connection number} of a connected graph $G$, denoted by $scfc(G)$, is defined as the smallest number of colors that are required to make $G$ strongly conflict-free connected. In this paper, we first investigate the question: Given a connected graph $G$ and a coloring $c: E(or V)rightarrow {1,2,cdots,k} (kgeq 1)$ of the graph, determine whether or not $G$ is, respectively, conflict-free connected, vertex-conflict-free connected, strongly conflict-free connected under coloring $c$. We solve this question by providing polynomial-time algorithms. We then show that it is NP-complete to decide whether there is a k-edge-coloring $(kgeq 2)$ of $G$ such that all pairs $(u,v)in P (Psubset Vtimes V)$ are strongly conflict-free connected. Finally, we prove that the problem of deciding whether $scfc(G)leq k$ $(kgeq 2)$ for a given graph $G$ is NP-complete.
A path in a vertex-colored graph is called emph{conflict free} if there is a color used on exactly one of its vertices. A vertex-colored graph is said to be emph{conflict-free vertex-connected} if any two vertices of the graph are connected by a conf
The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct pairs. We determine, with an exception of two cases, the complexity of the Disjoint P
This report documents the program and the outcomes of Dagstuhl Seminar 13082 Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices, held in February 2013 at Dagstuhl Castle.
A directed odd cycle transversal of a directed graph (digraph) $D$ is a vertex set $S$ that intersects every odd directed cycle of $D$. In the Directed Odd Cycle Transversal (DOCT) problem, the input consists of a digraph $D$ and an integer $k$. The
We establish a list of characterizations of bounded twin-width for hereditary, totally ordered binary structures. This has several consequences. First, it allows us to show that a (hereditary) class of matrices over a finite alphabet either contains