ﻻ يوجد ملخص باللغة العربية
We study the dominating set reconfiguration problem with the token sliding rule. It consists, given a graph G=(V,E) and two dominating sets D_s and D_t of G, in determining if there exists a sequence S=<D_1:=D_s,...,D_l:=D_t> of dominating sets of G such that for any two consecutive dominating sets D_r and D_{r+1} with r<t, D_{r+1}=(D_r u) U v, where uv is an edge of G. In a recent paper, Bonamy et al studied this problem and raised the following questions: what is the complexity of this problem on circular arc graphs? On circle graphs? In this paper, we answer both questions by proving that the problem is polynomial on circular-arc graphs and PSPACE-complete on circle graphs.
In this paper, we study independent domination in directed graphs, which was recently introduced by Cary, Cary, and Prabhu. We provide a short, algorithmic proof that all directed acyclic graphs contain an independent dominating set. Using linear alg
Gromov hyperbolicity is an interesting geometric property, and so it is natural to study it in the context of geometric graphs. It measures the tree-likeness of a graph from a metric viewpoint. In particular, we are interested in circular-arc graphs,
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
Given a graph $G=(V,E)$, the dominating set problem asks for a minimum subset of vertices $Dsubseteq V$ such that every vertex $uin Vsetminus D$ is adjacent to at least one vertex $vin D$. That is, the set $D$ satisfies the condition that $|N[v]cap D
For $kgeq 1$, a $k$-colouring $c$ of $G$ is a mapping from $V(G)$ to ${1,2,ldots,k}$ such that $c(u) eq c(v)$ for any two non-adjacent vertices $u$ and $v$. The $k$-Colouring problem is to decide if a graph $G$ has a $k$-colouring. For a family of gr