The Annihilating-Ideal Graph of a Commutative Ring with Respect to an Ideal

For a commutative ring R with identity, the annihilating-ideal graph of R, denoted 𝔸𝔾(R), is the graph whose vertices are the nonzero annihilating ideals of R with two distinct vertices joined by an edge when the product of the vertices is the zero ideal. We will generalize this notion for an ideal I of R by replacing nonzero ideals whose product is zero with ideals that are not contained in I and their product lies in I and call it the annihilating-ideal graph of R with respect to I, denoted 𝔸𝔾 _I (R). We discuss when 𝔸𝔾 _I (R) is bipartite. We also give some results on the subgraphs and the parameters of 𝔸𝔾 _I (R).     

Unit Graphs Associated with Rings

Let R be a ring with nonzero identity. The unit graph of R, denoted by G(R), has its set of vertices equal to the set of all elements of R; distinct vertices x and y are adjacent if and only if x + y is a unit of R. In this article, the basic properties of G(R) are investigated and some characterization results regarding connectedness, chromatic index, diameter, girth, and planarity of G(R) are given. (These terms are defined in Definitions and Remarks 4.1, 5.1, 5.3, 5.9, and 5.13.)     

图的色因子分解

设 ｎ１ ≥ ｎ ２ ≥ … ≥ ｎｋ ≥ ２ 是整数． 若图 Ｇ 能边分解成 Ｇ１  Ｇ２  …  Ｇｋ , 这里 χ（ Ｇｉ） ＝ ｎ ｉ, ｉ＝１,２,…,ｋ ,则称 Ｇ 有（ｎ１ , ｎ２ , …, ｎｋ ）色因子 分解． 本文改进 了 Ｈａｋｉｍ ｉ和 Ｓｃｈｍ ｅｉｃｈ ｅｌ 关于图的色因 子分解的结果,作为推 论,推广了 Ｍ ａｔｕｌａ 和 Ｈａｒａｒｙ 等人的结果     

Coloring the cliques of line graphs

The weak chromatic number, or clique chromatic number (CCHN) of a graph is the minimum number of colors in a vertex coloring, such that every maximal clique gets at least two colors. The weak chromatic index, or clique chromatic index (CCHI) of a graph is the CCHN of its line graph.Most of the results here are upper bounds for the CCHI, as functions of some other graph parameters, and contrasting with lower bounds in some cases. Algorithmic aspects are also discussed; the main result within this scope (and in the paper) shows that testing whether the CCHI of a graph equals $2$ is NP-complete. We deal with the CCHN of the graph itself as well.     

Coloring graphs with crossings

We generalize the Five-Color Theorem by showing that it extends to graphs with two crossings. Furthermore, we show that if a graph has three crossings, but does not contain K₆ as a subgraph, then it is also 5-colorable. We also consider the question of whether the result can be extended to graphs with more crossings.     

图的倍图与补倍图

计算机科学数据库的关系中遇到了可归为倍图或补倍图的参数和哈密顿圈的问题．对简单图C,如果V（D（G））：V（G）∪V（G′）E（D（G））=E（C）∪E（C″）U{vivj′｜vi∈V（G）,Vj′∈V（G′）且vivj∈E（G））那么,称D（C）是C的倍图,如果V（D（G））=V（C）∪V（G′）,E（D（C））：E（C）∪E（G′）∪{vivj′}vi∈V（G）,vj′∈V（G’）and vivj∈（G））,称D（C）是G的补倍图,这里G′是G的拷贝．本文研究了D（G）和D的色数,边色数,欧拉性,哈密顿性和提出了D（G） 的边色数是D（G）的最大度等公开问题．     

On Harary index of graphs

The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. For a connected graph G=(V,E) and two nonadjacent vertices v_i and v_j in V(G) of G, recall that G+v_iv_j is the supergraph formed from G by adding an edge between vertices v_i and v_j. Denote the Harary index of G and G+v_iv_j by H(G) and H(G+v_iv_j), respectively. We obtain lower and upper bounds on H(G+v_iv_j)−H(G), and characterize the equality cases in those bounds. Finally, in this paper, we present some lower and upper bounds on the Harary index of graphs with different parameters, such as clique number and chromatic number, and characterize the extremal graphs at which the lower or upper bounds on the Harary index are attained.     

The clique numbers of regular graphs of matrix algebras are finite

Let F be a field, char(F)≠2, and SGL_n(F), where n is a positive integer. In this paper we show that if for every distinct elements x,yS, x+y is singular, then S is finite. We conjecture that this result is true if one replaces field with a division ring.     

The Toughness of a Toroidal Graph with Connectivity 3 and Girth 6 is Exactly 1

We show that every toroidal graph with connectivity 3 and girth 6 is bipartite. This implies that its toughness is at most 1. This answers a question in Goddard, Plummer, and Swart [3] in which it was shown that such a graph has toughness at least 1.Acknowledgments We would like to thank Douglas B. West for helpful comments.Final version received: November 17, 2003     

Ideal extensions of graph algebras

Let A and B be graph algebras. In this paper we present the notion of an ideal in a graph algebra and prove that an ideal extension of A by B always exists. We describe (up to isomorphism) all such extensions.     

Semidefinite programming relaxations for graph coloring and maximal clique problems

The semidefinite programming formulation of the Lovász theta number does not only give one of the best polynomial simultaneous bounds on the chromatic number χ(G) or the clique number ω(G) of a graph, but also leads to heuristics for graph coloring and extracting large cliques. This semidefinite programming formulation can be tightened toward either χ(G) or ω(G) by adding several types of cutting planes. We explore several such strengthenings, and show that some of them can be computed with the same effort as the theta number. We also investigate computational simplifications for graphs with rich automorphism groups. Partial support by the EU project Algorithmic Discrete Optimization (ADONET), MRTN-CT-2003-504438, is gratefully acknowledged.     

微商共同作用在半素环的Lie理想上的结果

本文讨论了微商共同作用在半素环的某个Ｌｉｅ理想上的问题。给出了如下结果：设Ｒ是带有中心Ｚ（Ｒ）的半素环,Ｑｍｒ是Ｒ的极大右商环,Ｌ是Ｒ的非交换Ｌｉｅ理想,ｄ和δ是Ｒ的微商,假设ｒＲ（「Ｌ,Ｌ」）＝０且ｄ（ｘ）ｘ－ｘδ（ｘ）∈Ｚ（Ｒ）对任意ｘ∈Ｌ成立,则在Ｒ的扩张形心Ｃ中存在一个幂等元ｅ使得ｄ（１－ｅ）Ｑｍｒ＝０和δ（１－ｅ）Ｑｍｒ）＝０并且ｅＱｍｒ满足Ｓ４。另外给出微商共同作用在半素环上多项式的结     

理想簇和根理想

关于环的理想的根有两种定义,一种是所有包含I的极大理想的交,另一种是所有包含I的素理想交,本文主要研究后者定义的一些性质,以及和理想簇V(I)(所有包含I的素理想的集合)的关系.