Let α ∈ (0,1) and let $G=(V_G,E_G$) be a graph. According to Dunbar, Hoffman, Laskar and Markus [3] a set $D\subseteq V_G$ is called an α-dominating set of G, if $|N_G\left(u\right)\cap D|\ge \alpha d_G\left(u\right)$ for all $u\in V_G\setminus D$. We prove a series of upper bounds on the α-domination number of a graph G defined as the minimum cardinality of an α-dominating set of G.

Let $R$ be a ring with identity and $M$ be a unitary left $R$-module. The co-intersection graph of proper submodules of $M$, denoted by $\Omega \left(M\right)$, is an undirected simple graph whose vertex set $V\left(\Omega \right)$ is a set of all nontrivial submodules of $M$ and two distinct vertices $N$ and $K$ are adjacent if and only if $N+K\ne M$. We study the connectivity, the core and the clique number of $\Omega \left(M\right)$. Also, we provide some conditions on the module $M$, under which the clique number of $\Omega \left(M\right)$ is infinite and $\Omega \left(M\right)$ is a planar graph. Moreover, we give several...

Upper and lower bounds on the total domination number of the direct product of graphs are given. The bounds involve the {2}-total domination number, the total 2-tuple domination number, and the open packing number of the factors. Using these relationships one exact total domination number is obtained. An infinite family of graphs is constructed showing that the bounds are best possible. The domination number of direct products of graphs is also bounded from below.

Let G = (V,E) be a graph. A function f : V → {-1,1} is called a bad function of G if ∑u∈NG(v) f(u) ≤ 1 for all v ∈ V where NG(v) denotes the set of neighbors of v in G. The negative decision number of G, introduced in [12], is the maximum value of ∑v∈V f(v) taken over all bad functions of G. In this paper, we present sharp upper bounds on the negative decision number of a graph in terms of its order, minimum degree, and maximum degree. We also establish a sharp Nordhaus-Gaddum-type inequality for...

A subset S of V (G) is an independent dominating set of G if S is independent and each vertex of G is either in S or adjacent to some vertex of S. Let i(G) denote the minimum cardinality of an independent dominating set of G. A graph G is k-i-critical if i(G) = k, but i(G+uv) < k for any pair of non-adjacent vertices u and v of G. In this paper, we establish that if G is a connected 3-i-critical graph and S is a vertex cutset of G with |S| ≥ 3, then [...] improving a result proved by Ao [3],...

We consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) = γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k-path vertex cover number and the distance (k − 1)-domination number, respectively. We study (ψk−γk−1)-perfect paths, cycles and complete graphs for k ≥ 2. Moreover, we provide a complete characterisation of (ψ2 − γ1)- perfect graphs describing the set of its forbidden induced subgraphs and providing the explicit characterisation of the structure of graphs belonging...

Let $T$ be a tree. Then a vertex of $T$ with degree one is a leaf of $T$ and a vertex of degree at least three is a branch vertex of $T$. The set of leaves of $T$ is denoted by $L\left(T\right)$ and the set of branch vertices of $T$ is denoted by $B\left(T\right)$. For two distinct vertices $u$, $v$ of $T$, let $P_T[u,v]$ denote the unique path in $T$ connecting $u$ and $v.$ Let $T$ be a tree with $B\left(T\right)\ne \varnothing$. For each leaf $x$ of $T$, let $y_x$ denote the nearest branch vertex to $x$. We delete $V\left(P_T[x,y_x]\right)\setminus \left\{y_x\right\}$ from $T$ for all $x\in L\left(T\right)$. The resulting subtree of $T$ is called the reducible stem of $T$ and denoted...

In this paper we obtain several tight bounds on different types of alliance numbers of a graph, namely (global) defensive alliance number, global offensive alliance number and global dual alliance number. In particular, we investigate the relationship between the alliance numbers of a graph and its algebraic connectivity, its spectral radius, and its Laplacian spectral radius.

The Maximum Stable Set (MS) problem is a well known NP-hard problem. However different graph classes for which MS can be efficiently solved have been detected and the augmenting graph technique seems to be a fruitful tool to this aim. In this paper we apply a recent characterization of minimal augmenting graphs [22] to prove that MS can be solved for $(P₆,K_{2,3})$-free graphs in polynomial time, extending some known results.

A Roman dominating function (RDF) on a graph G = (V,E) is a function f : V −→ {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of an RDF is the value f(V (G)) = P u2V (G) f(u). An RDF f in a graph G is independent if no two vertices assigned positive values are adjacent. The Roman domination number R(G) (respectively, the independent Roman domination number iR(G)) is the minimum weight of an RDF (respectively,...

In this paper we study some of the structural properties of the set of all minimal total dominating functions (${}_T$) of cycles and paths and introduce the idea of function reducible graphs and function separable graphs. It is proved that a function reducible graph is a function separable graph. We shall also see how the idea of function reducibility is used to study the structure of ${}_T\left(G\right)$ for some classes of graphs.

Significant values of a combinatorial count need not fit the recurrence for the count. Consequently, initial values of the count can much outnumber those for the recurrence. So is the case of the count, Gl(n), of distance-l independent sets on the cycle Cn, studied by Comtet for l ≥ 0 and n ≥ 1 [sic]. We prove that values of Gl(n) are nth power sums of the characteristic roots of the corresponding recurrence unless 2 ≤ n ≤ l. Lucas numbers L(n) are thus generalized since L(n) is the count in question...