Narrow Results

The intersection non-simple graph, denoted by $\mathrm{\text{INS}}(G)$, of a finite abelian group $G$ is an undirected graph whose vertex set is the collection of all proper non-trivial subgroups of $G$, and any two distinct vertices are adjacent if and only if their intersection is not a simple subgroup of $G$. We obtain some properties of $\mathrm{\text{INS}}(G)$ related to connectedness, completeness, degree, and girth. The concepts of bipartiteness, triangle-free, cluster, claw-free and cograph are taken into consideration. We also investigate the clique number, independence number, domination number, and planarity of $\mathrm{\text{INS}}(G)$.

Let $G=(V,E)$ be a simple graph. A dominating set of $G$ is a subset $S\subseteq V$ such that every vertex not in $S$ is adjacent to at least one vertex in $S$. The cardinality of a smallest dominating set of $G$, denoted by $\gamma (G)$, is the domination number of $G$. A dominating set $S$ is called a super dominating set of $G$, if for every vertex $u\in \overline{S}=V\setminus S$, there exists $v\in S$ such that $N(v)\cap \overline{S}=\{u\}$. The cardinality of a smallest super dominating set of $G$, denoted by ${\gamma }_{sp}(G)$, is the super domination number of $G$. In this paper, we obtain more results on the super domination number of graphs which is modified by an operation on vertices. Also, we present some sharp bounds for super domination number of chain and bouquet of pairwise disjoint connected graphs.

Generalized hypercube is an interconnection network topology that exhibits excellent performance and symmetry; it facilitates the expansion of capacity and the upgrading of resources to accommodate larger demands; the domination parameters serve as a crucial foundation for the analysis and quantification of the dependability of interconnection networks. In this paper, we explore the structure and properties of generalized hypercube networks to establish the bounds of signed domination numbers and Italian domination numbers. We also present a vertex set partitioning approach to investigate these parameters for some small dimensional generalized hypercube networks and hypercube networks. Furthermore, a Vizing-type conjecture was proposed that satisfies the signed domination number and Italian domination number of generalized hypercube networks.

For a connected graph $G=(V,E)$, a vertex subset $S$ of $G$ is said to be a restrained geodetic dominating set if $S$ is both geodetic and dominating set of $G$ and also, the subgraph induced by $V-S$ consists of no vertex with degree zero. From the study of domination polynomial and geodetic domination polynomial, we have initiated the study on restrained geodetic domination polynomial.

Several factors have to be taken into account in the design of large interconnection networks. Optimal design is important both to achieve good performance and to reduce the cost of construction and maintenance. Practical communication networks are exposed to failures of network components. Failures between nodes and connections happen and it is desirable that a network is robust in the sense that a limited number of failures does not break down the whole system. Robustness of the network topology is a key aspect in the design of computer networks. A variety of measures have been proposed in the literature to quantify the robustness of networks and a number of graph-theoretic parameters have been used to derive formulas for calculating network reliability. In this paper, we study the vulnerability of interconnection networks to the failure of individual nodes, using a graph-theoretic concept of domination and strong-weak domination numbers of the transformation graph G^xy+ as a measure of network robustness.

For a simple, undirected graph $G$, a function $h:V(G)\to \{0,1,2\}$ which satisfies the following conditions is called an outer-independent total Roman dominating function (OITRDF) of $G$ with weight $h(V)={\sum }_{v\in V}h(v)$.

(C1) For all $q\in V$ with $h(q)=0$ there exists a vertex $r$ such that $qr\in E$ and $h(r)=2$,

(C2) The induced subgraph with vertex set $\{p:h(p)\ge 1\}$ has no isolated vertices and

(C3) The induced subgraph with vertex set $\{p:h(p)=0\}$ is independent.

For a graph $G$, the smallest possible weight of an OITRDF of $G$ which is denoted by ${\gamma }_{oitR}(G)$, is known as the outer-independent total Roman domination number of $G$. The problem of determining ${\gamma }_{oitR}(G)$ of a graph $G$ is called minimum outer-independent total Roman domination problem (MOITRDP). In this article, we show that the problem of deciding if $G$ has an OITRDF of weight at most $l$ for bipartite graphs and split graphs, a subclass of chordal graphs is NP-complete. We also show that MOITRDP is linear time solvable for connected threshold graphs and bounded treewidth graphs. Finally, we show that the domination and outer-independent total Roman domination problems are not equivalent in computational complexity aspects.

In several different applications and contexts, networks are essential frameworks and appear.Vulnerability value is a measure of the network’s durability in the face of damage that may lead to a reduction or complete loss of the network’s particular functionality. The domination number and it’s types can be used network vulnerability parameters. Recently, the disjunctive total domination number has been defined by Henning and Naicker. In this paper, the disjunctive total domination numbers of the transformation graph $G^{++z}$ when $z=\{+,-\}$ of some graphs $G$ have been obtained. Furthermore, some new general results have been given for the parameter mentioned above.

Let $G=(V,E)$ be graph. For any function $h:V\to \{0,1,2,3\}$, let $V_i=\{v\in V:h(v)=i\}$, $0\le i\le 3$. The function $h$ is called an outer-independent double Roman dominating function (OIDRDF) if the following conditions are satisfied.

• ⁽ⁱ⁾If $v\in V_0$, then $|N(v)\cap V_3|\ge 1$ or $|N(v)\cap V_2|\ge 2$
• ⁽ⁱⁱ⁾If $v\in V_1$, then $|N(v)\cap (V_2\cup V_3)|\ge 1$
• ⁽ⁱⁱⁱ⁾$V_0$ is independent.

The outer-independent double Roman domination number of $G$ is defined by ${\gamma }_{oidR}(G)=\mathrm{\text{min}}\left\{\right.{\sum }_{v\in V}h(v):h$ is an OIDRDF OF $G\left\}\right.$. We prove that the decision problem MOIDRDP, corresponding to ${\gamma }_{oidR}(G)$ is NP-complete for split graphs. We also show that it is linear time solvable for connected threshold graphs and bounded treewidth graphs. Finally, we show that the MOIDRDP and domination are not equivalent in computational complexity aspects.

The independent number and domination number are two essential parameters to assess the resilience of the interconnection network of multiprocessor systems which is usually modeled by a graph. The independent number, denoted by $\alpha (G)$, of a graph $G(V,E)$ is the maximum cardinality of any subset $S\subset V(G)$ such that no two elements in $S$ are adjacent in $G$. The domination number, denoted by $\gamma (G)$, of a graph $G(V,E)$ is the minimum cardinality of any subset $S\subset V(G)$ such that every vertex in $V(G)$ is either in $S$ or adjacent to an element of $S$. But so far, determining the independent number and domination number of a graph is still an NPC problem. Therefore, it is of utmost importance to determine the number of independent and domination number of some special networks with potential applications in multiprocessor system. In this paper, we firstly resolve the exact values of independent number and upper and lower bound of domination number of the $Q_{n,k,m}$-graph, a common generalization of various popular interconnection networks. Besides, as by-products, we derive the independent number and domination number of $(n,k)$-star graph $S_{n,k}$, $(n,k)$-arrangement graph $A_{n,k}$, as well as three special graphs.

Simplicial complexes are a popular tool used to model higher-order interactions between elements of complex social and biological systems. In this paper, we study some combinatorial aspects of a class of simplicial complexes created by a graph product, which is an extension of the pseudo-fractal scale-free web. We determine explicitly the independence number, the domination number, and the chromatic number. Moreover, we derive closed-form expressions for the number of acyclic orientations, the number of root-connected acyclic orientations, the number of spanning trees, as well as the number of perfect matchings for some particular cases.

For a graph G with n vertices and a permutation α on V(G), a permutation graph P_α(G) is obtained from two identical copies of G by adding an edge between v and α(V) for any v ϵ V(G). Let γ(G) be the domination number of a graph G. It has been shown that γ(G) ≤ γ(P_α(G) ≤ 2γ(G) for any permutation α on V(G). In this paper, we investigate specific graphs for which there exists a permutation α such that γ(P_α(G)) ≻ γ(G) in terms of the domination number of G or the maximum degree of G. Additionally, we construct a class of graphs for which the domination number of any permutation graph is twice the domination number of the original graph, as well as explore finding a specific graph G and permutation α for any two positive integers a and b with a ≤ b ≤ 2a, to have γ(G) = a and γ(P_α(G)) = b.

We associate a graph to a non locally cyclic group G (called the non-cyclic graph of G) as follows: take G\Cyc(G) as vertex set, where Cyc(G) = {x ∈ G | 〈x,y〉 is cyclic for all y ∈ G} is called the cyclicizer of G, and join two vertices if they do not generate a cyclic subgroup. For a simple graph Γ, w(Γ) denotes the clique number of Γ, which is the maximum size (if it exists) of a complete subgraph of Γ. In this paper we characterize groups whose non-cyclic graphs have clique numbers at most 4. We prove that a non-cyclic group G is solvable whenever and the equality for a non-solvable group G holds if and only if G/Cyc(G) ≅ A₅ or S₅.

Let V be a left R-module where R is a (not necessarily commutative) ring with unit. The intersection graph of proper R-submodules of V is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper R-submodules of V, and there is an edge between two distinct vertices U and W if and only if U ∩ W ≠ 0. We study these graphs to relate the combinatorial properties of to the algebraic properties of the R-module V. We study connectedness, domination, finiteness, coloring, and planarity for . For instance, we find the domination number of . We also find the chromatic number of in some cases. Furthermore, we study cycles in , and complete subgraphs in determining the structure of V for which is planar.

Let R be a commutative ring with unity. The cozero-divisor graph of R denoted by Γ'(R) is a graph with the vertex set W*(R), where W*(R) is the set of all nonzero and non-unit elements of R, and two distinct vertices a and b are adjacent if and only if a ∉ Rb and b ∉ Ra, where Rc is the ideal generated by the element c in R. Let α(Γ'(R)) and γ(Γ'(R)) denote the independence number and the domination number of Γ'(R), respectively. In this paper, we prove that if α(Γ'(R)) is finite, then R is Artinian if and only if R is Noetherian. Also, we prove that if α(Γ'(R)) is finite, then R/P is finite, for every prime ideal P. Moreover, we prove that if R is a Noetherian ring, γ(Γ'(R)) is finite and Γ'(R) has at least one isolated vertex, then J(R) = N(R). We show that if R is a commutative Noetherian local ring, γ(Γ'(R)) is finite and Γ'(R) has at least one isolated vertex, then R is a finite ring. Among other results, we prove that if R is a commutative ring and the maximum degree of Γ'(R) is finite and positive, then R is a finite ring.

The present work aims to exploit the interplay between the algebraic properties of rings and the graph-theoretic structures of their associated graphs. Let $R$ be an associative (not necessarily commutative) ring. We focus on the domination number of the zero-divisor graph $\mathrm{\Gamma }(R)$, the compressed zero-divisor graph ${\mathrm{\Gamma }}_E(R)$ and the unit graph $G(R)$. We find some relations between the domination number of the zero-divisor graph and that of the compressed zero-divisor graph. Moreover, some relations between the domination number of $\mathrm{\Gamma }(R)$ and $\mathrm{\Gamma }(R[x;\alpha ,\delta ])$, as well as the relations between the domination number of $G(R)$ and $G(R[[x;\alpha ]])$, are studied.

Let $R$ be a commutative ring with identity. The prime ideal sum graph of $R$, denoted by $\mathrm{\text{PIS}}(R)$, is a graph whose vertices are nonzero proper ideals of $R$ and two distinct vertices $I$ and $J$ are adjacent if and only if $I+J$ is a prime ideal of $R$. In this paper, we study some connections between the graph-theoretic properties of this graph and some algebraic properties of rings. The clique number, the chromatic number and the domination number of the prime ideal sum graph for some classes of rings are studied. It is observed that under which condition $PIS(R)$ is complete. Moreover, the diameter and the girth of $\mathrm{\text{PIS}}(R)$ are studied.

In a recent paper, Grau et al. studied the zero divisor graphs of the ring of Lipschitz integers modulo $n$, and computed the domination number of the undirected zero divisor graph of the ring of Lipschitz integers modulo $n$. But the case $n$ is a power of prime numbers remained open. In this paper, this problem is solved. We also show the automorphism group of the zero divisor graph of the ring of Lipschitz integers modulo $2^s$.

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.

In this paper, we study the Laplacian eigenvalues of graphs on n vertices with domination number γ and present upper bounds for the Laplacian spectral radius and algebraic connectivity as well, which improve old results apparently.

The aim of this paper is to introduce the concept of minimum independent dominating energy of a graph, compute it for some classes of graphs and to study its bounds.