The Zero-Divisor Graph Associated to a Semigroup

The zero-divisor graph of a commutative semigroup with zero is the graph whose vertices are the nonzero zero-divisors of the semigroup, with two distinct vertices adjacent if the product of the corresponding elements is zero. New criteria to identify zero-divisor graphs are derived using both graph-theoretic and algebraic methods. We find the lowest bound on the number of edges necessary to guarantee a graph is a zero-divisor graph. In addition, the removal or addition of vertices to a zero-divisor graph is investigated by using equivalence relations and quotient sets. We also prove necessary and sufficient conditions for determining when regular graphs and complete graphs with more than two triangles attached are zero-divisor graphs. Lastly, we classify several graph structures that satisfy all known necessary conditions but are not zero-divisor graphs.     

The non-nilpotent graph of a semigroup

We associate a graph ${\mathcal{N}}_{S}$ with a semigroup S (called the upper non-nilpotent graph of S). The vertices of this graph are the elements of S and two vertices are adjacent if they generate a semigroup that is not nilpotent (in the sense of Malcev). In case S is a group this graph has been introduced by A. Abdollahi and M.?Zarrin and some remarkable properties have been proved. The aim of this paper is to study this graph (and some related graphs, such as the non-commuting graph) and to discover the algebraic structure of S determined by the associated graph. It is shown that if a finite semigroup S has empty upper non-nilpotent graph then S is positively Engel. On the other hand, a semigroup has a complete upper non-nilpotent graph if and only if it is a completely simple semigroup that is a band. One of the main results states that if all connected ${\mathcal{N}}_{S}$ -components of a semigroup S are complete (with at least two elements) then S is a band that is a semilattice of its connected components and, moreover, S is an iterated total ideal extension of its connected components. We also show that some graphs, such as a cycle C _n on n vertices (with n??5), are not the upper non-nilpotent graph of a semigroup. Also, there is precisely one graph on 4 vertices that is not the upper non-nilpotent graph of a semigroup with 4 elements. This work also is a continuation of earlier work by Okni??ski, Riley and the first named author on (Malcev) nilpotent semigroups.     

On bipartite zero-divisor graphs

A (finite or infinite) complete bipartite graph together with some end vertices all adjacent to a common vertex is called a complete bipartite graph with a horn. For any bipartite graph G, we show that G is the graph of a commutative semigroup with 0 if and only if it is one of the following graphs: star graph, two-star graph, complete bipartite graph, complete bipartite graph with a horn. We also prove that a zero-divisor graph is bipartite if and only if it contains no triangles. In addition, we give all corresponding zero-divisor semigroups of a class of complete bipartite graphs with a horn and determine which complete r-partite graphs with a horn have a corresponding semigroup for r≥3.     

The zero-divisor graph of a commutative semigroup

An undirected graph Γ(S) is associated to each commutative multiplicative semigroup S with 0. The vertices of the graph are labeled by the nonzero zero-divisors of S , and two vertices x,y are connected by an edge in case xy = 0 in S . The properties and possible structures of the graph Γ (S) are studied.     

A New Graph Structure of Commutative Semigroups

In this paper, a new zero-divisor graph $\overline{\G}(S)$ is defined and studied for a commutative semigroup $S$ with zero element. The properties and the structure of the graph are studied; for any complete graph and complete bipartite graph $G$, commutative semigroups $S$ are constructed such that the graph $G$ is isomorphic to $\overline{\G}(S)$.     

Distances on the Commuting Graph of the Ring of Real Martices

The vertices of the commuting graph of a semigroup S are the noncentral elements of this semigroup, and its edges join all pairs of elements g, h that satisfy the relation gh = hg. The paper presents a proof of the fact that the diameter of the commuting graph of the semigroup of real matrices of order n ≥ 3 is equal to 4. A survey of results in that subject matter is presented, and several open problems are formulated.     

The Zero-Divisor Graphs Which Are Uniquely Determined By Neighborhoods

A nonempty simple connected graph G is called a uniquely determined graph, if distinct vertices of G have distinct neighborhoods. We prove that if R is a commutative ring, then Γ(R) is uniquely determined if and only if either R is a Boolean ring or T(R) is a local ring with x² = 0 for any x ∈ Z(R), where T(R) is the total quotient ring of R. We determine all the corresponding rings with characteristic p for any finite complete graph, and in particular, give all the corresponding rings of K_n if n + 1 = p^q for some primes p, q. Finally, we show that a graph G with more than two vertices has a unique corresponding zero-divisor semigroup if G is a zero-divisor graph of some Boolean ring.     

Zero-Divisor Semigroups and Some Simple Graphs

In this article, we study commutative zero-divisor semigroups determined by graphs. We prove that for all n ≥ 4, the complete graph K _n together with two end vertices has a unique corresponding zero-divisor semigroup, while the complete graph K _n together with three end vertices has no corresponding semigroups. We determine all the twenty zero-divisor semigroups whose zero-divisor graphs are the complete graph K ₃ together with an end vertex.     

本刊英文版Vol.33(2017),No.6论文摘要（英文）

正A Comparison between the Metric Dimension and Zero Forcing Number of Trees and Unicyclic Graphs Linda EROH Cong X.KANG Eunjeong YI Abstract The metric dimension dim(G)of a graph G is the minimum number of vertices such that every vertex of G is uniquely determined by its vector of distances to the chosen vertices.The zero forcing number Z(G)of a graph G is the minimum cardinality of a set S of     

On one test for the switching separability of graphs modulo <Emphasis Type="Italic">q</Emphasis>

We consider graphs whose edges are marked by numbers (weights) from 1 to q - 1 (with zero corresponding to the absence of an edge). A graph is additive if its vertices can be marked so that, for every two nonadjacent vertices, the sum of the marks modulo q is zero, and for adjacent vertices, it equals the weight of the corresponding edge. A switching of a given graph is its sum modulo q with some additive graph on the same set of vertices. A graph on n vertices is switching separable if some of its switchings has no connected components of size greater than n - 2. We consider the following separability test: If removing any vertex from G leads to a switching separable graph then G is switching separable. We prove this test for q odd and characterize the set of exclusions for q even. Connection is established between the switching separability of a graph and the reducibility of the n-ary quasigroup constructed from the graph.     

The inertia of unicyclic graphs and the implications for closed-shells

The inertia of a graph is an integer triple specifying the number of negative, zero, and positive eigenvalues of the adjacency matrix of the graph. A unicyclic graph is a simple connected graph with an equal number of vertices and edges. This paper characterizes the inertia of a unicyclic graph in terms of maximum matchings and gives a linear-time algorithm for computing it. Chemists are interested in whether the molecular graph of an unsaturated hydrocarbon is (properly) closed-shell, having exactly half of its eigenvalues greater than zero, because this designates a stable electron configuration. The inertia determines whether a graph is closed-shell, and hence the reported result gives a linear-time algorithm for determining this for unicyclic graphs.     

On the orders of directly indecomposable groups

We investigate the set of those integers n for which directly indecomposable groups of order n exist. For even n such groups are easily constructed. In contrast, we show that the density of the set of odd numbers with this property is zero. For each n we define a graph whose connected components describe uniform direct decompositions of all groups of order n. We prove that for almost all odd numbers (i.e., with the exception of a set of density zero) this graph has a single ‘big’ connected component and all other vertices are isolated. We also give an asymptotic formula for the number of isolated vertices of the graph, i.e., for the number of prime divisors q of n such that every group of order n has a cyclic direct factor of order q.     

An asymptotically exact algorithm for the maximum traveling salesman problem in a finite-dimensional normed space

We consider the geometric maximum traveling salesman problem on assuming that the vertices of a graph lie in an arbitrary finite-dimensional normed space. For this problem we obtain an approximate algorithm with the relative error tending to zero as the number of vertices grows. The algorithm generalizes Serdyukov’s algorithm for the Euclidean Max TSP.     

The free idempotent generated locally inverse semigroup

In this paper we construct a model for the free idempotent generated locally inverse semigroup on a set X. The elements of this model are special vertex-labeled bipartite trees with a pair of distinguished vertices. To describe this model, we need first to introduce a variation of a model for the free pseudosemilattice on a set X presented in Auinger and Oliveira (On the variety of strict pseudosemilattices. Stud Sci Math Hungarica 50:207–241, 2013). A construction of a graph associated with a regular semigroup was presented in Brittenham et al. (Subgroups of free idempotent generated semigroups need not be free. J Algebra 321:3026–3042, 2009) in order to give a first example of a free regular idempotent generated semigroup on a biordered set E with non-free maximal subgroups. If G is the graph associated with the free pseudosemilattice on X, we shall see that the models we present for the free pseudosemilattice on X and for the free idempotent generated locally inverse semigroup on X are closely related with the graph G.     

The Zero Divisor Graph of 2 × 2 Matrices Over a Field

A zero divisor graph, Γ(R), is formed from a ring R by having each element of Z(R) \ {0} to be a vertex in the graph and having two vertices u and v adjacent if the corresponding elements from the ring are nonequal and have product equal to zero. In this paper, the structure of the zero-divisor graph of 2 × 2 matrices over a field, Γ(M2(F)), are completely determined.     

Perfect zero–one matrices

A zero–one matrix is called perfect if the polytope of the associated set packing problem has integral vertices only. By this definition, all totally unimodular zero–one matrices are perfect. In this paper we give a characterization of perfect zero–one matrices in terms offorbidden submatrices. Perfect zero–one matrices are closely related to perfect graphs and constitute a generalization of balanced matrices as introduced by C. Berge. Furthermore, the results obtained here bear on an unsolved problem in graph theory, the strong perfect graph conjecture, also due to C. Berge.     

Minimum vertex covers and the spectrum of the normalized Laplacian on trees

We show that, in the graph spectrum of the normalized graph Laplacian on trees, the eigenvalue 1 and eigenvalues near 1 are strongly related to minimum vertex covers.In particular, for the eigenvalue 1, its multiplicity is related to the size of a minimum vertex cover, and zero entries of its eigenvectors correspond to vertices in minimum vertex covers; while for eigenvalues near 1, their distance to 1 can be estimated from minimum vertex covers; and for the largest eigenvalue smaller than 1, the sign graphs of its eigenvectors take vertices in a minimum vertex cover as representatives.     

The subdirectly irreducible algebras in the variety generated by graph algebras

We show that every non-trivial subdirectly irreducible algebra in the variety generated by graph algebras is either a two-element left zero semigroup or a graph algebra itself. We characterize all the subdirectly irreducible algebras in this variety. From this we derive an example of a groupoid (graph algebra) that generates a variety with NP-complete membership problem. This is an improvement over the result of Z. Székely who constructed an algebra with similar properties in the signature of two binary operations. The second author was supported by OTKA grants no. T043671, NK67867, K67870 and by NKTH (National Office for Research and Technology, Hungary).     

Balanced group-labeled graphs

A group-labeled graph is a graph whose vertices and edges have been assigned labels from some abelian group. The weight of a subgraph of a group-labeled graph is the sum of the labels of the vertices and edges in the subgraph. A group-labeled graph is said to be balanced if the weight of every cycle in the graph is zero. We give a characterization of balanced group-labeled graphs that generalizes the known characterizations of balanced signed graphs and consistent marked graphs. We count the number of distinct balanced labellings of a graph by a finite abelian group $\Gamma$ and show that this number depends only on the order of $\Gamma$ and not its structure. We show that all balanced labellings of a graph can be obtained from the all-zero labeling using simple operations. Finally, we give a new constructive characterization of consistent marked graphs and markable graphs, that is, graphs that have a consistent marking with at least one negative vertex.