Narrow Results

In this paper, we introduce the unit-Jacobson graph, which is defined by the unit elements and the elements of the Jacobson radical of a commutative ring $R$ with nonzero identity. We give relationships between this new graph concept and some special rings such as $j$-clean rings, $UJ$-rings, local rings, and cartesian rings. Moreover, we investigate the concepts of the dominating set, diameter, and girth on the unit-Jacobson graph.

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

Graph properties’ computation is widely used in science. Some algorithms for specific graphs help us compute properties like girth, clique number, and independent number. Nevertheless, processing time would be increased by the growth of the number of graph vertices. This paper suggests machine learning methods for computing a given graph’s girth, maximum clique number, and maximum independent set number. We leveraged random graph generation methods to collect many graph instances. Next, we present 14 features used for the training and testing while classifying or predicting those properties. The experimental results on the collected dataset offer accuracies of 90.51%, 91.61%, and 99.99% for binary classification and correlation coefficients of 0.9703, 0.8757, and 0.992 for value prediction for maximum clique number, girth, and maximum independent set number, respectively.

Recently, Low Density Parity-Check (LDPC) codes based on Affine Permutation Matrices (APM) drew lots of attention. Compared with the Quasi-Cyclic LDPC (QC-LDPC) codes, these kinds of codes have some advantages. APM-LDPC codes obtain lower cycle-distributions, minimum hamming distance and greater girth. This paper explains the importance of cyclic distribution by comparing APM-LDPC codes with QC-LDPC codes. Then a particular form of APM-LDPC codes is proposed and researched. The new codes can low down the cycle-distribution to larger extent. In the following research, an effective method, which constructs the new codes with fixed girth, is proposed. Simulations show that the construction method is reasonable and effective. The transmission performances are better than the traditional methods, as well. Finally, the implementation and verification are carried out on FPGA.

A knot diagram can be divided by a circle into two parts, such that each part can be coded by a planar tree with integer weights on its edges. A half of the number of intersection points of this circle with the knot diagram is called the girth. The girth of a knot is the minimal girth of all diagrams of this knot. The girth of a knot minus one is an upper bound of the Heegaard genus of the 2-fold branched covering of that knot. We will use Topological Quantum Field Theory (TQFT) coming from the Kauffman bracket to determine the girth of some knots. Consequently, our method can be used to determine the Heegaard genus of the 2-fold branched covering of some knots.

This paper bounds the computational cost of computing the Kauffman bracket of a link in terms of the crossing number of that link. Specifically, it is shown that the image of a tangle with g boundary points and n crossings in the Kauffman bracket skein module is a linear combination of O(2^g) basis elements, with each coefficient a polynomial with at most n non-zero terms, each with integer coefficients, and that the link can be built one crossing at a time as a sequence of tangles with maximum number of boundary points bounded by for some C. From this it follows that the computation of the Kauffman bracket of the link takes time and memory a polynomial in n times .

We compute the mixing rate of a non-backtracking random walk on a regular expander. Using some properties of Chebyshev polynomials of the second kind, we show that this rate may be up to twice as fast as the mixing rate of the simple random walk. The closer the expander is to a Ramanujan graph, the higher the ratio between the above two mixing rates is.

As an application, we show that if G is a high-girth regular expander on n vertices, then a typical non-backtracking random walk of length n on G does not visit a vertex more than times, and this result is tight. In this sense, the multi-set of visited vertices is analogous to the result of throwing n balls to n bins uniformly, in contrast to the simple random walk on G, which almost surely visits some vertex Ω(log n) times.

The Kautz digraphs K(d, ℓ) are a well-known family of dense digraphs, widely studied as a good model for interconnection networks. Closely related to these, the cyclic Kautz digraphs CK(d, ℓ) were recently introduced by Böhmová, Huemer and the author, and some of its distance-related parameters were fixed. In this paper we propose a new approach to the cyclic Kautz digraphs by introducing the family of the subKautz digraphs sK(d, ℓ), from where the cyclic Kautz digraphs can be obtained as line digraphs. This allows us to give exact formulas for the distance between any two vertices of both sK(d, ℓ) and CK(d, ℓ). Moreover, we compute the diameter and the semigirth of both families, also providing efficient routing algorithms to find the shortest path between any pair of vertices. Using these parameters, we also prove that sK(d, ℓ) and CK(d, ℓ) are maximally vertex-connected and super-edge-connected. Whereas K(d, ℓ) are optimal with respect to the diameter, we show that sK(d, ℓ) and CK(d, ℓ) are optimal with respect to the mean distance, whose exact values are given for both families when ℓ = 3. Finally, we provide a lower bound on the girth of CK(d, ℓ) and sK(d, ℓ).

For a given graph $G=(V,E)$, by $\tau (G)$ and $\omega (G)$ denote the order of the largest component and the number of connected components of $G$, respectively. The rupture degree of $G$ is an important combinatorial parameters, which defined as $r(G)=max\{\omega (G-X)-|X|-\tau (G-X):X\subset V(G),\omega (G-X)>1\}$. Clearly, the smaller the value $r(G)$ is, the better the connectivity of graph $G$ is. In this paper, the tree structures with minimum rupture degree be discussed, and the extremal graphs on the rupture degree in terms of graph girth are also characterized.

Let R be an associative ring with two-sided multiplicative identity. In this paper, in the case that R is a commutative α-compatible ring, we compare the diameter (and girth) of the zero-divisor graphs Γ(R) and Γ(R[x;α, δ]). Moreover, we study the zero-divisors of the Öre extension ring R[x;α, δ], whenever R is reversible and (α, δ)-compatible.

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 with nonzero identity. Then the Jacobson graph of R, denoted by 𝔍_R, is defined as a graph with vertex set R\J(R) such that two distinct vertices x and y are adjacent if and only if 1 - xy is not a unit of R. We obtain some graph theoretical properties of 𝔍_R including its connectivity, planarity and perfectness and we compute some of its numerical invariants, namely diameter, girth, dominating number, independence number and vertex chromatic number and give an estimate for its edge chromatic number.

Let G be a finite group and H be a subgroup of G. We introduce the non-normal graph of H in G, denoted by _H,G, and give some of the graph theoretical properties of _H,G.

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

The unit graph of a ring R, denoted G(R), is the simple graph defined on the elements of R with an edge between vertices x and y iff x + y is a unit of R. In this paper, we prove that the girth gr(G(R)) of the unit graph of an arbitrary ring R is 3, 4, 6 or ∞. We determine the rings R with R/J(R) semipotent and with gr(G(R)) = 6 or ∞, and classify the rings R with R/J(R) right self-injective and with gr(G(R)) = 3 or 4.

In this paper, we extend the concept of the cozero-divisor graph to any arbitrary ring with nonzero identity. Also we study some basic properties of this graph and gain some results on the cozero-divisor graphs of matrix rings.

Let R be a commutative ring with identity, I its proper ideal and M be a unitary R-module. In this paper, we introduce and study a kind of graph structure of an R-module M with respect to proper ideal I, denoted by Γ_I(_RM) or simply Γ_I(M). It is the (undirected) graph with the vertex set M\{0} and two distinct vertices x and y are adjacent if and only if [x : M][y : M] ⊆ I. Clearly, the zero-divisor graph of R is a subgraph of Γ₀(R); this is an important result on the definition. We prove that if ann_R(M) ⊆ I and H is the subgraph of Γ_I(M) induced by the set of all non-isolated vertices, then diam(H) ≤ 3 and gr(Γ_I(M)) ∈ {3, 4, ∞}. Also, we prove that if Spec(R) and ω(Γ_Nil(R)(M)) are finite, then χ(Γ_Nil(R)(M)) ≤ ∣Spec(R)∣ + ω(Γ_Nil(R)(M)). Moreover, for a secondary R-module M and prime ideal P, we determine the chromatic number and the clique number of Γ_P(M), where ann_R(M) ⊆ P. Among other results, it is proved that for a semisimple R-module M with ann_R(M) ⊆ I, Γ_I(M) is a forest if and only if Γ_I(M) is a union of isolated vertices or a star.

In this paper, we continue to study zero-divisor properties of skew polynomial rings $R[x;\alpha ,\delta ]$, where $R$ is an associative ring equipped with an endomorphism $\alpha$ and an $\alpha$-derivation $\delta$. For an associative ring $R$, the undirected zero-divisor graph of $R$ is the graph $\mathrm{\Gamma }(R)$ such that the vertices of $\mathrm{\Gamma }(R)$ are all the nonzero zero-divisors of $R$ and two distinct vertices $x$ and $y$ are connected by an edge if and only if $xy=0$ or $yx=0$. As an application of reversible rings, we investigate the interplay between the ring-theoretical properties of a skew polynomial ring $R[x;\alpha ,\delta ]$ and the graph-theoretical properties of its zero-divisor graph $\mathrm{\Gamma }(R[x;\alpha ,\delta ])$. Our goal in this paper is to give a characterization of the possible diameters of $(\mathrm{\Gamma }(R[x;\alpha ,\delta ]))$ in terms of the diameter of $\mathrm{\Gamma }(R)$, when the base ring $R$ is reversible and also have the $(\alpha ,\delta )$-compatible property. We also completely describe the associative rings all of whose zero-divisor graphs of skew polynomials are complete.

The zero-divisor graphs of modules introduced and studied in [S. Safaeeyan, M. Baziar and E. Momtahan, A generalization of the zero-divisor graph for modules, J. Korean Math. Soc. 51(1) (2014) 87–98]. Basic results for zero-divisor graphs of $\mathbb{Z}$-modules were obtained in [M. Baziar, E. Momtahan and S. Safaeeyan, Zero-divisor graph of abelian groups, J. Algebra Appl.13(6) (2014) 13]. In this paper, zero-divisor graphs in the title are studied. Here, among other things, we generalize results stated in [M. Baziar, E. Momtahan and S. Safaeeyan, Zero-divisor graph of abelian groups, J. Algebra Appl.13(6) (2014) 13]. Some results for modules over non-integral domains are also obtained.

In this paper, we study the zero-divisor graph $\mathrm{\Gamma }(P)$ of a poset $P$ and its line graph $L(\mathrm{\Gamma }(P))$. We characterize all posets whose $\mathrm{\Gamma }(P)$ are star, finite complete bipartite or finite. Also, we prove that the diameter of $L(\mathrm{\Gamma }(P))$ is at most 3 while its girth is either 3, 4 or $\infty$. We also characterize $L(\mathrm{\Gamma }(P))$ in terms of their diameter and girth. Finally, we classify all posets $P$ whose $L(\mathrm{\Gamma }(P))$ are planar.