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.

Let $K_n$ denote a complete graph on $n$ vertices and $S_k$ denote a complete bipartite graph $K_{1,k}$. A Bowtie $B_l$ is a graph formed by the union of two cycles $C_n$ and $C_m$ intersecting at a common vertex. A decomposition of a graph $G$ is a collection of edge-disjoint subgraphs $H$, such that every edge of G belongs to exactly one $H$. Given non-isomorphic subgraphs $H_1$ and $H_2$ of $G$, a $(H_1,H_2)$ — multi-decomposition of $G$ is the decomposition of $G$ into $a$ copies of $H_1$ and $b$ copies of $H_2$, such that $a{H}_1\oplus b{H}_2=G$, for some integers $a,b\ge 0$. In this paper, the multi-decomposition of $K_n$ into $S_k$ and $B_l$ has been investigated and obtained a necessary and sufficient condition when $k=l=6$. It is proved that for a given positive integer $n$, $K_n$ can be decomposed into $a$ copies of $S_6$ and $b$ copies of $B_6$ for some pair of non-negative integers $(a,b)$ if and only if $6(a+b)=\left(\genfrac{}{}{0.0pt}{}{n}{2}\right)$, for all $n\ge 9$.

Let $\mathrm{\Sigma }=(G,\sigma )$ be a signed graph with a vertex set $V(G)$. A set $D\subseteq V(G)$ is said to be a double dominating set of $\mathrm{\Sigma }$ if it satisfies the following conditions: (i) $|N[v]\cap D|\ge 2$ for each $v\in V(G)$, and (ii) $\mathrm{\Sigma }[D,D^c]$ is balanced, where $N[v]$ denotes the closed neighborhood of $v$ and $\mathrm{\Sigma }[D,D^c]$ denotes the subgraph induced by the edges of $\mathrm{\Sigma }$ with one end vertex in $D$ and the other end vertex in $D^c$. The minimum size among all the double dominating sets of $\mathrm{\Sigma }$ is the double domination number ${\gamma }_{\times 2}(\mathrm{\Sigma })$ of $\mathrm{\Sigma }$. In this study, we investigated this parameter for signed complete graphs. We prove that, for $n\ge 5$, if $(K_n,\sigma )$ is a signed complete graph, then $2\le {\gamma }_{\times 2}(K_n,\sigma )\le n-1$ and these bounds are sharp. Moreover, for all signed complete graphs over $K_n$ we determined their possible double domination numbers. Finally, we compute the double domination numbers of all signed complete graphs of orders up to six.

A graph G is said to be super edge connected (in short super – λ) if every minimum edge cut isolates a vertex of G. The Kronecker product of graphs G and H is the graph with vertex set V(G × H) = V(G) × V(H), where two vertices (u1, v1) and (u2, v2) are adjacent in G × H if u1u2 ∈ E(G) and v1v2 ∈ E(H). Let G be a connected graph, and let δ(G) and λ(G) be the minimum degree and the edge-connectivity of G, respectively. In this paper we prove that G × K_n is super-λ for n ≥ 3, if λ(G) = δ(G) and G ≇ K₂. Furthermore, we show that K₂ × K_n is super-λ when n ≥ 4. Similar results for G × T_n are also obtained, where T_n is the graph obtained from K_n by adding a loop to every vertex of K_n.

The conditional fractional matching preclusion number (CFMP number for short) $fm{p}_1(G)$ of a graph $G$ is the minimum number of edges whose deletion results in a graph without isolated vertices and without fractional perfect matchings. In this paper, we study the CFMP number of complete graphs, complete bipartite graphs and twisted cubes. Also, we give Nordhaus–Gaddum-type results for the CFMP numbers of general graphs.

Let k be a non-negative integer. Then any embedding of the complete graph on 6·2^k vertices into a three-space contains a two-component link with the absolute value of its linking number greater than or equal to 2^k. Let j be a non-negative integer. Then any embedding of the complete graph on 48·2^j vertices into a three-space contains a knot with the absolute value of the second coefficient of its Conway polynomial greater than or equal to 2^2j.

In 1983 Conway and Gordon and Sachs proved that every embedding of the complete graph on six vertices, K₆, is intrinsically linked. In 2004 it was shown that all straight-edge embeddings of K₆ have either one or three linked triangle pairs. We expand this work to characterize the straight-edge embeddings of K₇ and determine the number and types of links in every embedding which forms a convex polyhedron of seven vertices.

An oriented and ordered n-component link L in the 3-sphere is said to be achiral if it is ambient isotopic to its mirror image ignoring orientations and ordering of the components. For an oriented and ordered n-component link L, let λ_L be the product of linking numbers of all 2-component sublinks in L. For n = 4m + 3, where m is a non-negative integer, we show that if L is achiral then λ_L = 0. And for n ≠ 4m + 3, we show that there exists an n-component achiral link L with λ_L ≠ 0 by using achiral embeddings of complete graphs with n vertices K_n.

In 1983 Conway and Gordon proved that any embedding of the complete graph K₇ into ℝ³ contains at least one nontrivial knot as its Hamiltonian cycle. After their work knots (also links) are considered as intrinsic properties of abstract graphs, and numerous subsequent works have been continued until recently. In this paper, we are interested in knotted Hamiltonian cycles in linear embedding of K₇. Concretely it is shown that any linear embedding of K₇ contains at most three figure-8 knots.

In this paper, it is shown that a complete graph with $n$ vertices has an optimal diagram, i.e. a diagram whose crossing number equals the value of Guy’s formula, with a free maximal linear tree and without free Hamiltonian cycles for any odd integer $n\ge 7$.

Broadcasting is disseminating information in a network where a specific message must spread to all network vertices as quickly as possible. Finding the minimum broadcast time of a vertex in an arbitrary network is proven to be NP-complete. However, this problem is solvable for a few families of networks. In this paper, we present an optimal algorithm for finding the broadcast time of any vertex in a fully connected tree (${\mathrm{\text{FCT}}}_n$) in $O(|V|loglogn)$ time. An ${\mathrm{\text{FCT}}}_n$ is formed by attaching arbitrary trees to vertices of a complete graph of size $n$ where $\left|V\right|$ is the total number of vertices in the graph.

The $\{K_{1,1},K_{1,2},\dots ,K_{1,k},{𝒯}(2k+1)\}$-factor and $\{K_{1,2},K_{1,3},K_5\}$-factor of a graph are a spanning subgraph whose each component is an element of $\{K_{1,1},K_{1,2},\dots ,K_{1,k},{𝒯}(2k+1)\}$ and $\{K_{1,2},K_{1,3},K_5\}$, respectively, where ${𝒯}(2k+1)$ is a special family of trees. In this paper, we obtain a sufficient condition in terms of tight toughness, isolated toughness and binding number bounds to guarantee the existence of a $\{K_{1,1},K_{1,2},\dots ,K_{1,k},{𝒯}(2k+1)\}$-factor and $\{K_{1,2},K_{1,3},K_5\}$-factor for any graph.

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 ring with identity. The unit graph of R, denoted by G(R), is a simple graph with vertex set R, and where two distinct vertices x and y are adjacent if and only if x + y is a unit in R. The genus of a simple graph G is the smallest nonnegative integer g such that G can be embedded into an orientable surface S_g. In this paper, we determine all isomorphism classes of finite commutative rings whose unit graphs have genus at most three.

Let $R$ be a commutative ring with identity, and let $Z(R)$ be the set of zero-divisors of $R$. The essential graph of $R$ is defined as the graph $EG(R)$ with the vertex set $Z{(R)}^{*}=Z(R)\setminus \{0\}$, and two distinct vertices $x$ and $y$ are adjacent if and only if ann${}_R(xy)$ is an essential ideal. It is proved that $EG(R)$ is connected with diameter at most three and with girth at most four, if $EG(R)$ contains a cycle. Furthermore, rings with complete or star essential graphs are characterized. Also, we study the affinity between essential graph and zero-divisor graph that is associated with a ring. Finally, we show that the essential graph associated with an Artinian ring is weakly perfect, i.e. its vertex chromatic number equals its clique number.

In this paper, we describe the algebras $A({\mathrm{\Gamma }}_{K_n})$ associated with the Hasse graph of the poset of the faces of the complete graph at n vertices $K_n$. Present the relations that define this algebra, calculate the Hilbert series of quadratic grade algebra $A({\mathrm{\Gamma }}_{K_n})$ and the graded trace generating functions of $D_n$ acting on $A({\mathrm{\Gamma }}_{K_n})$ and show that $A({\mathrm{\Gamma }}_{K_n})$ is a Koszul algebra. The methodology adopted in this paper consists of building the algebra $A({\mathrm{\Gamma }}_{K_n})$ using [I. Gelfand, V. Retakh, S. Serconek and R. L. Wilson, On a class of algebras associated to directed graphs, Selecta Math. 11(2) (2005) 281], giving a presentation based on what was established by [V. Retakh, S. Serconek and R. L. Wilson, On a class of koszul algebras associated to directed graphs, J. Algebra 304(2) (2006) 1114–1129] in terms of the vertices of the graph ${\mathrm{\Gamma }}_{K_n}$. After that, we use [V. Retakh, S. Serconek and R. L. Wilson, Hilbert series of algebras associated to directed graphs, J. Algebra 312(1) (2007) 142–151] to determine the Hilbert series of $A({\mathrm{\Gamma }}_{K_n})$ and use [9] again to show that this algebra is a Koszul algebra. We use [J. Caldeira, A. De Souza Lima and J. Eder Salvador De Vasconcelos, Representations of automorphism groups of algebras associated to star polygons, J. Algebra Appl. 18(10) (2019) 1950197; C. Duffy, Representations of Aut(A($\mathrm{\Gamma }$)) acting on homogeneous components of $A(\mathrm{\Gamma })$ and $A(\mathrm{\Gamma })!$, Adv. Appl. Math. 42(1) (2009) 94–122] to determine the generating functions of the graduated trace of $D_n$ acting on $A({\mathrm{\Gamma }}_{K_n})$.

The search for structural anomalies in a complete graph, $K_N$, using scattering quantum walks (SQWs) is investigated in this study. A complete graph with a second graph, $G$, attached to one of its vertices is referred to as external structural anomaly. The structural change within a complete graph is called internal structural anomaly. First, an example with $G$ being a triangle is presented to illustrate the problem. Then, a general proof is provided to show that the vertex to which $G$ is attached can be found in $O(\sqrt{N})$ time steps as long as the connectivity between $G$ and $K_N$ is far less than $N$. Finally, two types of internal structural anomalies, namely, a complete graph with a missing edge and that with an extra loop, are considered. These two anomalies can be solved in a similar manner as external anomalies in $O(\sqrt{N})$ time steps. These examples demonstrate that Cottrell’s formalism in star graphs can be applied more generally.

In this paper, we define a new graph ${\Gamma }_d(G)$ on a finite group $G$, where $d$ is a divisor of $\left|G\right|$. The vertices of ${\Gamma }_d(G)$ are the subgroups of $G$ of order $d$ and two subgroups $H_1$ and $H_2$ of $G$ are said to be adjacent if there exists $S_i\in {𝒯}(G,H_i)$$(i=1,2)$ such that $S_1\cong S_2$, where ${𝒯}(G,H_i)$$(i=1,2)$ denote the set of all NRTs of $H_i$ in $G$. We shall discuss the completeness of ${\Gamma }_d(G)$ for various groups like finite abelian groups, dihedral groups and some finite $p$-groups.

Let $X$ be a finite simple graph. The $2$-distance graph $D_2(X)$ of $X$ is the graph with the same vertex set as $X$ and two vertices are adjacent if and only if their distance in $X$ is exactly $2$. A graph $G$ is a $2$-distance graph if there exists a graph $X$ such that $D_2(X)\cong G$. In this paper, we give three characterizations of $2$-distance graphs, and find all graphs $X$ such that $D_2(X)\cong k{P}_2$ or $K_m\cup K_n$, where $k\ge 2$ is an integer, $P_2$ is the path of order $2$, and $K_m$ is the complete graph of order $m\ge 1$.

The planarity of the direct product of two graphs has been widely studied in the past. Surprisingly, the missing part is the product with K₂, which seems to be less predictible. In this piece of work, we characterize which subdivisions of multipartite complete graphs, have their direct product with K₂ planar. This can be seen as a step towards the characterization of all such graphs.