Zobrazeno 1 - 10
of 191
pro vyhledávání: '"Brewster, Richard"'
Given a graph $G=(V,E)$ of diameter $d$, a broadcast is a function $f:V(G) \to \{ 0, 1, \dots, d \}$ where $f(v)$ is at most the eccentricity of $v$. A vertex $v$ is broadcasting if $f(v)>0$ and a vertex $u$ hears $v$ if $d(u,v) \leq f(v)$. A broadca
Externí odkaz:
http://arxiv.org/abs/2406.05825
The complexity of the list homomorphism problem for signed graphs appears difficult to classify. Existing results focus on special classes of signed graphs, such as trees and reflexive signed graphs. Irreflexive signed graphs are in a certain sense t
Externí odkaz:
http://arxiv.org/abs/2306.06449
Let $G$ be a graph in which each edge is assigned one of the colours $1, 2, \ldots, m$, and let $\Gamma$ be a subgroup of $S_m$. The operation of switching at a vertex $x$ of $G$ with respect to an element $\pi$ of $\Gamma$ permutes the colours of th
Externí odkaz:
http://arxiv.org/abs/2306.05962
The independent domination number $i(G)$ of a graph $G$ is the minimum cardinality of a maximal independent set of $G$, also called an $i(G)$-set. The $i$-graph of $G$ is the graph whose vertices correspond to the $i(G)$-sets, and where two $i(G)$-se
Externí odkaz:
http://arxiv.org/abs/2305.17814
Autor:
Booker, Kyle, Brewster, Richard C
We present a edge-coloured analogue of the duality theorem for transitive tournaments and directed paths. Given a edge-coloured path $P$ whose edges alternate blue and red, we construct a edge-coloured graph $D$ so that for any edge-coloured graph $G
Externí odkaz:
http://arxiv.org/abs/2208.12326
The CSP dichotomy conjecture has been recently established, but a number of other dichotomy questions remain open, including the dichotomy classification of list homomorphism problems for signed graphs. Signed graphs arise naturally in many contexts,
Externí odkaz:
http://arxiv.org/abs/2206.01068
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, vol. 24, no 2, Graph Theory (November 3, 2022) dmtcs:9242
A mixed graph is a set of vertices together with an edge set and an arc set. An $(m,n)$-mixed graph $G$ is a mixed graph whose edges are each assigned one of $m$ colours, and whose arcs are each assigned one of $n$ colours. A \emph{switch} at a verte
Externí odkaz:
http://arxiv.org/abs/2203.08070
Publikováno v:
In Theoretical Computer Science 27 June 2024 1001
Autor:
Brewster, Richard C., Moore, Benjamin
Given a graph $G$, the $k$-mixing problem asks: Can one obtain all $k$-colourings of $G$, starting from one $k$-colouring $f$, by changing the colour of only one vertex at a time, while at each step maintaining a $k$-colouring? More generally, for a
Externí odkaz:
http://arxiv.org/abs/2008.12185
We consider homomorphisms of signed graphs from a computational perspective. In particular, we study the list homomorphism problem seeking a homomorphism of an input signed graph $(G,\sigma)$, equipped with lists $L(v) \subseteq V(H), v \in V(G)$, of
Externí odkaz:
http://arxiv.org/abs/2005.05547