Search

For a commutative ring R with unity, the associate ring graph, denoted by A G (R) , is a simple graph with vertices as nonzero elements of R and two distinct vertices are adjacent if they are associates. The graph A G (R) contains components equal in number to the number of distinct orbits, except for the orbit of an element 0. Moreover, each component is a complete graph. An important finding is that this is a class of strongly perfect graphs. In this article we describe the structure of the associate ring graph of the ring of integers modulo n, denoted by A G (Z n) . We carried out computer experiments and provide a program for the same. We further characterize cases in which A G (Z n) , its complement A G (Z n) ¯ , and their line graphs are planar, ring graphs, and outerplanar. We also discuss the properties of the associate ring graph of a commutative ring R with unity. [ABSTRACT FROM AUTHOR]

Let L be a lattice, 𝒥(L) be the set of ideals of L and S be a subset of 𝒥 (L). In this paper, we introduce an undirected Cayley graph of L, denoted by ΓL,S with elements of 𝒥 (L) as the vertex set and, for two distinct vertices I and J, I is adjacent to J if and only if there is an element K of S such that I ∨ K = J or J ∨ K = I. We study some basic properties of the graph ΓL,S such as connectivity, girth and clique number. Moreover, we investigate the planarity, outerplanarity and ring graph of ΓL,S.

Let S be a regular semigroup, J(S) be the set of ideals of S and M be a subset of J(S). In this paper, we introduce an undirected Cayley graph of S, denoted by ΓS,M, with elements of J(S) as the vertex set, and, for two distinct vertices I and J, I is adjacent to J if and only if there is an element K of M such that IK = J or JK = I. We study some basic properties of the graph ΓS,M such as connectivity, girth and clique number. Moreover, we investigate the planarity, outerplanarity and ring graph of ΓS,M. [ABSTRACT FROM AUTHOR]

Given a graph H, a path of length at least two is called an H-path if meets H exactly in its ends. A graph G is a ring graph if each block of G which is not a bridge or a vertex can be constructed inductively by starting from a single cycle and then in each step adding an H-path that meets graph H in the previous step in two adjacent vertices. In this article, we classify all graphs whose line graphs and total graphs are ring graphs.

Let R be a commutative ring with non-zero identity. For a natural number n, we associate a directed graph, denoted byPnR,with Rn\ {0}as the vertex set and, for two distinct verticesX = (x1, x2, . . . , xn) and Y = (y1, y2, . . . , yn),we have an arc X → Y in PnRif and only if there exists an n × n lower triangular matrix A =(aij ) over R such that AXT = Y Tand det (A) ϵ [x1, x2, . . . , x2], where [x1, x2, . . . , xn] is a subsemigroup generated by the elements x1, x2, . . . , xn in the multiplicative semigroup R. When we consider the ring R as a semigroup with respect to multiplication, the graph P1R is the usual directed power graph (over a semigroup). Hence PnR is a gener- alization of power graphs. In this paper we study some basic properties of PnR. Also we study the planarity, outer planarity and ring graph of PnR and we determine the cases for which the graph PnR has thickness 2. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with nonzero identity. In this paper we intro- duce the coannihilator graph of R, which is a dual of the annihilator graph AG(R), denoted by AG'(R). AG'(R) is a graph with the vertex set W*(R), where W*(R) is the set of all nonzero and nonunit elements of R, and two distinct vertices x and y are adjacent if and only if x ∉ xyR or y ∉ xyR, where for z ∊ R, zR is the principal ideal generated by z. We study the interplay between the ring-theoretic properties of R and graph-theoretic properties of AG'(R). Also we completely determine all finite commutative rings R such that AG'(R) is planar, outerplanar or ring graph. Among other things, we prove that AG'(R) has a cut vertex if and only if R is isomorphic to Z∊2 × K, where K is a field. Also, we examine the domination number of AG'(R). [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with nonzero identity. Let Γ(R) denote the maximal graph associated to R, that is, Γ(R) is a graph with vertices as non-units of R, where two distinct vertices a and b are adjacent if and only if there is a maximal ideal of R containing both. In this paper, we characterize the finite commutative rings such that their maximal graph are planar graphs, and we also study the case where they are outerplanar and ring graphs. The equivalence of outerplanar graphs and ring graphs for Γ(R) is established. [ABSTRACT FROM AUTHOR]

The graph exploration problem requires a group of mobile robots, initially placed arbitrarily on the nodes of a graph, to work collaboratively to explore the graph such that each node is eventually visited by at least one robot. One important requirement of exploration is the termination condition, i.e., the robots must know that exploration is completed. The problem of live exploration of a dynamic ring using mobile robots was recently introduced by Di Luna et al. [DC 2020]. More specifically, they studied the problem of live exploration in a dynamic ring and proposed multiple algorithms to solve this problem in the fully synchronous and semi-synchronous settings with various guarantees when 2 robots were involved. They also showed that, under certain assumptions, exploration of the ring using two robots was impossible. An important question left open was how the presence of 3 robots would affect the results. In this paper, we try to settle this question in a fully synchronous setting and also show how to extend our results to a semi-synchronous setting. In particular, we present algorithms for exploration with explicit termination using 3 robots in conjunction with either (i) unique IDs of the robots and edge crossing detection capability (i.e., two robots moving in opposite directions through an edge in the same round can detect each other), or (ii) access to randomness. The time complexity of our deterministic algorithm is asymptotically optimal. We also provide complementary impossibility results showing that there does not exist any explicit termination algorithm for 2 robots even when each robot has a unique ID, edge crossing detection capability, and access to randomness. The theoretical analysis and comprehensive simulations of our algorithm show the effectiveness and efficiency of the algorithm in dynamic rings. We also present an algorithm to achieve exploration with partial termination using 3 robots with unique IDs in the semi-synchronous setting, when robots have access to edge crossing detection capability and randomness but do not know a bound on the size of the ring or have access to a landmark or are guaranteed that robots have common chirality. Our algorithms are fully decentralized, lightweight, and easily implementable. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with nonzero identity and I be a proper ideal of R. The annihilator graph of R with respect to I, which is denoted by AGI (R), is the undirected graph with vertex-set V (AGI (R)) = {x ∈ R \ I: xy ∈ I for some y ∉ I} and two distinct vertices x and y are adjacent if and only if AI (xy) ≠ = AI (x) ∪ AI (y), where AI (x) = {r ∈ R : rx ∈ I}. In this paper, we study some basic properties of AGI (R), and we characterise when AGI (R) is planar, outerplanar or a ring graph. Also, we study the graph AGI (Zn), where Zn is the ring of integers modulo n. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with nonzero identity. The cozero-divisor graph of R, denoted by Γ′(R), is a graph with vertex-set W*(R), which is the set of all nonzero and non-unit elements of R, and two distinct vertices a and b in W*(R) are adjacent if and only if a ∉ Rb and b ∉ Ra. In this paper, we characterize all finite commutative rings R such that Γ′(R) is planar, outerplanar or ring graph. [ABSTRACT FROM AUTHOR]

Abstract: We study the family of graphs whose number of primitive cycles equals its cycle rank. It is shown that this family is precisely the family of ring graphs. Then we study the complete intersection property of toric ideals of bipartite graphs and oriented graphs. An interesting application is that complete intersection toric ideals of bipartite graphs correspond to ring graphs and that these ideals are minimally generated by Gröbner bases. We prove that any graph can be oriented such that its toric ideal is a complete intersection with a universal Gröbner basis determined by the cycles. It turns out that bipartite ring graphs are exactly the bipartite graphs that have complete intersection toric ideals for any orientation. [Copyright &y& Elsevier]

Abstract: We study the family of simple graphs whose number of primitive cycles equals its cycle rank. Then we study toric ideals of simple and oriented graphs. [Copyright &y& Elsevier]