Narrow Results

Communication networks must be constructed to be as stable as possible, not only with the respect to the initial disruption, but also with respect to the possible reconstruction. Many graph theoretical parameters have been used to describe the stability of communication networks. Tenacity is a reasonable one, which shows not only the difficulty to break down the network but also the damage that has been caused. Total graphs are the largest graphs formed by the adjacent relations of elements of a graph. Thus, total graphs are highly recommended for the design of interconnection networks. In this paper, we determine the tenacity of the total graph of a path, cycle and complete bipartite graph, and thus give a lower bound of the tenacity for the total graph of a graph.

A signed graph is an ordered pair $S=(S^u,\sigma )$, where $S^u$ is a graph G = (V, E), called the underlying graph of S and $\sigma :E\to \{+,-\}$ is a function from the edge set E of S^u into the set {+, -}, called the signature of S. In this paper, we characterize all those signed graphs whose 2-path signed graphs are isomorphic to their square signed graph along with algorithm to check the same. In other sections we find the characterization of signed graph S such that $D_2\cong D^2$ where D is a derived signed graph of the signed graph S such as: line signed graphs, total signed graphs, common edge signed graphs, splitting signed graphs. Also each characterization is supported by algorithms for the same.

Let R be a commutative ring with nonzero identity. For an arbitrary multiplicatively closed subset S of R, we associate a simple graph denoted by Γ_S(R) with all elements of R as vertices, and two distinct vertices x, y ∈ R are adjacent if and only if x+y ∈ S. Two well-known graphs of this type are the total graph and the unit graph. In this paper, we study some basic properties of Γ_S(R). Moreover, we will improve and generalize some results for the total and the unit graphs.

Let R be a commutative ring and M be an R-module with a proper submodule N. The total graph of M with respect to N, denoted by T(Γ_N(M)), is investigated. The vertex set of this graph is M and for all x, y belonging to M, x is adjacent to y if and only if x + y ∈ M(N), where M(N) = {m ∈ M : rm ∈ N for some r ∈ R - (N : M)}. In this paper, in addition to studying some algebraic properties of M(N), we investigate some graph theoretic properties of two important subgraphs of T(Γ_N(M)) in the cases depending on whether or not M(N) is a submodule of M.

Let R be a commutative ring with nonzero identity, and let Z(R) be its set of zero-divisors. The total graph of R is the (undirected) graph T(Γ(R)) with vertices all elements of R, and two distinct vertices x and y are adjacent if and only if x + y ∈ Z(R). In this paper, we study the two (induced) subgraphs Z₀(Γ(R)) and T₀(Γ(R)) of T(Γ(R)), with vertices Z(R)\{0} and R\{0}, respectively. We determine when Z₀(Γ(R)) and T₀(Γ(R)) are connected and compute their diameter and girth. We also investigate zero-divisor paths and regular paths in T₀(Γ(R)).

Let R be a commutative ring and Z(R) be its set of all zero-divisors. Anderson and Badawi [The total graph of a commutative ring, J. Algebra320 (2008) 2706–2719] introduced the total graph of R, denoted by T_Γ(R), as the undirected graph with vertex set R, and two distinct vertices x and y are adjacent if and only if x + y ∈ Z(R). Tamizh Chelvam and Asir [Domination in the total graph of a commutative ring, to appear in J. Combin. Math. Combin. Comput.] obtained the domination number of the total graph and studied certain other domination parameters of T_Γ(R) where R is a commutative Artin ring. The intersection graph of gamma sets in T_Γ(R) is denoted by I_TΓ(R). Tamizh Chelvam and Asir [Intersection graph of gamma sets in the total graph, Discuss. Math. Graph Theory32 (2012) 339–354, doi:10.7151/dmgt.1611] initiated a study about the intersection graph I_TΓ (ℤ_n) of gamma sets in T_Γ(ℤ_n). In this paper, we study about I_TΓ(R), where R is a commutative Artin ring. Actually we investigate the interplay between graph-theoretic properties of I_TΓ(R) and ring-theoretic properties of R. At the first instance, we prove that diam(I_TΓ(R)) ≤ 2 and gr(I_TΓ(R)) ≤ 4. Also some characterization results regarding completeness, bipartite, cycle and chordal nature of I_TΓ(R) are given. Further, we discuss about the vertex-transitive property of I_TΓ(R). At last, we obtain all commutative Artin rings R for which I_TΓ(R) is either planar or toroidal or genus two.

The intersection graph I_TΓ(R) of gamma sets in the total graph T_Γ(R) of a commutative ring R, is the undirected graph with vertex set as the collection of all γ-sets in the total graph of R and two distinct vertices u and v are adjacent if and only if u ∩ v ≠ ∅. Tamizh Chelvam and Asir [The intersection graph of gamma sets in the total graph I, to appear in J. Algebra Appl.] studied about I_TΓ(R) where R is a commutative Artin ring. In this paper, we continue our interest on I_TΓ(R) and actually we study about Eulerian, Hamiltonian and pancyclic nature of I_TΓ(R). Further, we focus on certain graph theoretic parameters of I_TΓ(R) like the independence number, the clique number and the connectivity of I_TΓ(R). Also, we obtain both vertex and edge chromatic numbers of I_TΓ(R). In fact, it is proved that if R is a finite commutative ring, then χ(I_TΓ(R)) = ω(I_TΓ(R)). Having proved that I_TΓ(R) is weakly perfect for all finite commutative rings, we further characterize all finite commutative rings for which I_TΓ(R) is perfect. In this sequel, we characterize all commutative Artin rings for which I_TΓ(R) is of class one (i.e. χ′(I_TΓ(R)) = Δ(I_TΓ(R))). Finally, it is proved that the vertex connectivity and edge connectivity of I_TΓ(R) are equal to the degree of any vertex in I_TΓ(R).

Let R be a commutative ring with nonzero identity and H be a nonempty proper subset of R such that R\H is a saturated multiplicatively closed subset of R. The generalized total graph of R is the (simple) graph GT_H(R) with all elements of R as the vertices, and two distinct vertices x and y are adjacent if and only if x + y ∈ H. In this paper, we investigate the structure of GT_H(R).

Let $H$ be a subset of a commutative graded ring $R$. The Cayley graph $\mathrm{\text{Cay}}(R,H)$ is a graph whose vertex set is $R$ and two vertices $a$ and $b$ are adjacent if and only if $a-b\in H$. The Cayley sum graph ${\mathrm{\text{Cay}}}^{+}(R,H)$ is a graph whose vertex set is $R$ and two vertices $a$ and $b$ are adjacent if and only if $a+b\in H$. Let $S$ be the set of homogeneous elements and $\mathrm{\text{Z}}(R)$ be the set of zero-divisors of $R$. In this paper, we study ${\mathrm{\text{Cay}}}^{+}(R,\mathrm{\text{Z}}(R))$ (total graph) and $\mathrm{\text{Cay}}(R,S)$. In particular, if $R$ is an Artinian graded ring, we show that $\mathrm{\text{Cay}}(R,S)$ is isomorphic to a Hamming graph and conversely any Hamming graph is isomorphic to a subgraph of $\mathrm{\text{Cay}}(R,S)$ for some finite graded ring $R$.

In this paper, we introduce the entire graph of a module with respect to a submodule, as a generalization of the total graph of a commutative ring in the sense of Anderson–Badawi. Let $M$ be an $R$-module over a commutative ring $R$, $N$ a submodule of $M$ and $M(N)$ the set of all elements $m\in M$ such that ${(Rm{:}_{R}M)}^{k}Rm\subseteq N$. The entire graph of $M$ with respect to $N$ denoted by $E{G}_N(M)$ whose vertices are all elements of $M$ and two distinct elements $m,m^{\prime }\in M$ are adjacent if and only if $m+m^{\prime }\in M(N)$. Also, we study two (induced) subgraphs $E{G}_N(M(N))$ and $E{G}_N(M\backslash M(N))$ of $E{G}_N(M)$, with vertices $M(N)$ and $M\backslash M(N)$, respectively.

In this paper, we initiate the study of the total zero-divisor graph over a commutative ring with unity. This graph is constructed by both relations that arise from the zero-divisor graph and from the total graph of a ring and give a joint insight of the structure of zero-divisors in a ring. We characterize Artinian rings with the connected total zero-divisor graphs and give their diameters. Moreover, we compute major characteristics of the total zero-divisor graph of the ring ${\mathbb{Z}}_m$ of integers modulo $m$ and prove that the total zero-divisor graphs of ${\mathbb{Z}}_m$ and ${\mathbb{Z}}_n$ are isomorphic if and only if $m=n$.

Let $F$ be a finite field, $R=T_n(F)$ the ring of all $n\times n$ upper triangular matrices over $F$, $Z(R)$ the set of all zero-divisors of $R$, i.e. $Z(R)$ consists of all $n\times n$ upper triangular singular matrices over $F$. The total graph of $R=T_n(F)$, denoted by ${𝒯}(\mathrm{\Gamma }(R))$, is a graph with all elements of $R$ as vertices, and two distinct vertices $x,y\in R$ are adjacent if and only if $x+y\in Z(R)$. In this paper, we determine all automorphisms of the total graph ${𝒯}(\mathrm{\Gamma }(R))$ of $R=T_n(F)$.

For a given finite commutative ring $R$ with $1\ne 0$, one may associate a graph which is called the total graph of $R$. This graph has $R$ as the vertex set and its two distinct vertices $x$ and $y$ are adjacent exactly whenever $x+y$ is a zero-divisor of $R$. In this paper, we give necessary and sufficient conditions for two classes of total graphs to be Cohen–Macaulay.

We prove that the Laplacian matrix of the total graph of a finite commutative ring with identity has integer eigenvalues and present a recursive formula for computing its eigenvalues and eigenvectors. We also prove that the total graph of a finite commutative local ring with identity is super integral and give an example showing that this is not true for arbitrary rings.

Let $L$ be a lattice, $I$ an ideal of $L$ and $T(I)$ the set of all elements of $L$ which are not prime to $I$. In this paper, we investigate some interesting properties of $T(I)$ and introduce the total graph of a lattice $L$ with respect to an ideal $I$. It is the graph with all elements of $L$ as vertices and for distinct $a,b\in L$, the vertices $a$ and $b$ are adjacent if and only if $a\vee b\in T(I)$. We investigated the basic properties of this graph and its induced subgraphs as diameter, girth, clique number, cut vertex and independence number.

For a commutative ring R, let Z(R) be its set of zero-divisors. The total graph of R, denoted by T_Γ(R), is the undirected graph with vertex set R, and for distinct x, y ∈ R, the vertices x and y are adjacent if and only if x + y ∈ Z(R). Tamizh Chelvam and Asir studied about the domination in the total graph of a commutative ring R. In particular, it was proved that the domination number γ(T_Γ(ℤ_n)) = p₁ where p₁ is the smallest prime divisor of n. In this paper, we characterize all the γ-sets in T_Γ(ℤ_n). Also, we obtain the values of other domination parameters like independent, total and perfect domination numbers of the total graph on ℤ_n.

Let R be a commutative ring. The total graph of R, denoted by T(Γ(R)), is a graph with all elements of R as vertices, and two distinct vertices x, y ∈ R are adjacent if and only if x + y ∈ Z(R), where Z(R) denotes the set of zero-divisors of R. In this paper, we examine the preservation of the diameter, girth and completeness of T(Γ(R)) under extension to polynomial rings and rings of fractions. We also study the chromatic index, clique number and independence number of T(Γ(R)).

Let R be a commutative ring and Z(R) be the set of all zero-divisors of R. The total graph of R, denoted by T_Γ(R), is the (undirected) graph with vertices set R. For any two distinct elements x, y ∈ R, the vertices x and y are adjacent if and only if x + y ∈ Z(R). In this paper, we obtain certain fundamental properties of the total graph of ℤ_n × ℤ_m, where n and m are positive integers. We determine the clique number and independent number of the total graph T_Γ(ℤ_n × ℤ_m).

Motivated by the earlier study on the notion of signed total graph of a commutative ring, in this paper, we characterize all the commutative rings with unity for which signed total graph is ${𝒞}$-consistent and sign-compatible. To do this, first, we derive a formula to determine the degree of each vertex in $\mathrm{\text{Reg}}(\mathrm{\Gamma }(R))$ (induced subgraph of the total graph), when $R\cong {𝔽}_{p^r}\times {\prod }_{i=1}^t{𝔽}_i$ and $R\cong {\prod }_{i=1}^t{𝔽}_i$, where each ${𝔽}_i$’s is a field of characteristic $2$, $p$ is an odd prime, $r\ge 1$ and $t\ge 2$.

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)$.