Let $G=(V,E)$ be a simple graph. A $3$-valued function $fV\left(G\right)\to \{-1,0,1\}$ is said to be a minus dominating function if for every vertex $v\in V$, $f\left(N\left[v\right]\right)={\sum }_{u\in N\left[v\right]}f\left(u\right)\ge 1$, where $N\left[v\right]$ is the closed neighborhood of $v$. The weight of a minus dominating function $f$ on $G$ is $f\left(V\right)={\sum }_{v\in V}f\left(v\right)$. The minus domination number of a graph $G$, denoted by ${\gamma }^{-}\left(G\right)$, equals the minimum weight of a minus dominating function on $G$. In this paper, the following two results are obtained. (1) If $G$ is a bipartite graph of order $n$, then $${\gamma }^{-}\left(G\right)\ge 4\left(\sqrt{n+1}-1\right)-n.$$ (2) For any negative integer $k$ and any positive integer $m\ge 3$, there exists...

Let p be a positive integer and G = (V,E) a graph. A subset S of V is a p-dominating set if every vertex of V-S is dominated at least p times. The minimum cardinality of a p-dominating set a of G is the p-domination number γₚ(G). It is proved for a cactus graph G that γₚ(G) ⩽ (|V| + |Lₚ(G)| + c(G))/2, for every positive integer p ⩾ 2, where Lₚ(G) is the set of vertices of G of degree at most p-1 and c(G) is the number of odd cycles in G.

A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertexconnected. It was proved that if G is a graph of order n with minimum degree δ, then rvc(G) < 11n/δ. In this paper, we show that rvc(G) ≤ 3n/(δ+1)+5 for [xxx] and n ≥ 290, while rvc(G) ≤ 4n/(δ + 1) + 5...

Let G be a graph. A function f : V (G) → {−1, 1} is a signed k- independence function if the sum of its function values over any closed neighborhood is at most k − 1, where k ≥ 2. The signed k-independence number of G is the maximum weight of a signed k-independence function of G. Similarly, the signed total k-independence number of G is the maximum weight of a signed total k-independence function of G. In this paper, we present new bounds on these two parameters which improve some existing bounds....

Let G be a connected graph. A vertex w ∈ V.G/ strongly resolves two vertices u,v ∈ V.G/ if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set S of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality of a strong resolving set for G is called the strong metric dimension of G. It is well known that the problem of computing this invariant is NP-hard. In this paper we study...

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ t(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sdγt (G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. Karami, Khoeilar, Sheikholeslami and Khodkar, (Graphs and...

The technique of counting cliques in networks is a natural problem. In this paper, we develop certain results on counting of triangles for the total graph of the Mycielski graph or central graph of star as well as completegraph families. Moreover, we discuss the upper bounds for the number of triangles in the Mycielski and other well known transformations of graphs. Finally, it is shown that the achromatic number and edge-covering number of the transformations mentioned above are equated.

Let k be a positive integer and let G = (V,E) be a simple graph. The k-tuple domination number ${\gamma }_{\times k}\left(G\right)$ of G is the minimum cardinality of a k-tuple dominating set S, a set that for every vertex v ∈ V, $|N_G\left[v\right]\cap S|\ge k$. Also the total k-domination number ${\gamma }_{\times k,t}\left(G\right)$ of G is the minimum cardinality of a total k -dominating set S, a set that for every vertex v ∈ V, $|N_G\left(v\right)\cap S|\ge k$. The k-transversal number τₖ(H) of a hypergraph H is the minimum size of a subset S ⊆ V(H) such that |S ∩e | ≥ k for every edge e ∈ E(H). We know that for any graph...

Let G = (V,E) be a graph. A total restrained dominating set is a set S ⊆ V where every vertex in V∖S is adjacent to a vertex in S as well as to another vertex in V∖S, and every vertex in S is adjacent to another vertex in S. The total restrained domination number of G, denoted by ${\gamma }_r^t\left(G\right)$, is the smallest cardinality of a total restrained dominating set of G. We determine lower and upper bounds on the total restrained domination number of the direct product of two graphs. Also, we show that these bounds...

Let G = (V,E) be a graph of order n and let D ⊆ {0, 1, 2, 3, . . .}. For v ∈ V, let ND(v) = {u ∈ V : d(u, v) ∈ D}. The graph G is said to be D-vertex magic if there exists a bijection f : V (G) → {1, 2, . . . , n} such that for all v ∈ V, ∑uv∈ND(v) f(u) is a constant, called D-vertex magic constant. O’Neal and Slater have proved the uniqueness of the D-vertex magic constant by showing that it can be determined by the D-neighborhood fractional domination number of the graph. In this paper we give...

This paper is part of a work in progress whose goal is to construct a fast, practical algorithm for the vertex separation (VS) of cactus graphs. We prove a theorem for cacti", a necessary and sufficient condition for the VS of a cactus graph being k. Further, we investigate the ensuing ramifications that prevent the construction of an algorithm based on that theorem only.

In this paper we initiate the study of total restrained domination in graphs. Let $G=(V,E)$ be a graph. A total restrained dominating set is a set $S\subseteq V$ where every vertex in $V-S$ is adjacent to a vertex in $S$ as well as to another vertex in $V-S$, and every vertex in $S$ is adjacent to another vertex in $S$. The total restrained domination number of $G$, denoted by ${\gamma }_r^t\left(G\right)$, is the smallest cardinality of a total restrained dominating set of $G$. First, some exact values and sharp bounds for ${\gamma }_r^t\left(G\right)$ are given in Section 2. Then the Nordhaus-Gaddum-type...

Unique minimum vertex dominating sets in the Cartesian product of a graph with a complete graph are considered. We first give properties of such sets when they exist. We then show that when the first factor of the product is a tree, consideration of the tree alone is sufficient to determine if the product has a unique minimum dominating set.

For a fixed positive integer $k$ and $G=(V,E)$ a connected graph of order $n$, whose minimum vertex degree is at least $k$, a set $S\subseteq V$ is a total $k$-dominating set, also known as a $k$-tuple total dominating set, if every vertex $v\in V$ has at least $k$ neighbors in $S$. The minimum size of a total $k$-dominating set for $G$ is called the total $k$-domination number of $G$, denoted by ${\gamma }_{kt}\left(G\right)$. The total $k$-domination problem is to determine a minimum total $k$-dominating set of $G$. Since the exact problem is in general quite difficult to solve,...

A dominating set D for a graph G is a subset of V(G) such that any vertex in V(G)-D has a neighbor in D, and a domination number γ(G) is the size of a minimum dominating set for G. For the Cartesian product G ⃞ H Vizing's conjecture [10] states that γ(G ⃞ H) ≥ γ(G)γ(H) for every pair of graphs G,H. In this paper we introduce a new concept which extends the ordinary domination of graphs, and prove that the conjecture holds when γ(G) = γ(H) = 3.

A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer [14] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. One of the most challenging problems in this area, posed in the survey of Plummer [15], is to find a good characterization of well-covered graphs of girth 4. We examine several subclasses of well-covered graphs of girth ≥ 4 with respect to the odd girth of the...

In on-line computation, the instance of the problem dealt is not entirely known from the beginning of the solution process, but it is revealed step-by-step. In this paper we deal with on-line independent set. On-line models studied until now for this problem suppose that the input graph is initially empty and revealed either vertex-by-vertex, or cluster-by-cluster. Here we present a new on-line model quite different to the ones already studied. It assumes that a superset of the final graph is initially...