Narrow Results

Let $G=(V,E)$ be a simple connected graph. A dominating set $D\subseteq V$ is an independent dominating set of graph $G$ if the subgraph induced by $D$ is isomorphic to an empty graph. The minimum cardinality of an independent dominating set, denoted by $i(G)$, is called the independent domination number of graph $G$. It is known that for any tree $i(T)\le \frac{n(T)+\gamma (T)+l(T)}{4}$. The extremal trees attaining the bound is characterized, which answers the problem posed in [A. Cabrera-Martínez, New bounds on the double domination number of trees, Discrete Appl. Math.315 (2022) 97–103].

In many fields, including science, technology, engineering, and communication networks, the idea of domination is used. Double domination is a widely recognized idea of domination concept in graph theory. A prominent crucial factor in network architecture is integrity. A subset $S$ of $V(G)$ is called a double dominating set of $G$ if each vertex of $G$ is dominated at least twice by $S$. In this paper, an algorithm to compute the double domination integrity of graphs is given. Also, an application of double domination integrity in the optimal phasor measurement unit placement problem in a power system is given.

Let $G=(V,E)$ be a simple connected graph. An edge $e\in E(G)$$\mathrm{\text{ev}}$-dominates a vertex $v\in V$ if $e$ is incident with $v$ or $e$ is incident with a vertex adjacent to $v$. A set $D\subset E$ is an edge-vertex dominating set of graph $G$ if every vertex in $V$ is $\mathrm{\text{ev}}$-dominated by an edge in $D$. An edge-vertex dominating set $D$ is minimal edge-vertex dominating set if any proper subset of $D$ is not an edge-vertex dominating set. The minimum (maximum, respectively) cardinality of minimal edge-vertex dominating set is called the edge-vertex domination number (upper edge-vertex domination number, respectively) of a graph $G$ and is denoted by ${\gamma }_{\mathrm{\text{ev}}}(G)$ (${\mathrm{\Gamma }}_{ve}(G)$, respectively). Gallai type inequalities ${\mathrm{\Gamma }}_{\mathrm{\text{ev}}}(T)+\gamma (T)\le n(T)$ and $\mathrm{\Gamma }(T)+{\gamma }_{\mathrm{\text{ev}}}(T)\le n(T)$ are proved and extremal trees attaining the equality are characterized.

The spanning star forest problem is an interesting algorithmic problem in combinatorial optimization and finds different applications. We generalize it into the spanning k-tree forest problem, which is to find a maximum spanning forest in which each tree component has a central vertex and other vertices in the component have distance at most k away from the central vertex. We show that this new problem can be approximated with ratio in polynomial time for both undirected and directed graphs. In the weighted distance model, a ½-approximation algorithm is presented for it.

A set of vertices D is a dominating set of a graph G=(V, E) if every vertex in V−D is adjacent to at least one vertex in D. The domatic partition of G is the partition of the vertex set V into a maximum number of dominating sets. In this paper, we present efficient parallel algorithms for finding the domatic partition of Interval graphs, Block graphs and K-trees.

A weakly connected dominating set (WCDS) of graph G is a subset of G so that the vertex set of the given subset and all vertices with at least one endpoint in the subset induce a connected sub-graph of G. The minimum WCDS (MWCDS) problem is known to be NP-hard, and several approximation algorithms have been proposed for solving MWCDS in deterministic graphs. However, to the best of our knowledge no work has been done on finding the WCDS in stochastic graphs. In this paper, a definition of the MWCDS problem in a stochastic graph is first presented and then several learning automata-based algorithms are proposed for solving the stochastic MWCDS problem where the probability distribution function of the weight associated with the graph vertices is unknown. The proposed algorithms significantly reduce the number of samples needs to be taken from the vertices of the stochastic graph. It is shown that by a proper choice of the parameters of the proposed algorithms, the probability of finding the MWCDS is as close to unity as possible. Experimental results show the major superiority of the proposed algorithms over the standard sampling method in terms of the sampling rate.

The idempotent graph of a ring R, denoted by I(R), is a graph whose vertices are all nontrivial idempotents of R and two distinct vertices x and y are adjacent if and only if xy = yx = 0. In this paper we show if D is a division ring, then the clique number of I(M_n(D))(n ≥ 2) is n and for any commutative Artinian ring R the clique number and the chromatic number of I(R) are equal to the number of maximal ideals of R. We prove that for every left Noetherian ring R, the clique number of I(R) is finite. For every finite field F, we also determine an independent set of I(M_n(F)) with maximum size. If F is an infinite field, then we prove that the domination number of I(M_n(F)) is infinite. We show that the idempotent graph of every reduced ring is connected and if n ≥ 3 and D is a division ring, then I(M_n(D)) is connected and moreover diam(I(M_n(D))) ≤ 5.

The global defensive $k$-alliance is a very well-studied notion in graph theory, it provides a method of classification of graphs based on relations between members of a particular set of vertices. In this paper, we explore this notion in zero-divisor graph of commutative rings. The established results generalize and improve recent work by Muthana and Mamouni who treated a particular case for $k=-1$ known by the global defensive alliance. Various examples are also provided which illustrate and delimit the scope of the established results.

In this paper, we develop a fuzzy mathematics approach to study the influence of actors in networks on diffusion. We construct a dynamic diffusion model that represents the interactions and evolution of the current international network and determines the rate of Islamism by the internal and external pressures exerted on each state. We then identify key states in the international system by their degree to test if, and to what extent, they influence the rate and breadth of diffusion. Using this model we determine to what extent the most central actors in a network influence the overall rate of diffusion. We hypothesize that diffusion by the most central actors in the international system will greatly increase the overall rate of diffusion for the remaining actors. Given the current structure of the international system, we hypothesize that the prevalence of Islamism will decrease over time.

Recently, in Borzooei et al. [Inverse fuzzy graphs with applications, to appear in New Mathematics and Natural Computation], we defined the concept of inverse fuzzy graph as a generalization of graph, which is able to answer some problems that graph theory and fuzzy graph theory cannot explain. Now, in this paper, we define the notions of dominating set, domination number and different kinds of dominating sets like strong, weak, total, independent and inverse dominating sets with their domination numbers in inverse fuzzy graphs. Then, we investigate the relations among different kinds of dominating numbers. Finally, we give an application in decision making for service buildings.

Let $G=(V,E)$ be a graph and $u,v\in V.$ A dominating set $D$ is a set of vertices such that each vertex of $G$ is either in $D$ or has at least one neighbor in $D$. The minimum cardinality of such a set is called the domination number of $G$, $\gamma (G).$$u$ strongly dominates $v$ and $v$ weakly dominates $u$ if (i) $uv\in E$ and (ii) $degu\ge degv.$ A set $D\subset V$ is a strong-dominating set, shortly sd-set, (weak-dominating set, shortly wd-set) of $G$ if every vertex in $V-D$ is strongly (weakly) dominated by at least one vertex in $D$. The strong (weak) domination number ${\gamma }_s({\gamma }_w)$ of $G$ is the minimum cardinality of an sd-set (wd-set). In this paper, we present weak and strong domination numbers of thorn graphs.

A graph G is said to be domatically co-critical, if d(G + uv) > d(G), for any two non-adjacent vertices u, v in G. In this paper we present the set of graphs that are not domatically co-critical.

The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater than γ(G), where γ(G) denote the domination number of G. Let G be a toroidal graph with maximum degree Δ(G). In this paper, we show that b(G) ≤ 9. Moveover, if Δ(G) ≠ 6, then b(G) ≤ 8.

A graph G is said to be domatically co-critical, if d(G + uv) > d(G), for any two nonadjacent vertices u, v in G. In this paper, we present few more newly found results and list some more open problems for further research.

Let G be a graph. The gamma graph of G denoted by γ ⋅ G is the graph with vertex set V(γ ⋅ G) as the set of all γ-sets of G and two vertices D and S of γ ⋅ G are adjacent if and only if |D ∩ S| = γ(G) – 1. A graph H is said to be a γ-graph if there exists a graph G such that γ ⋅ G is isomorphic to H. In this paper, we show that every induced subgraph of a γ-graph is also a γ-graph. Furthermore, if we prove that H is a γ-graph, then there exists a sequence {G_n} of non-isomorphic graphs such that H = γ ⋅ G_n for every n.

A star is a graph in which some node is incident with every edge of the graph, i.e., a graph of diameter at most 2. A star forest is a graph in which each connected component is a star. Given a connected graph G in which the edges may be weighted positively. A spanning star forest of G is a subgraph of G which is a star forest spanning the nodes of G. The size of a spanning star forest F of G is defined to be the number of edges of F if G is unweighted and the total weight of all edges of F if G is weighted. We are interested in the problem of finding a Maximum Weight spanning Star Forest (MWSFP) in G. In [C. T. Nguyen, J. Shen, M. Hou, L. Sheng, W. Miller and L. Zhang, Approximating the spanning star forest problem and its applications to genomic sequence alignment, SIAM J. Comput. 38(3) (2008) 946–962], the authors introduced the MWSFP and proved its NP-hardness. They also gave a polynomial time algorithm for the MWSF problem when G is a tree. In this paper, we present a linear time algorithm that solves the MSWF problem when G is a cactus.

This paper discusses a new approach to use a specially constructed social relation graph with high homophily to select a survey respondent group under a limited budget such that the result of the survey is biased to the minority opinions. This approach has a wide range of potential applications, e.g., collecting diversified complaints from the customers while most of them are satisfied, but is hardly investigated. We formulate the problem of computing such a group as the $p$-biased-representative selection problem ($p$-BRSP), where $p$ represents the size of the group constraint by the available budget. This problem has two independent optimization goals and therefore is difficult to deal with. We introduce two polynomial time algorithms for the problem, where each of which has an approximation ratio with respect to each of the objectives when the other optimization objective is substituted with a constraint. Under the substituted constraint, we prove that the first algorithm is an $O(\mathrm{\text{ln}}\mathrm{\Delta })$-approximation (which is best possible) algorithm with respect to the first objective and the second algorithm is a 2-approximation (which is best possible) with respect to the second objective, where $\mathrm{\Delta }$ is the degree of the input social relation graph.

A vertex of a graph $G$ is said to dominate itself and all its neighbors. A double dominating set (DDS) of a graph $G$ is a set $D$ of vertices such that every vertex of $G$ is dominated by at least two vertices of $D$. The double domination number of a graph $G$ is the minimum cardinality of a DDS of $G$. For a graph $G$, a subset $D$ of $V(G)$ is a super dominating set SDS if for every vertex of $V(G)\backslash D$ there exists an external private neighbor of $v$ with respect to $V(G)\backslash D$. The super domination number of $G$ is the minimum cardinality of a SDS of $G$. We prove that for every tree $T$, ${\gamma }_d(T)/2\le {\gamma }_{sp}(T)$, and we characterize the trees attaining this bound.

Let $R$ be a commutative ring and $Z(R)$ be its set of zero divisors. The total graph of $R$ (introduced by Anderson and Badawi) denoted by $T_{\mathrm{\Gamma }}(R)$. For any positive integers $n$ and $m$ we obtain the domination number of the total graph of ${\mathbb{Z}}_n\times {\mathbb{Z}}_m$. We also obtain various domination parameters including ${\gamma }_c,{\gamma }_{cl},{\gamma }_p,{\gamma }_t,{\gamma }_s,{\gamma }_w,{\gamma }_t,i$ and ${\gamma }_{\mathrm{\text{eff}}}$. Finally we explore domination parameters in the complement of the total graph $T_{\mathrm{\Gamma }}(R)$.

Online social relationships which can be extracted from various online resources such as online social networks are getting much attention from the research communities since they are rich resources to learn about the members of our society as well as the relationships among them. With the advances of Internet related technologies, online surveys are established as an essential tool for a wide range of applications. One significant issue of online survey is how to select a quality respondent group so that the survey result is reliable. This paper studies the use of pairwise online social relationships among the members of a society to form a biased survey respondent group, which might be useful for various applications. We first introduce a way to construct a homophily-high social relation graph. Then, we introduce the minimum inverse k-core dominating set problem (MIkCDSP), which aims to compute a biased respondent group using the homophily-high social relation graph. We show the problem is NP-hard and most importantly propose a greedy approximation for it. Our simulation based on a real social network shows the proposed algorithm is very effective.