The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still very large. The...

The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still very large....

Let $X$ be a finite simple undirected graph with a subgroup $G$ of the full automorphism group $\mathrm{Aut}\left(X\right)$. Then $X$ is said to be $(G,s)$-transitive for a positive integer $s$, if $G$ is transitive on $s$-arcs but not on $(s+1)$-arcs, and $s$-transitive if it is $\left(\mathrm{Aut}\right(X),s)$-transitive. Let $G_v$ be a stabilizer of a vertex $v\in V\left(X\right)$ in $G$. Up to now, the structures of vertex stabilizers $G_v$ of cubic, tetravalent or pentavalent $(G,s)$-transitive graphs are known. Thus, in this paper, we give the structure of the vertex stabilizers $G_v$ of connected hexavalent $(G,s)$-transitive...

An infinite class of counterexamples is given to a conjecture of Dahme et al. [1] concerning the minimum size of a dominating vertex set that contains at least a prescribed proportion of the neighbors of each vertex not belonging to the set.

For a given graph G and a positive integer r the r-path graph, $P_r\left(G\right)$, has for vertices the set of all paths of length r in G. Two vertices are adjacent when the intersection of the corresponding paths forms a path of length r-1, and their union forms either a cycle or a path of length k+1 in G. Let $P_r^k\left(G\right)$ be the k-iteration of r-path graph operator on a connected graph G. Let H be a subgraph of $P_r^k\left(G\right)$. The k-history $P_r^{-k}\left(H\right)$ is a subgraph of G that is induced by all edges that take part in the recursive definition of...

A 2-stratified graph $G$ is a graph whose vertex set has been partitioned into two subsets, called the strata or color classes of $G$. Two $2$-stratified graphs $G$ and $H$ are isomorphic if there exists a color-preserving isomorphism $\phi$ from $G$ to $H$. A $2$-stratified graph $G$ is said to be homogeneously embedded in a $2$-stratified graph $H$ if for every vertex $x$ of $G$ and every vertex $y$ of $H$, where $x$ and $y$ are colored the same, there exists an induced $2$-stratified subgraph $H^{\text{'}}$ of $H$ containing $y$ and a color-preserving...

Let $(H,r)$ be a fixed rooted digraph. The $(H,r)$-coloring problem is the problem of deciding for which rooted digraphs $(G,s)$ there is a homomorphism $f:G\to H$ which maps the vertex $s$ to the vertex $r$. Let $(H,r)$ be a rooted oriented path. In this case we characterize the nonexistence of such a homomorphism by the existence of a rooted oriented cycle $(C,q)$, which is homomorphic to $(G,s)$ but not homomorphic to $(H,r)$. Such a property of the digraph $(H,r)$ is called rooted cycle duality or $*$-cycle duality. This extends the analogical result for...