# Graph ofBCI-Algebras

Authors: Omid Zahiri; Rajab Ali Borzooei
Journal: International Journal of Mathematics and Mathematical Sciences
 (2012)

---

## Abstract

We associate a graph to any subsetY of a BCI-algebra X and denote it by
G(Y). Then we find the set of all connected components of G(X) and verify the relation between X
and G(X), when X is commutative BCI-algebra or G(X) is complete graph or n-star graph. Finally,
we attempt to investigate the relation between some operations on graph and some operations on BCI-algebras.


---

## Body

## 1. Introduction

BCK- and BCI-algebras are two classes of abstract algebras were introduced by Imai and Iséki [1, 2], in 1966. The notion of BCK-algebras is originated from two different ways. One of the motivations is from classical and nonclassical propositional logic. Another motivation is based on set theory. It is known that the class of BCK-algebras is a proper subclass of the class of BCI-algebras. Many authors studied the graph theory in connection with semigroups and rings. For example, Beck [3] associated to any commutative ring R its zero divisors graph G(R), whose vertices are the zero divisors of R, with two vertices a,b jointed by an edge in case ab=0. In [4], Jun and Lee defined the notion of zero divisors and quasi-ideals in BCI-algebra and show that all zero divisors are quasi-ideal. Then, they introduced the concept of associated graph of BCK/BCI-algebra and verified some properties of this graph and proved that if X is a BCK-algebra, then associated graph of X is a connected graph. Moreover, if X is a BCI-algebra and x∈X such that x is not contained in BCK-part of X, then there is not any edge connecting x and y, for any y∈X. In this paper, we associate new graph to a BCI-algebras X which is denoted it by G(X). This definition based on branches of X. If X is a BCK-algebras, then this definition and last definition, which was introduced by Jun and Lee, are the same. Then, for any a∈P, we defined the concept of a-divisor, where P is a p-semisimple part of BCI-algebra X and show that it is quasi-ideal of X. Then, we explain some properties of this graph as mentioned in the abstract.


## 2. Preliminaries

Definition 2.1 (see [1, 2]).
ABCI-algebra is an algebra (X,*,0) of type (2,0) satisfying the following conditions:(BCI1)
((x*y)*(x*z))*(z*y)=0;(BCI2)
x*0=x;(BCI3)
x*y=0 and y*x=0 imply y=x.
IfX is a BCI-algebra, then for all x,y∈X the following hold:
(BCI4)
x*x=0;(BCI5)
x*(x*(x*y))=x*y;(BCI6)
(x*y)*z=(x*z)*y;(BCI7)
x≤y implies x*z≤y*z and z*y≤z*x, for any z∈X.
Moreover, the relation ≤ was defined by x≤y⇔x*y=0, for any x,y∈X, is a partial-order on X, which is called BCI-ordering of X. The set B={x∈X∣0*x=0} is called BCK-part of X. A BCI-algebra X is called a BCK-algebra if B=X. A BCK-chain is a BCK-algebra such that (X,≤) is a chain, where ≤ is the BCI-ordering of X. A nonzero element a of BCK-algebra X is called an atom of X if x*a=0 implies x=a, for any nonzero element x∈X. Moreover, P={x∈X∣0*(0*x)=x} is called p-semisimple part of a BCI-algebra X. It is the set of all minimal elements of X, with respect to the BCI-ordering of X. The BCI-algebra X is called a p-semisimpleBCI-algebra if P=X. For any a∈P, we use the notation VX(a) or simply V(a) to denote the set {x∈X∣a*x=0} which is called the branch of X with respect to a. It is easy to see that X=⋃a∈PV(a), and for any distinct elements a,b∈P, we have(P1)
V(a)∩V(b)=∅;(P2)
ifx∈V(a) and y∈V(b), then x*y∈V(a*b);(P3)
ifx∈V(a), then {y∈X∣x≤y}∪{y∈X∣y≤x}⊆V(a);(P4)
for allx∈X, x*a=0 implies x=a.A BCI-algebra X is called commutative if x≤y implies x=y*(y*x), for any x,y∈X. Moreover, X is called branchwise commutative if x*(x*y)=y*(y*x), for all x,y∈V(a) and all a∈P. For more details, we refer to [5–11].Lemma 2.2 (see [9]).
ABCI-algebra X is commutative if and only if it is branchwise commutative.Theorem 2.3 (see [10]).
LetX={x0,x1,…,xn} and (X,*,0) be a BCK-chain with x0 as the zero element, whose BCI-ordering is supposed as follows: x0<x1<⋯<xn. Then, X is commutative if and only if the relation * on X is given by xi*xj=xi*j, where i*j=max{0,i-j}, for any i,j∈{0,1,…,n} (see [10, Theorem 2.3.3]).A partial-order set(P,≤) is said to be of finite length if the lenghts of all chains of P are bounded. Let x,y∈P. Then, a chain of length n between x and y is a chain a0<a1<⋯<an-1<an such that {a0,an}={x,y}. For any x,y∈P, l(x,y) is the greatest number in the lenghts of all chain between a and b.ABCI-algebra X is said to be finite length if it is finite length as a partial-order set.Note 1 (see [4]).
LetX be a BCI-algebra and A⊆X. We will use the notations UX(A) and LX(A) or simply U(A) and L(A) to denote the sets {x∈X∣a*x=0,∀a∈A} and {x∈X∣x*a=0,∀a∈A}, respectively, that is, U(A)={x∈X∣a≤x,∀a∈A} and L(A)={x∈X∣x≤a,∀a∈A}.Definition 2.4 (see [4]).
A nonempty subsetI of BCI-algebra X is called a quasi-ideal of X if x*y=0 implies x∈I, for any y∈I and x∈X.Proposition 2.5 (see [12]).
Let(X,*1,0) and (Y,*2,0) be two BCK-algebras such that X∩Y={0} and * be the binary operation on X∪Y as follows: for any a,b∈X∪Y;
(2.1)a*b={a*1bifa,b∈X,a*2bifa,b∈Y,aotherwise.
Then, (X∪Y,*,0) is a BCK-algebra. We denote (X∪Y,*,0) by X⊕Y.Definition 2.6 (see [4]).
For anyx∈X, the set {y∈X∣L({x,y})={0}} is called the set of all zero divisors of x.Theorem 2.7 (see [4]).
For any elementx of BCK-algebra X, the set of all zero divisors of x is a quasi-ideal of X containing the zero element {0}.LetG be a graph, E(G) be the set of all edges of G and V(G) be the set of all vertexes of G. For any S⊆E(G), the graph with vertex set V(G) and edge set E(G)-S is denoted by G-S. The edge which connect two vertices x,y is denoted by xy. Note that, xy and yx are the same. For any T⊆V(G), the graph with vertex set V(G)-T and edge set E(G)-T′ is denoted by G-T, where T′={xy∈E(G)∣x∈T,y∈G}. A graph H is called a subgraph of G if V(H)⊆V(G) and E(H)⊆E(G). A graph G=(V,E) is connected, if any vertices x,y of G linked by a path in G, otherwise the graph is disconnected. A tree is a connected graph with no cycles. The degree of a vertex v in a graph G, denoted by deg(v), is the number of edges of G incident with v and deg(G)=∑x∈Vdeg(x)=2|E|. We denote by δ(G) and Δ(G) the minimum and maximum degrees of the vertices of G, respectively. If G and H are two graphs such that V(G)∩V(H)=∅, then the graph with vertex set V(G)∪V(H) and edge set E(G)∪E(H) is called the disjoint union of G and H and we denote it by G∪H. Any graph G=(V,E) may be expressed uniquely as a disjoint union of connected graphs. These graphs are called the connected components or simply components of G. The number of components of G is denoted by c(G). A graph G is called empty graph if E(G)=∅. Moreover, a graph K is called complete graph if xy∈E(G), for any distinct elements x,y∈V(G). For more details we refer to [13, 14].Definition 2.8.
LetG and H be two graphs such that V(G)∩V(H)=∅. We denote the graph G+H, for the graph, whose vertex set and edge set are V(G)∪V(H) and E(G)∪E(H)∪{xy∣x∈V(G),y∈V(H)}, respectively.Definition 2.9 (see [4]).
By the associated graph ofBCK/BCI-algebra X, denoted Γ(X), we means the graph whose vertices are just the elements of X, and for distinct x,y∈Γ(X), there is an edge connecting x and y if and only if L({x,y})={0}.Definition 2.10 (see [13, 15]).
LetG be a finite graph with |V(G)|=n. Then, the adjacency matrix of G is an n×n matrix AG=[ai,j] such that ai,j is the number of edges joining vi and vj. Moreover, we denote the characteristic polynomial of the matrix AG, by χ(G,λ). That is χ(G,λ)=det(λI-AG), where I is a n×n identity matrix.Proposition 2.11 (see [15, Proposition 2.3]).
LetG be a graph and χ(G,λ)=λn+c1λn-1+c2λn-2+⋯+cn. be the characteristic polynomial of the adjacent matrix G. Then, c1=0, -c2 is the number of edges of G and -c3 is twice the number of triangles in G.


## 3. Graph Based onBCI-Algebras

From now on, in this paper,(X,*,0) or simply X is a BCI-algebra, B is a BCK-part and P is a p-semisimple part of X, unless otherwise state. For all x,y∈X, we use x≨y to denote x≤y and x≠y.Definition 3.1.
Note that the set of all 0-divisors ofxand the set of all zero divisors of x are the same. Let x∈X. Then, there exists a∈P such that x∈V(a). We will use the notation Zx to denote the set of all y∈X such that L({x,y})={a}, that is, Zx={y∈X∣L({x,y})={a}}, which is called the set of a-divisor of X.Note that the set of all 0-divisors ofx and the set of all zero divisors of x are the same.Lemma 3.2.
Leta,b∈P and x,y∈X. Then(i)
one has(3.1)L({x,a})={aifx∈V(a),∅otherwise,(ii)
ifa≠b, x∈V(a) and y∈V(b), then L({x,y})=∅.Proof.
(i) Clearly, ifx∈V(a), then L({x,a})={a}. Let x∉V(a). Then, y∈L({x,a}) implies y≤x and y≤a. Since a∈P, we have a=y and so a≤x, which is impossible. Therefore, L({x,a})=∅.
(ii) Sincea≠b, we have L({x,y})⊆V(a)∩V(b)=∅.Lemma 3.3.
For anyx,y∈X, if x*y=0, then L({x})⊆L({y}) and Zy⊆Zx.Proof.
Letx*y=0, for some x,y∈X. Then, x≤y. Clearly, L{x}⊆L{y}. If x∈V(a), where a∈P, then a≤x≤y and so by (P3), y∈V(a), too. Now, let u∈Zy. Then, L({u,y})={a} and so a∈L({u,x})⊆L({u,y})={a}. Hence, L({x,u})=a and so u∈Zx. Therefore, Zy⊆Zx.Jun and Lee in [4] proved that if x is an element of BCK-algebra X, then the set of all zero divisors of x is a quasi-ideal of X. In Theorem 3.4, we will show that if x is an element of BCI-algebra X, then Zx is a quasi-ideal of X.Theorem 3.4.
Zx is a quasi-ideal of X, for any x∈X.Proof.
Letx∈X such that x∈V(a), for some a∈P and u,v∈X such that u*v=0 and v∈Zx. Then, u≤v and L({v,x})={a}. Hence, v∈V(a) and so by (P3), u∈V(a). Since a∈L({u,x})⊆L({v,x})={a}, then L({u,x})={a}. Therefore, u∈Zx and so Zx is a quasi-ideal of X.Definition 3.5.
LetY⊆X, and G(Y) be a simple graph, whose vertices are just the elements of Y and for distinct x,y∈Y, there is an edge connecting x and y, denoted by xy if and only if L({x,y})={a}, for some a∈P. If Y=X, then G(X) is called a BCI-graph ofX.Clearly, ifX is a BCK-algebra, then G(X)=Γ(X). But it is not true, in general.Example 3.6.
(i) LetX={0,1,a,b,c}. Define the binary operation “*’’ on X by the following table:
Then, (X,*,0) is a BCI-algebra, P={0,a}, V(0)={0,1}, and V(a)={a,b,c}. Moreover, L({1,0})={0} and L({a,b})=L({a,c})=L({b,c})={a} and so E(G(X))={10,ac,bc,ab}. Therefore, the graphs G(X) and Γ(X) which are given by Figure 1 are different.
(ii) Let(X,*,0) be the BCI-algebra in Example 3.6(i) and Y={0,1,b,c}. Then, G(Y) is given by Figure 2.Figure 1Figure 2Example 3.7 (see [4]).
LetX={0,a,b,c}. Define the binary operation “*’’ on X by the following table:
Then, (X,*,0) is a BCK-algebra and P={0} and so G(X)=Γ(X). Moreover, L({0,a})=L({0,b})=L({0,c})=L({a,c})=L({b,c})=L({a,b})={0}. Therefore, the graph G(X) is given by Figure 3.Figure 3Proposition 3.8.
(i)G(V(a)) is a connected graph, for any a∈P,
(ii)G(X)=⋃a∈PG(V(a)),
(iii)G(X) is a graph with |P| components.Proof.
(i) Leta∈P and x,y∈V(a). Then, by Lemma 3.2(i) xa,ya∈E(G(X)) and so there is a path from x to y in G(X).
(ii) SinceX=⋃a∈PV(a), then V(G(X))=V(⋃a∈PG(V(a))). Clearly, E(⋃a∈PG(V(a)))⊆E(G(X)). Now, let xy∈E(G(X)). Then, L({x,y})={a}, for some a∈P and so xy∈G(V(a)). Hence, E(⋃a∈PG(V(a)))=E(G(X)). Therefore, G(X)=⋃a∈PG(V(a)).
(iii) We want to show that there is not any path between elements ofV(a) and V(b), for all distinct elements a,b∈P. Let a,b be distinct elements of P, x∈V(a) and y∈V(b). If there is a path x,x1,x2,…,xn,y, which link x to y, then a=L({x,x1})≠∅ and so by Lemma 3.2(ii), x1∈V(a). By a similar way, we have x2,…,xn,y∈V(a), which is impossible. Hence, there is not any path between x and y. Therefore, by (i), G(X) is a graph with |P| components.Theorem 3.9.
X is a p-semisimple BCI-algebra if and only if G(X) is an empty graph.Proof.
Clearly, ifX is a p-semisimple BCI-algebra, then by Lemma 3.2(ii), G(X) is an empty graph. Conversely, let G(X) be an empty graph and x∈X. Since, 0*(0*x)∈P and x∈V(0*(0*x)), then L({0*(0*x),x})={0*(0*x)}. If 0*(0*x)≨x, then there exists an edge between x and 0*(0*x) in G(X), which is impossible. Hence, x=0*(0*x) and so X is a p-semisimple BCI-algebra.Definition 3.10.
Leta∈P. The element x∈V(a) is called an a-atom if x≠a and y*x=0 implies y=a or y=x, for all y∈X.Note that ifX is a BCK-algebra then the concept of 0-atom and atom are the same.Lemma 3.11.
LetX be a BCI-algebra of finite order. Then, for any x∈X-P, there is an a-atom b∈X, such that b≤x, for some a∈P.Proof.
Letx∈X-P. Then, there is a∈P such that x∈V(a). Let S={L(x,u)∣u*x=0, u∈V(a)-{a}}. Clearly, 0∈S. Since X is of finite length, then S has the greatest element. Let L(x,u) be the greatest element of S. Then, we show that v is an a-atom of X. Let w*v=0, for some w∈X. Then, w≤v and so by (P3), w∈V(a). If w≨v, then 1+L(x,u)≤L(x,w), which is impossible. Therefore, w=v or w=a and so v is an atom of X.Theorem 3.12.
LetX be a finite leght BCI-algebra and a∈P. Then(i)
G(V(a)) is a tree if and only if V(a)={a} or V(a) has only one a-atom.(ii)
G(X) is a tree if and only if X={0} or X is a BCK-algebra with only one atom.Proof.
(i) LetG(V(a)) be a tree. If V(a)={a}, we do not have any thing to prove. Let V(a)≠{a} and A be the set of all a-atoms of V(a). Then, by Lemma 3.11, we have 1≤|A|. Let x,y∈A, u≤x and u≤y, for some u∈X. Then, by (P3), u∈V(a). Since x,y are a-atoms of V(a), then u=a or x=u=y. Hence, x=y or xy∈E(G(X)). If xy∈E(G(X)), then by Lemma 3.2(i), we have xy,ax,ay∈E(G(X)). Hence, G(X) has a cycle, which is impossible. Therefore, x=y and so |A|=1. Conversely, let V(a) has only one a-atom. By Proposition 3.8, G(V(a)) is a connected graph. If V(a)={a}, then clearly, G(V(a)) is a tree. Let V(a)≠{a}, x,y∈V(a)-{a} and u be an a-atom of X. Then, by Lemma 3.11, u∈L({x,y}) and so L({x,y})≠{a}. Hence, E(G(X))={xa∣x∈V(a)-{a}} and so G(V(a)) does not have any cycle. Therefore, G(V(a)) is a tree.
(ii) LetG(X) be a tree. Then, G(X) is a connected graph and so by Proposition 3.8, |P|=1. Hence, P={0} and so, X is a BCK-algebra. Since X is a BCK-algebra, we have X=V(0) and so by (i), X={0} or X is a BCK-algebra with only one atom. The converse is straight consequent of (i).Example 3.13.
LetX=ℝ+={x∈ℝ∣0≤x} and x*y=max{x-y,0}, for any x,y∈X. Then, (X,*,0) is a BCK-algebra. Clearly, X does not have any atoms. Since X is a BCK-algebra, then by Proposition 3.8, G(X) is a connected graph. Moreover, L({x,y})≠{0}, for any x,y∈X-{0}. Hence, E(G(X))={x0∣x∈X-{0}}. Therefore, G(X) is a tree.Example 3.14.
Let “*’’ be the binary operation in Example3.13, A={ai∣i∈ℝ+} and B={bi∣i∈ℝ+}, where a0=0=b0 and A∩B={0}. Let a binary operation *′ on X is defined as follows: for all i,j∈ℝ+,
(3.2)ai*′aj=ai*j;bi*′bj=bi*j;ai*′bj=ai;bi*′aj=bi.
By Example 3.13, (A,*1,0) and (B,*2,0) are two BCK-algebras, where ai*1aj=ai*j and bi*2bj=bi*j, for any i,j∈ℝ+. Hence, by Proposition 2.5, (X,*′,0) is a BCK-algebra and so by Proposition 3.8, G(X) is a connected graph. Let ai∈A-{a0} and bi∈B-{a0}. Since X is a BCK-algebra, then 0∈L({ai,bi}). Let u∈L({ai,bi}), for some u∈X. If u=bj, for some j∈ℝ+, then u=u*′ai=0. If u=aj, for some j∈ℝ+, then u=u*′bi=0. Hence, L({ai,bi})={0} and so aibi∈E(G(X)). Since 0ai,0bi,aibi∈E(G(X)), then G(X) has a cycle and so it is not a tree. But, X does not have any atoms.Proposition 3.15.
LetX be a BCI-algebra such that the set {|V(a)|:a∈P} is bounded. Then, Δ(G(X))=max{|V(a)|-1:a∈P}.Proof.
Since the set{|V(a)|:a∈P} is bounded, then there is a u∈P, such that |V(u)|-1=max{|V(a)|-1:a∈P}. We show that deg(x)≤deg(u), for any x∈X. Let x∈X. Then, there is a∈P such that x∈V(a). Since V(a)∩V(b)=∅, for any b∈P-{a}, then by Proposition 3.8(ii) and Lemma 3.2(i), deg(x)≤|V(a)|-1≤|V(u)|-1=deg(u). Therefore, Δ(G(X))=deg(u)=|V(u)|-1=max{|V(a)|-1:a∈P}.Corollary 3.16.
(i) IfX is a finite BCI-algebra, then Δ(G(X))=max{|V(a)|-1:a∈P}.
(ii) IfX is a finite BCK-algebra, then Δ(G(X))=|X|-1.Proof.
(i) IfX is a finite BCI-algebra, then {|V(a)|:a∈P} is bounded. Therefore, by Proposition 3.15, Δ(G(X))=max{|V(a)|-1:a∈P}.
(ii) IfX is a BCK-algebra, then P={0} and so {|V(a)|-1:a∈P}={V(0)-1}={|X|-1}. Hence, by Proposition 3.15, Δ(G(X))=|X|-1.Definition 3.17.
LetG be a graph with n+1 vertices. Then G is called an n-star graph if it has Figure 4.Figure 4
n-star.Theorem 3.18.
LetX be a BCK-algebra with m+1 elements and only one atom. Then G(X) is an m-star graph. Moreover, if G is an m-star graph, then there is a BCK-algebra X such that G(X)=G.Proof.
Since,X is a BCK-algebra, then G(X) is a connected graph. Let a be an atom of X. Then by Lemma 3.11, a≤x, for all x∈X-{0} and so E(G(X))={0x∣x∈X-{0}}. Therefore, G(X) is a m-star graph. Now, let G be a m-star graph, for some m∈ℕ and X=V(G)={x0,x1,…,xm} be a chain such that xi<xi+1, for any i∈{0,1,…,m-1}. Define the binary operation *′ on X by xi*′xj=xi*j, where i*j=max{0,i-j}, for any i,j∈{0,1,…,m}. By Theorem 2.3, X is a commutative BCK-chain and so L({x,y})≠{0}, for any x,y∈X-{0}. Hence, by Lemma 3.2(i), E(G(X))={x0x1,x0x2,…,x0xm} and so G(X) is an m-star graph.Theorem 3.19.
X is a commutative BCI-algebra and x*y=x*a, for any a∈P and x,y∈V(a), where x≠y if and only if G(X) is a graph with complete components.Proof.
LetG(X) be a graph with complete components, a∈P and x,y∈V(a) such that x≠y. Since x*y∈V(0) by (BCI6), we get x*(x*y)∈L({x,y}). Now, since x,y∈V(a) and G(X) is a graph with complete components, then by Proposition 3.8, xy∈E(G(X)) and so L({x,y})={a}. Hence, x*(x*y)=a and so by (BCI6) and (BCI4), we get x*a≤x*y. On the other hand, since a≤y, then by (BCI7), x*y≤x*a. Therefore, x*y=x*a. Now, we show that X is a commutative BCI-algebra. Let a∈P and x,y∈V(a). Clearly, if x=y, then x*(x*y)=y*(y*x). If x≠y, then x*(x*y)=x*(x*a)≤a. Since a∈P, we get x*(x*a)=a. By the similar way, we get y*(y*x)=a and so x*(x*y)=a=y*(y*x). Hence, X is branchwise commutative. Therefore, by Lemma 2.2, X is commutative BCI-algebra. Conversely, let X be a commutative BCI-algebra such that x*y=x*a, for any a∈P and distinct elements x,y∈V(a). Let a∈P and x,y∈V(a). If u∈L({x,y}), then by (P3), u*a=u*x=0 and so u≤a. Since u∈P, we have a=u. Hence, L({x,y})={a} and so xy∈E(G(X)). Therefore, by Proposition 3.8, all components of G(X) are complete graph.Corollary 3.20.
The graphG(X) is a complete graph if and only if X is a BCK-algebra and
(3.3)x*y={0ify=x,xotherwise.Definition 3.21 (see [10]).
Let(X1,*1,0) be a BCK-algebra and (X2,*2,0) be a BCI-algebra such that X1∩X2={0}. Define the binary operation “*’’ on X1∪X2 by
(3.4)x*y={x*1yifx,y∈X1;x*2yifx,y∈X2;0*2yifx∈X1,y∈X2-{0};xifx∈X2,y∈X1.
The (X1∪X2,*,0) is a BCI-algebra, whose BCK-part B contains X1 and p-semisimple part P is contained in X2. This algebra is called the Li’s union of X1 and X2 and is denoted by X1∪LX2.Lemma 3.22.
Let(X1,*1,0) be a BCK-algebra, (X2,*2,0) be a BCI-algebra such that X1∩X2={0} and Y be the Li’s union of X1 and X2. Then
(3.5)LY({x,y})={LX1({x,y})ifx,y∈X1;LX2({x,y})ifx,y∈X2-VX2(0);LX2({x,y})∪X1ifx,y∈VX2(0)-{0};∅otherwise.Proof.
Ifx,y∈X1, then
(3.6)u∈LX1({x,y})⟺u*1x=u*x=0=u*y=u*1y⟺u∈LY({x,y}).
Hence, LX1({x,y})=LY({x,y}). Let x,y∈VX2(a), for some a∈P-{0}. Then by Definition 3.21, a∈Q-{0}, where Q is a p-semisimple part of Y. Let u∈LY({x,y}). Then by (P3), u∈VY(a) and so u∈X2-{0}. Hence, u*2x=u*x=0=u*y=u*2y and so u∈LX2({x,y}). Now, let u∈LX2({x,y}). Then u*x=u*2x=0=u*2y=u*y and so u∈LY({x,y}). Hence, LX2({x,y})=LY({x,y}), for any a∈P-{0} and x,y∈V(a). If x,y∈VX2(0)-{0}, then u*x=0*2x=0 and u*y=0*2y=0, for any u∈X1. Clearly, by definition of “*’’, LX2({x,y})⊆LY({x,y}) and so LX2({x,y})∪X1⊆LY({x,y}). Let u∈LY({x,y}). Then u*x=0. Since x∈VX2(0)-{0} by definition of “*’’, u∈X1 or u∈LX2({x,y}) and so LY({x,y})⊆LX2({x,y})∪X1. The final part is straight consequent of Lemma 3.2.Proposition 3.23.
Let(X1,*1,0) be a BCK-algebra, (X2,*2,0) be a BCI-algebra such that X1∩X2={0}, X1≠{0} and S={xy∈E(G(X2))∣x,y∈VX2(0)-{0}}. Then G(X1∪LX2)=(G(X1)∪G(X2))-S.Proof.
Clearly,V(G(X1∪LX2))=X1∪X2=V((G(X1)∪G(X2))-S). Let Y=X1∪LX2, Q be a p-semisimple part of Y and xy∈E(G(Y)). Then x≠y and LY{x,y}={a}, for some a∈Q. If a≠0, then by Definition 3.21, x,y∈X2 and so by Lemma 3.22, LX2({x,y})={a}. Hence, xy∈E(G(X2)-S)⊆E((G(X1)∪G(X2))-S). Let a=0. Then LY({x,y})={0} and so x,y∈VY(0)=VX1(0)∪VX2(0). If x,y∈VX1(0), then by Lemma 3.22, xy∈E(G(X1))⊆E((G(X1)∪G(X2))-S). If x=0 or y=0, then clearly, xy∈E(G(X1)∪G(X2)-S). If x,y∈VX2(0)-{0}, then by Lemma 3.22, LX2({x,y})∪X1⊆LY({x,y})={0} and so X=0, which is impossible. If x∈VX1(0)-{0} and y∈VX2(0)-{0}, then x*y=0*y=0 and so x∈LY({x,y})={0}, which is impossible. By the similar way, we get that x∈VX2(0)-{0} and y∈VX1(0)-{0} is impossible. Hence, E(G(Y))⊆E(G(X1)∪G(X2)-S). Now, let xy∈E((G(X1)∪G(X2))-S). Then x≠y and xy∈E(G(X1)) or xy∈E(G(X2)-S). By Lemma 3.22, E(G(X1))⊆E(G(Y)). Let xy∈E(G(X2)-S). Then LX2({x,y})={a}, for some a∈P2 and a∉S, where P2 is a p-semisimple part of X2. If a≠0, then a∈Q-{0} and by Lemma 3.22, LY({x,y})={a}. Hence, by Lemma 3.2, xy∈E(G(Y)). If a=0, then x,y∈VX2(0) and so xy∈E(G(X2)-S) implies x=0 or y=0. Hence, xy∈E(G(Y)). Therefore, E((G(X1)∪G(X2))-S)⊆E(G(Y)) and so E((G(X1)∪G(X2))-S)=E(G(Y)).Corollary 3.24.
Let(X1,*1,0) be a BCK-algebra, (X2,*2,0) be a BCI-algebra such that X1∩X2=∅ and the graph G(VX2(0)) be a tree. Then G(X1∪LX2)=G(X1)∪G(X2).Proof.
IfX1={0}, then X2=X1∪LX2 and so G(X1∪LX2)=G(X2)=G(X1)∪G(X2). Now, let G(VX2(0)) be a tree. Then for any distinct elements x,y∈VX2(0)-{0}, we have xy∉E(G(VX2(0)). Hence, by Proposition 3.8(ii), xy∉E(G(X2)) and so S=∅, where S={xy∈E(G(X2))∣x,y∈VX2(0)-{0}}. Therefore, by Proposition 3.23, G(X1∪LX2)=G(X1)∪G(X2).Example 3.25.
(i) LetX1={0,a,b,c} and X2={0,1,2,3}. Define the binary operations *1 and *2 on X1 and X2, respectively, by the following tables:
Then (X1,*1,0) and (X2,*2,0) are BCK-algebras (see [10]). Also, G(X1), G(X2) and G(X1)∪G(X2) are given by Figure 5.
LetY=X1∪LX2. Then LY({x,0})={0}, for any x∈Y. Hence, by Lemma 3.22, x∈LY({x,y}) and LY({0,z})={0}=LY({a,b}), for any x∈{1,2,3}, z∈X1 and y∈{a,b,c}. Moreover, X1⊆LY({a,b})∩LY({a,c})∩LY({b,c}). Hence, E(G(Y))={0x∣x∈Y-{0}}∪{ab} and so G(Y) is given by Figure 6.
IfS is the set was defined in the Proposition 3.23, then S={13,23}. Therefore, G(Y)=G(X1)∪(G(X2)-S).
(ii) LetX be the BCI-algebra was defined in Example 3.6(i) and X1 be the BCK-algebra in (i). Then the BCK-part of X2 is a tree. Hence, by Corollary 3.24, G(X1∪LX)=G(X1)∪G(X).Figure 5Figure 6Lemma 3.26.
Let(X,*1,0) and (Y,*2,0) be two BCK-algebras and x,y∈X⊕Y. Then
(3.7)LX⊕Y{x,y}={LX{x,y}ifx,y∈X;LY{x,y}ifx,y∈Y;{0}otherwise.Proof.
Letx,y∈X∪Y.(1)
Ifx,y∈X, then for any u∈LX{x,y}, we have u*x=0=u*y. If u∈Y, then by Proposition 2.5, u=u*x=0 and so u∈X. Moreover, if u∈X, then u*1x=u*x=0 and u*1y=u*y=0 and so u∈LX{x,y}. Hence, LX⊕Y{x,y}⊆LX{x,y}. Now, let u∈LX{x,y}. Then u,x,y∈X and u*1x=0=u*1y and so u*x=u*1x=0=u*1y=u*y. Hence, LX{x,y}⊆LX⊕Y{x,y}. Therefore, LX⊕Y{x,y}=LX{x,y}, for all x,y∈X. By the similar way, we can prove that LX⊕Y{x,y}=LY{x,y}, for all x,y∈Y.(2)
Ifx∈X and y∈Y. Since X⊕Y is a BCK-algebra, we have 0∈LX⊕Y{x,y}. Let u∈LX⊕Y{x,y}. Then u*x=0=u*y. Since x∈X and y∈Y, then by definition of “*’’, we have u*x=u or u*y=u and so u=0. Therefore, LX⊕Y{x,y}={0}. By the similar way, if x∈Y and y∈X, then we can prove that LX⊕Y{x,y}={0}.Theorem 3.27.
Let(X,*1,0) and (Y,*2,0) be two BCK-algebras. Then G(X⊕Y)-{0}=(G(X)-{0})+(G(Y)-{0}).Proof.
Clearly,V(G(X⊕Y)-{0})=V((G(X)-{0})+(G(Y)-{0})). Let xy∈E(G(X⊕Y)-{0}). Then x≠0, y≠0 and LX⊕Y{x,y}={0}. If x,y∈X or x,y∈Y, then by Lemma 3.26, LX{x,y}={0} or LY{x,y}={0} and so xy∈E(G(X)-{0}) or xy∈E(G(Y)-{0}). Hence, by Definition 2.8, xy∈E((G(X)-{0})+(G(Y)-{0})). If x∈X and y∈Y or x∈Y and y∈X, then x∈V((G(X)-{0})) and y∈V(G(Y)-{0}) and so xy∈E((G(X)-{0})+(G(Y)-{0})). Now, let xy∈E((G(X)-{0})+(G(Y)-{0})). Then xy∈E(G(X)-{0})∪E(G(Y)-{0}) or x∈X-{0} and y∈Y-{0}. If xy∈E(G(X)-{0})∪E(G(Y)-{0}), then x≠0, y≠0 and LX{x,y}={0} or LY{x,y}={0}. Hence, by Lemma 3.26, xy∈E(G(X⊕Y)-{0}). If x∈X-{0} and y∈Y-{0}, then by Lemma 3.26, LX⊕Y={0} and so xy∈E(G(X⊕Y)-{0}). Therefore, E(G(X⊕Y)-{0})=E((G(X)-{0})+(G(Y)-{0})).Corollary 3.28.
Let(X,*1,0) and (Y,*2,0) be two finite BCK-algebras. Then |E(X⊕Y)|=(|X|+|Y|-1)+(|X|-1)·(|Y|-1).Proof.
Straightforward.Example 3.29.
LetX={a0,a1,a2,a3}, Y={b0,b1,b2}, a0=b0 and “*’’ be the operation was defined in Example 3.13. Then (X,*1,a0) and (Y,*2,b0) are BCK-chain, where ai*1aj=ai*j and bi*1bj=bi*j. Since they are BCK-chain, then by Lemma 3.2, G(X) is 3-star graph and G(Y) is 2-star graph and so G(X)-{0} and G(Y)-{0} have Figure 7.
Hence, by Definition2.8, (G(X)-{0})+(G(Y)-{0}) is given by Figure 8.
On the other hand, by Lemma3.26, G(X⊕Y) is given by Figure 9 and so G(X⊕Y)-{0} is the graph on Figure 8.Figure 7Figure 8
(G(X)-{0})+(G(Y)-{0}).Figure 9
G(X⊕Y)-{0}.LetI be an ideal of X. Define a binary relation θ on X as follows: (x,y)∈θ if and only if x*y,y*x∈I, for all x,y∈X. Then, θ is a congruence relation and it is called the equivalence relation induced by I. If X/I={[x]∣x∈X}, then (X/I,*,[0]) is a BCI-algebra, where [x]*[y]=[x*y], for all x,y∈X (see [10]). Moreover, let G=(V,E) be a graph and Π be a partition of X. The graph whose vertexes are the elements of Π and for distinct elements u,v∈Π, there is an edge connecting u and v if and only if xy∈E, for some x∈u and y∈v, is denoted by G/Π. Now, we want to verify the relation between the G(X/I) and G(X)/Π, where I is an ideal of X, θ is a congruence relation induced by I and Π is a partition induced by θ.Theorem 3.30.
LetI be an ideal of X and Π be the partition of X induced by I.(i)
IfX is a BCK-algebra, then G(X)/Π is a subgraph of G(X/I).(ii)
IfX/I is a commutative BCI-algebra, then G(X)/Π is a subgraph of G(X/I).Proof.
(i) Clearly,V(G(X/I))={[x]∣x∈X}=V(G(X)/Π). Let [x][y]∈E(G(X)/Π). Then there are u∈[x] and v∈[y], such that uv∈E(G(X)). Hence, LX{u,v}={0}. Let [z]∈LX/I{[x],[y]}. Since [u]=[x] and [v]=[y], then [z*u]=[z]*[u]=[0]=[z]*[v]=[z*v] and so z*u∈I and z*v∈I. Hence, z*u=a and z*v=b, for some a,b∈I. Since X is a BCK-algebra, then by (BCI6), (z*a)*b∈LX{u,v}={0}. Since I is an ideal of X and a,b∈I, then z∈I and so z*0∈I and 0*z=0∈I. Hence, [z]=[0] and so LX/I{[x],[y]}={[0]}. Therefore, [x][y]∈E(G(X/I)) and so G(X)/Π is a subgraph of G(X/I).
(ii) Clearly,V(G(X/I))={[x]∣x∈X}=V(G(X)/Π). Let [x][y]∈E(G(X)/Π). Then there are u∈[x] and v∈[y], such that uv∈E(G(X)) and so LX{u,v}={a}, for some a∈P. Since u,v∈V(a), then by (P2), v*u,u*v∈V(0) and so by (BCI6), v*(v*u),u*(u*v)∈LX{u,v}={a}. Hence, v*(v*u)=a=u*(u*v) and so [v]*([v]*[u])=[a]=[u]*([u]*[v]). Let [z]∈LX/I{[x],[y]}. Then by (P3), [z]∈VX/I([a]). Since X/I is a commutative BCI-algebra, then by Lemma 2.2, [v]*([v]*[z])=[z]*([z]*[v])=[z] and so by (BCI7), we have [z]=[v]*([v]*[z])≤[v]*([v]*[u])=[a]. Clearly, a∈Q, where Q is a p-semisimple part of X/I. Hence, [a]=[z] and so LX/I{[x],[y]}={[a]}. Therefore, [x][y]∈E(G(X/I)) and so G(X)/Π is a subgraph of G(X/I).Example 3.31.
LetY={0,1,2,a,b} and X={0,1,2,3,4}. Define the binary operations “*1’’ and “*2’’ on Y and X, respectively by the following tables:
(i)
It is easy to see that(Y,*1,0) is a BCI-algebra and J={0,1} is an ideal of Y (see [10, Example 2.5.5]). Moreover, [0]={0,1,a,b} and [2]={2}. Hence, Y/J={[0],[2]} is a commutative BCI-algebra and so E(G(Y/I))={[0][2]}. Moreover, Since LY{2,0}={0}, then [0][2]∈E(G(X)/Φ, where Φ is the partition of Y induced by J. Therefore, G(X/J)=G(X)/Φ.(ii)
We can prove that(X,*2,0) is a BCK-algebra and I={0,1,2} is an ideal of X (see [10]). Moreover, X/I={[0],[3],[4]}, where [0]={0,1,2}, [3]={3} and [4]={4}. It is easy to check that E(G(X/I))={[0][3],[0][4],[3][4]} and E(G(X)/Π)={[0][3],[0][4]}.


## 4. Characteristic Polynomials of Graphs ofBCI-Algebras

In this section, we verify the characteristic polynomials of graph ofBCI-algebras. Then we fined the relation between Characteristic polynomial of G(X) and Characteristic polynomial of graphs of branches of X, for any BCI-algebra X.Theorem 4.1.
LetX be a finite BCI-algebra. Then χ(G(X),λ)=∏a∈Pχ(G(V(a)),λ).Proof.
Letm∈ℕ, P={a1,…,am}, V(at)={x1,t,…,xrt,t} and At=[bi,j] be the adjacency matrix of G(V(ai)), for all t∈{1,2,…,m}. Then X={x1,1,x2,1,…,xr1,1,x1,2,x2,2,…,xr2,2,…,x1,m,x2,m,…,xrm,m}. Since V(ai)∩V(aj)=∅, for all distinct i,j∈{1,2,…,m}, then by Proposition 3.8(ii), the adjacent matrix of G(X) is of the form
(4.1)[A10⋯00A2⋯0⋮⋮⋱⋮00⋯Am],
where Aj is a mj×mj matrix, for all j∈{1,2,…,m}. By the properties of determinant, we have χ(G(X),λ)=det(λI-A)=det(λI1-A1)×det(λI2-A2)×⋯×det(λIm-Am)=∏a∈Pχ(G(V(a)),λ), where Ij is a mj×mj identity matrix, for all j∈{1,2,…,m}.Corollary 4.2.
LetX be a finite BCI-algebra and t is the number of elements a∈P such that |V(a)|=1.(i)
χ(G(X),λ)=λt×f(λ), for some polynomial f(λ).(ii)
X is a p-semisimple BCI-algebra if and only if χ(G(X),λ)=λn, for some n∈ℕ.Proof.
(i) Let|X|=n and {a1,…,at} be the set of all elements of P such that |V(ai)|=1, for all i∈{1,2,…,t}. Then by using the proof of Theorem 4.1, the adjacent matrix of G(X) is of the form
(4.2)[B000]n×n,
where B is an (n-t×n-t) matrix. Hence, by properties of determinant, we have χ(G(X),λ)=det(λIt)×det(λIn-t-B)=λt×det(λIn-t-B). Let f(λ)=det(λIn-t-B), then χ(G(X),λ)=λt×f(λ).
(ii) SinceX is a p-semisimple BCI-algebra, then |V(a)|=1, for all a∈X. Therefore, by (i), χ(G(X),λ)=λn, where |X|=n. Conversely, let χ(G(X),λ)=λn, for some n∈ℕ. Then by Proposition 2.11, G(X) is an empty graph. Therefore, by Theorem 3.9, X is a p-semisimple algebra.Theorem 4.3.
LetX be a finite BCI-algebra and a∈P. If χ(G(V(a)),λ)=λn+c1λn-1+c2λn-2+⋯+cn-1λ+cn, for some n∈ℕ, then(i)
c1=0 and 2c2=-∑x∈X|Zx|+|P|,(ii)
letA be the set of all {x,y,z}⊆X such that x,y,z are distinct elements of X and u*v=u*a, for all u,v∈{x,y,z} and some a∈P. If X is a commutative BCI-algebra, then c3=-2|A|.Proof.
(i) By Proposition2.11, c1=0. If x∈X-P, then by Lemma 3.2,
(4.3)deg⁡(x)=|{y∈X-{x}∣L{x,y}=a,forsomea∈P}|=|Zx|.
Now, if x∈P, then by Lemma 3.2, deg(x)=|{y∈X-{x}|L{x,y}=a,forsomea∈P}|=|Zx|-1. Hence, by Proposition 2.11, we have
(4.4)2c2=-2|E(G(X))|=-deg⁡(G)=-(∑x∈X-P|Zx|+∑x∈P(|Zx|-1))=-∑x∈X|Zx|+|P|.
(ii) By Proposition2.11, c3=-2t, where t is the number of triangles of G(X). Since by Proposition 3.8, G(X)=⋃a∈PG(V(a)) and V(a)∩V(b)=∅, for any distinct elements a,b∈P, then t=∑a∈Pta, where ta is the number of triangles of G(V(a)), for all a∈P. Now, let a∈P and x,y,z be three vertexes of a triangles of G(V(a)). Then x,y,z are distinct elements of X and L{x,y}=L{x,z}=L{y,z}={a}. Since x*(x*y)∈L{x,y}, then x*(x*y)=a and so by (BCI4) and (BCI6), x*a≤x*y. Moreover, a≤y and (BCI7), imply x*y≤x*a and so x*y=x*a. By the similar way, we can prove that x*z=x*a, y*z=y*a=y*x and z*x=z*a=z*y. Hence, {x,y,z}∈A. Conversely, let {x,y,z}∈A. Then there exists a∈P such that u*v=u*a, for any u,v∈{x,y,z}. Let u,v∈{x,y,z} and w∈L{u,v}. Then by (P2), w∈V(a). Since X is commutative, then by Lemma 2.2, (BCI6) and (BCI7), w=w*0=w*(w*u)=u*(u*w)≤u*(u*v)=u*(u*a)≤a. Hence, w=a (since a∈P), and so L{u,v}={a}. Therefore, xy,xz,yz∈E(G(V(a))) and so x,y,z are three vertexes of a triangle of G(V(a)), for some a∈P. Hence, t=∑a∈Pta=|A|. This complete the proof.



---

*Source: 126835-2012-02-15.xml*