Advanced Search

A graph G is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class), where the vertices in one class are colored red and those in the other class are colored blue. Let F be a 2-stratified graph rooted at some blue vertex v. An F-coloring of a graph is a red-blue coloring of the vertices of G in which every blue vertex v belongs to a copy of F rooted at v. The F-domination number ${\gamma }_F\left(G\right)$ is the minimum number of red vertices in an F-coloring of G. In...

A graph is $2$-stratified if its vertex set is partitioned into two classes, where the vertices in one class are colored red and those in the other class are colored blue. Let $F$ be a $2$-stratified graph rooted at some blue vertex $v$. An $F$-coloring of a graph $G$ is a red-blue coloring of the vertices of $G$ in which every blue vertex $v$ belongs to a copy of $F$ rooted at $v$. The $F$-domination number ${\gamma }_F\left(G\right)$ is the minimum number of red vertices in an $F$-coloring of $G$. In this paper, we study $F$-domination where $F$ is...

The Traveling Salesman Problem (TSP) is still one of the most researched topics in computational mathematics, and we introduce a variant of it, namely the study of the closed k-walks in graphs. We search for a shortest closed route visiting k cities in a non complete graph without weights. This motivates the following definition. Given a set of k distinct vertices = x₁, x₂, ...,xₖ in a simple graph G, the closed k-stop-distance of set is defined to be $dₖ\left(\right)=mi{n}_{\Theta \in \left(\right)}(d(\Theta \left(x₁\right),\Theta \left(x₂\right))+d(\Theta \left(x₂\right),\Theta \left(x₃\right))+...+d(\Theta \left(xₖ\right),\Theta \left(x₁\right)))$, where () is the set of all permutations from...

For a nontrivial connected graph $G$, let $c:V\left(G\right)\to \mathbb{N}$ be a vertex coloring of $G$ where adjacent vertices may be colored the same. For a vertex $v\in V\left(G\right)$, the neighborhood color set $\mathrm{NC}\left(v\right)$ is the set of colors of the neighbors of $v$. The coloring $c$ is called a set coloring if $\mathrm{NC}\left(u\right)\ne \mathrm{NC}\left(v\right)$ for every pair $u,v$ of adjacent vertices of $G$. The minimum number of colors required of such a coloring is called the set chromatic number ${\chi }_{\mathrm{s}}\left(G\right)$. We show that the decision variant of determining ${\chi }_{\mathrm{s}}\left(G\right)$ is NP-complete in the general case, and show that ${\chi }_{\mathrm{s}}\left(G\right)$ can be...

Let $G_1$ and $G_2$ be copies of a graph $G$, and let $f:V\left(G_1\right)\to V\left(G_2\right)$ be a function. Then a functigraph $C(G,f)=(V,E)$ is a generalization of a permutation graph, where $V=V\left(G_1\right)\cup V\left(G_2\right)$ and $E=E\left(G_1\right)\cup E\left(G_2\right)\cup \{uv:u\in V\left(G_1\right),v\in V\left(G_2\right),v=f\left(u\right)\}$. In this paper, we study colorability and planarity of functigraphs.

Let G₁ and G₂ be disjoint copies of a graph G, and let f:V(G₁) → V(G₂) be a function. Then a functigraph C(G,f) = (V,E) has the vertex set V = V(G₁) ∪ V(G₂) and the edge set E = E(G₁) ∪ E(G₂) ∪ {uv | u ∈ V(G₁), v ∈ V(G₂),v = f(u)}. A functigraph is a generalization of a permutation graph (also known as a generalized prism) in the sense of Chartrand and Harary. In this paper, we study domination in functigraphs. Let γ(G) denote the domination number of G. It is readily seen that γ(G) ≤ γ(C(G,f))...