The Inclusion Ideal Graph of Rings

Let R be a ring with unity. The inclusion ideal graph of a ring R, denoted by In(R), is a graph whose vertices are all nontrivial left ideals of R and two distinct left ideals I and J are adjacent if and only if I ? J or J ? I. In this paper, we show that In(R) is not connected if and only if R ? M ₂(D) or D ₁ × D ₂, for some division rings, D, D ₁ and D ₂. Moreover, we prove that if In(R) is connected, then diam(In(R)) ≤3. It is shown that if In(R) is a tree, then In(R) is a caterpillar with diam(In(R)) ≤3. Also, we prove that the girth of In(R) belongs to the set {3, 6, ∞}. Finally, we determine the clique number and the chromatic number of the inclusion ideal graph for some classes of rings.     

A note on generalized pentagons

Thomassen introduced the notion of a generalized pentagon and proved that the chromatic number of a triangle-free graph with n vertices and minimum degree at least cn, , is at most 2(3c−1)^{−(4c−1)/(3c−1)}, the first bound independent of the order n. We present a short proof of the stronger upper bound (3c−1)⁻¹, again based on generalized pentagons.     

Two classes of edge domination in graphs

Let (, resp.) be the number of (local) signed edge domination of a graph G [B. Xu, On signed edge domination numbers of graphs, Discrete Math. 239 (2001) 179-189]. In this paper, we prove mainly that and hold for any graph G of order n(n?4), and pose several open problems and conjectures.     

Bounds for the Least Laplacian Eigenvalue of a Signed Graph

A signed graph is a graph with a sign attached to each edge. This paper extends some fundamental concepts of the Laplacian matrices from graphs to signed graphs. In particular, the relationships between the least Laplacian eigenvalue and the unbalancedness of a signed graph are investigated.     

Lower bounds on the signed domination numbers of directed graphs

A numerical invariant of directed graphs concerning domination which is named signed domination number γ_S is studied in this paper. We present some sharp lower bounds for γ_S in terms of the order, the maximum degree and the chromatic number of a directed graph.     

两类图的符号控制数

图G的符号控制数γs(G)有着许多重要的应用背景,因而确定其精确值有重要意义.Cm表示m个顶点的圈,n-Cm和n·Cm分别表示恰有一条公共边或一个公共顶点的n个Cm的拷贝.给出了n-Cm和n·Cm的符号控制数.     

The signed domatic number of some regular graphs

Let G be a finite and simple graph with vertex set V(G), and let f:V(G)→{−1,1} be a two-valued function. If ∑_x∈N[v]f(x)≥1 for each v∈V(G), where N[v] is the closed neighborhood of v, then f is a signed dominating function on G. A set {f₁,f₂,…,f_d} of signed dominating functions on G with the property that for each x∈V(G), is called a signed dominating family (of functions) on G. The maximum number of functions in a signed dominating family on G is the signed domatic number on G. In this paper, we investigate the signed domatic number of some circulant graphs and of the torus C_p×C_q.     

Circular flow on signed graphs

The circular flow number Φc(G,σ) of a signed graph (G,σ) is the minimum r for which an orientation of (G,σ) admits a circular r-flow. We prove that the circular flow number of a signed graph (G,σ) is equal to the minimum imbalance ratio of an orientation of (G,σ). We then use this result to prove that if G is 4-edge-connected and (G,σ) has a nowhere zero flow, then Φc(G,σ) (as well as Φ(G,σ)) is at most 4. If G is 6-edge-connected and (G,σ) has a nowhere zero flow, then Φc(G,σ) is strictly less than 4.     

Injective coloring of planar graphs

A coloring of a graph G is injective if its restriction to the neighborhood of any vertex is injective. The injective chromatic numberχ_i(G) of a graph G is the least k such that there is an injective k-coloring. In this paper we prove that if G is a planar graph with girth g and maximum degree Δ, then (1) χ_i(G)=Δ if either g≥20 and Δ≥3, or g≥7 and Δ≥71; (2) χ_i(G)≤Δ+1 if g≥11; (3) χ_i(G)≤Δ+2 if g≥8.     

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

On signed cycle domination in graphs

Let G=(V,E) be a graph, a function f:E→{−1,1} is said to be an signed cycle dominating function (SCDF) of G if ∑_e∈E(C)f(e)≥1 holds for any induced cycle C of G. The signed cycle domination number of G is defined as is an SCDF of G}. In this paper, we obtain bounds on , characterize all connected graphs G with , and determine the exact value of for some special classes of graphs G. In addition, we pose some open problems and conjectures.