Printer Friendly

End-completely-regular and end-inverse lexicographic products of graphs.

1. Introduction and Preliminary Concepts

Endomorphism monoids of graphs are generalizations of automorphism groups of graphs. In recent years, much attention has been paid to endomorphism monoids of graphs and many interesting results concerning graphs and their endomorphism monoids have been obtained. The aim of this research is to develop further relationship between graph theory and algebraic theory of semigroups and to apply the theory of semigroups to graph theory. The bipartite graph is a class of famous graphs. Their endomorphism monoids are studied by several authors. In [1], the connected bipartite graphs whose endomorphism monoids are regular were explicitly found. In [2], Fan gave a characterization of connected bipartite graphs with an orthodox monoid. The joins of bipartite graphs with regular endomorphism monoids were characterized in [3]. The joins of bipartite graphs with completely regular endomorphism monoids were characterized in [4]. The endomorphism monoids and endomorphism regularity of graphs were considered by several authors (see [5-8]). In this paper, we will characterize the End-completely-regular and End-inverse lexicographic products of two graphs. We give several approaches to construct new End-completely-regular graphs by means of the lexicographic products of two graphs with certain conditions. In particular, we will determine the End-completely-regular and End-inverse lexicographic products of bipartite graphs.

The graphs X considered in this paper are undirected finite simple graphs. The vertex set of X is denoted by V(X) and the edge set of X is denoted by E(X). If two vertices [x.sub.1] and [x.sub.2] are adjacent in X, the edge connecting [x.sub.1] and [x.sub.2] is denoted by [[x.sub.1], [x.sub.2]] and we write [[x.sub.1],[x.sub.2]] [member of] E(X). A subgraph H is called an induced subgraph of X if for any a,b [member of] V(H), {a, b} [member of] E(H) if and only if {a, b} [member of] E(X). A graph X is called bipartite if X has no odd cycle. It is known that if a graph X is a bipartite graph, then its vertex set can be partitioned into two disjoint nonempty subsets such that no edge joins two vertices in the same set.

Let X and Y be two graphs. The join of X and Y, denoted by X + Y, is a graph such that V(X + Y) = V(X) [union] V(Y) and E(X + Y) = E(X) [union] E(Y) [union] {{[x.sub.1], [x.sub.2]} | [x.sub.1] [member of] V(X), [x.sub.2] [member of] Y(Y)}. The lexicographic product of X and Y, denoted by X[Y], is a graph with vertex set Y(X[Y]) = V(X) x Y(Y), and with edge set E(X[Y]) = {{(x, y),([x.sub.1], [y.sub.1])} | {x,[x.sub.1]} [member of] E(X), or x = [x.sub.1] and {y, [y.sub.1]} [member of] E(Y)}. Denote [Y.sub.x] = {(x, y) | y [member of] V(Y)} for any x [member of] V(X).

Let X and Y be graphs. A mapping f from V(X) to V(Y) is called a homomorphism (from X to Y) if {[x.sub.1],[x.sub.2]} [member of] E(X) implies that {f([x.sub.1]), f([x.sub.2])} [member of] E(Y). A homomorphism f is called an isomorphism if f is bijective and [f.sup.-1] is a homomorphism. A homomorphism (resp., isomorphism) f from X to itself is called an endomorphism (resp., automorphism) of X (see [9]). The sets of all endomorphisms and automorphisms of X are denoted by End(X) and Aut(X),respectively. A graph X is said to be unretractive if End(X) = Aut(X). For any f [member of] End(X), it is easy to see that f [member of] Aut(X) if and only if f is injective.

A retraction of a graph X is a homomorphism f from X to a subgraph Y of X such that the restriction f[|.sub.Y] of f to V(Y) is the identity mapping on V(Y). In this case, Y is called a retract of X. It is known that the idempotents of End(X) are retractions of X. Denote by Idpt(X) the set of all idempotents of End(X). Let f be an endomorphism of a graph X. A subgraph of X is called the endomorphic image of X under /, denoted by [I.sub.f], if V([I.sub.f]) = f(V(X)) and {f(a), f(b)} [member of] E(If) if and only if there exist c [member of] [f.sup.-1](f(a)) and d [member of] [f.sup.-1](f(b)) such that {c, d} [member of] E(X). By [[rho].sub.f] we denote the equivalence relation on V(X) induced by f; that is, for a,b [member of] V(X), (a, b) [member of] [[rho].sub.f] if and only if f(a) = f(b). Denote by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the equivalence class containing a [member of] V(X) with respect to [[rho].sub.f].

An element a of a semigroup S is called regular if there exists x [member of] S such that axa = a. An element a of a semigroup S is called completely regular if a = axa and xa = ax hold for some x [member of] S. A semigroup S is called regular (resp., completely regular) if all its elements are regular (resp., completely regular). An inverse semigroup is a regular semigroup in which the idempotents commute. A graph X is said to be End-regular (resp., End-completely-regular, End-inverse) if its endomorphism monoid End(X) is regular (resp., completely regular, inverse). Clearly, End-completely-regular graphs as well as End-inverse graphs are End-regular.

For undefined notation and terminology in this paper, the reader is referred to [9-14]. We list some known results which will be used in the sequel.

Lemma 1 (see [2]). If X[Y] is End-regular, then both X and Y are End-regular.

Lemma 2 (see [15]). Let G be a graph and let f [member of] End(G). Then f is completely regular if and only if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Aut(If).

Lemma3 (see [15]). Let X be a bipartite graph. Then X is End-completely-regular if and only if X is one of [K.sub.1], [K.sub.2], [P.sub.2], 2[K.sub.1], 2[K.sub.2], and [K.sub.1] [union] [K.sub.2].

Lemma 4 (see [4]). Let X and Y be two bipartite graphs. Then X + Y is End-completely-regular if and only if one of them is End-completely-regular and the other is [K.sub.1] or [K.sub.2].

Lemma 5 (see [16]). Let G be a graph and f [member of] End(G). Then f is completely regular if and only if there exists g [member of] Idpt(G) such that [[rho].sub.g] = [[rho].sub.f] and [I.sub.g] = [I.sub.f].

Lemma 6 (see [4]). Let X be a bipartite graph. Then X is End-inverse if and only if X = [K.sub.1] or X = [K.sub.2].

Lemma 7 (see [17]). Let X and Y be two graphs. Then End(X[Y]) = End(X)[End(Y)] if and only if for any f [member of] End(X[Y]) and x [member of] V(X), there exists x [member of] V(X) such that f([Y.sub.x]) [subset or equal to] [Y.sub.x'].

2. Main Results

In this section, we will characterize the End-completely-regular and End-inverse lexicographic products of two graphs. We first show that if X[Y] is End-completely-regular, then both X and Y are End-completely-regular.

Theorem 8. Let X and Y be two graphs. If X[Y] is End-completely-regular, then both X and Y are End-completely-regular.

Proof. By Lemma 2, to show that X is End-completely-regular, it is only necessary to verify that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is an automorphism of [I.sub.f] for each f [member of] End(X). Define a mapping F from V(X[Y]) to itself by

F((x,y)) = (f(x),y) [for all](x,y) [member of] V(X[Y]). (1)

Then F [member of] End(X[Y]). Since X[Y] is End-completely-regular, by Lemma 2, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is an automorphism of IF. It is easy to see that [I.sub.F] = [I.sub.f][Y]. For any distinct [x.sub.1],[x.sub.2] [member of] V([I.sub.f]) and y [member of] V(Y), F(([x.sub.1], y)) = (f([x.sub.1]), y) and F(([x.sub.2], y)) = (f([x.sub.1]), y) hold. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is an automorphism of IF, (f([x.sub.1]), y) = (f([x.sub.2]),y). Hence f'([x.sub.1]) = f([x.sub.2]) and so [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is an automorphism of If.

Let g [member of] End(Y). Define a mapping G from Y(X[Y]) to itself by

G((x,y)) = (x,g(y)) [for all] (x, y) [member of] V (X [Y]). (2)

Then G [member of] End(X[Y]).Since X[Y] is End-completely-regular, by Lemma 2, is an automorphism of IG. It is easy to see that [I.sub.G] = X[[I.sub.g]]. For any x [member of] V(X) and [y.sub.1], [y.sub.2] [member of] V([I.sub.g]), G((x, [y.sub.1]) = (x, g([y.sub.1]) and G((x, [y.sub.2])) = (x, g([y.sub.2])). Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is an automorphism of [I.sub.G], (x, g([y.sub.1])) = (x, g([y.sub.2])), we get that g([y.sub.1]) [not equal to] g([y.sub.2]) and so [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is an automorphism of [I.sub.g], as required.

The following example shows that X and Y being End-completely-regular does not yield that X[Y] is End-completely-regular.

Example 9. Let X and Y be two graphs with V(X) = {[x.sub.1],[x.sub.2]}, V(Y) = {[y.sub.1], [y.sub.2]}, E(X) = {{[x.sub.1], [x.sub.2]}}, and E(Y) = [phi]. By Lemma 3, X and Y are End-completely-regular. It is easy to see that X[Y] [congruent to] [C.sub.4]. Also by Lemma 3, this is not End-completely-regular.

In the following, we give some sufficient conditions for X[Y] to be End-completely-regular. To this aim, we need the following result due to Fan [17].

Lemma 10 (see [17]). Let X and Y be two [K.sub.3]-free connected graphs. If girth(X) or girth(Y) is odd, then End(X[Y]) = End(X)[End(Y)], where End(X)[End(Y)] is the wreath product of the monoids End(X) and End(Y).

Let X and Y be two [X.sub.3]-free connected graphs such that girth(X) or girth(Y) is odd. In [2], Fan proved that if both of X and Y are End-regular and one of them is unretractive, then X[Y] is End-regular. Here we prove that if X is an End-completely-regular graph and Y is an unretractive graph, then X[Y] is End-completely-regular.

Theorem 11. Let X and Y be two [K.sub.3]-free connected graphs with girth(X) or girth(Y) being odd, and assume that

(1) X is End-completely-regular,

(2) Y is unretractive.

Then X[Y] is End-completely-regular.

Proof. Let X and Y be two graphs satisfying the assumptions. To show that X[Y] is End-completely-regular, we prove that for any F [member of] End(X[7]), there exists an idempotent endomorphism G [member of] End(X[7]) such that [[rho].sub.F] = [[rho].sub.G] and [I.sub.F] = [I.sub.G].

Let F [member of] End(X)[End(7)]. Since End(X[X]) =

End(X)[End(X)], F = (s, f) for some s [member of] End(X) and f [member of] End[(Y).sup.V(X)]. Thus, for any u [member of] V(X), there exists [f.sub.u] = f(u) [member of] End(Y). Let X and Y be [X.sub.3]-free connected graphs with girth(X) or girth(Y) being odd. By Lemma 7, for any m [member of] V(X), F([Y.sub.u]) [subset or equal to] [Y.sub.v] for some v [member of] V(X). Note that 7 is unretractive. Then F([Y.sub.u]) = [Y.sub.v]. Since X is End-completely-regular and s [member of] End(X), by Lemma 5, there exists t [member of] Idpt(X) such that [[rho].sub.t] = [[rho].sub.s] and It = [I.sub.s]. Clearly, [I.sub.s] is an induced subgraph of X. Hence [I.sub.F] = [I.sub.s][7] is an induced subgraph of X[Y].

Since X is End-completely-regular, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is an automorphism of [I.sub.s]. Thus for any u [member of] [I.sub.s], there exists only one vertex [u.sub.1] [member of] Is such that s([u.sub.1]) = u. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Now for any (u, v) [member of] [I.sub.F], there exists only one vertex ([u.sub.1], [v.sub.1]) [member of] [I.sub.F] such that F(([u.sub.1], [v.sub.1])) = (u, v). Define a mapping G from V(X[Y]) to itself in the following way. If (x, y) [member of] V([I.sub.F]), then G((x, y)) = (x, y); if (x, y) [not equal to] V([I.sub.F]), then F((x,y)) = (u, v) for some (u, v) [member of] V([I.sub.F]). Now let G((x,y)) = ([u.sub.1], [v.sub.1]), where ([u.sub.1], [v.sub.1]) is the only vertex in V([I.sub.F]) such that F(([u.sub.1])), [v.sub.1])) = (u, v). Then it is easy to see that G is well-defined. Let (x, y) [member of] 7(X[7]). If (x, y) [member of] V([I.sub.F]), then x [member of] Is. Thus t(x) = x. Hence G((x, y)) = (x,y) [member of] [Y.sub.t](x). If (x,y) [not member of] V([I.sub.F]), then t(x) = (([u.sub.1])). Hence G((x,y)) = ([u.sub.1], [v.sub.1]) [member of] [Y.sub.t](x). Therefore, G((x,y)) [member of] [Y.sub.t](x) for any (x,y) [member of] 7(X[7]).

Let ([x.sub.1],[y.sub.1]), ([x.sub.2], [y.sub.2]) [member of] V(X[Y]) be such that {([x.sub.1], [y.sub.1]), ([x.sub.2], [y.sub.2])} [member of] E(X[Y]). If ([x.sub.1],[y.sub.1]),([x.sub.2],[y.sub.2]) [member of] V([I.sub.F]), then {G(([x.sub.1], [y.sub.1])), G(([x.sub.2], [y.sub.2]))} = {([x.sub.1], [y.sub.1]), ([x.sub.2], [y.sub.2])} [member of] E(X[Y]). If ([x.sub.1], [y.sub.1]) [member of] V([I.sub.F]) and ([x.sub.2], [y.sub.2]) [not member of] V([I.sub.F]), then [x.sub.1] [not equal to] [x.sub.2] and {[x.sub.1], [x.sub.2]} [member of] E(X). Thus [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since t [member of] Idpt(X) and {[x.sub.1],[x.sub.2]} [member of] E(X), {t([x.sub.1]), t([x.sub.2])} [member of] E(X). Hence {G(([x.sub.1], [y.sub.1])), G(([x.sub.2], [y.sub.2]))} [member of] E(X[Y]). If ([x.sub.1], [y.sub.1]) [not member of] V([I.sub.F]) and ([x.sub.2], [y.sub.2]) [not member of] V([I.sub.F]), there are two cases.

Case 1. Assume that {[x.sub.1],[x.sub.2]} [member of] E(X). Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since t [member of] Idpt(X) and {[x.sub.1], [x.sub.2]} [member of] E(X), {t([x.sub.1]), t([x.sub.2])} [member of] E(X). Hence we have {G(([x.sub.1], [y.sub.1])), G(([x.sub.2],[y.sub.2]))} [member of] E(X[7]).

Case 2. Assume that [x.sub.1] = [x.sub.2] and {[y.sub.1], [y.sub.2]} [member of] E(Y). Then we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is an isomorphism from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Therefore, G [member of] End(X[Y]).

If (x,y) [member of] V([I.sub.F]), then [G.sup.2]((x, y)) = G((x,y)) = (x,y). If (x,y) [not member of] V([I.sub.F]), then G((x,y)) [member of] V([I.sub.F]). Thus [G.sup.2]((x,y)) = G(G((x,y)) = G((x, y)). Hence G [member of] Idpt(X[Y]). Clearly, [I.sub.G] = [I.sub.F].

Suppose [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some ([x.sub.1], [y.sub.1]), ([x.sub.2], [y.sub.2]),... ,([x.sub.k], [y.sub.k]) [member of] Y(X[7]). In fact, it is easy to prove that [[rho].sub.F] [subset or equal to] [[rho].sub.G] [subset or equal to] [[rho].sub.p]. Let ([x.sub.1], [y.sub.1])[[rho].sub.F]([x.sub.2], [y.sub.2]). Then, by the definition of G, we have G([x.sub.1],[y.sub.1]) = G(([x.sub.2],[y.sub.2])) = ([u.sub.1], [v.sub.1]) for some ([u.sub.1], [v.sub.1]) [member of] V([I.sub.F]) with F([x.sub.1],[y.sub.1]) = F([u.sub.1], [v.sub.1]) = F(([x.sub.2],[y.sub.2])). So ([x.sub.1],[y.sub.1])[[rho].sub.G]([x.sub.2],[y.sub.2]) and thus [[rho].sub.F] [subset or equal to] [[rho].sub.G] [subset or equal to] [[rho].sub.F]. Hence [[rho].sub.P] = [[rho].sub.G].

Next we start to seek the conditions for bipartite graphs X and Y under which X[7] is End-completely-regular.

Lemma 12. Let X be a graph and R be a retract of X. If R[Y] is not End-completely-regular, then X[7] is not End-completely-regular.

Proof. Let R be a retract of X. Then there exists f [member of] Idpt(X) such that [I.sub.f] = R. Let g [member of] End(R[Y]). Since R[Y] is not End-completely-regular, there exists g [member of] End(R[Y]) such that g is not completely regular. By Lemma 2, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is not an automorphism of [I.sub.g]. Thus there exist [x.sub.1],[x.sub.2] [member of] [I.sub.g] with [x.sub.1] = [x.sub.2] such that g([x.sub.1]) = g([x.sub.2]). Define a mapping F from V(X[7]) to itself by

F((x,y)) = (f(x),y) [for all] (x,y) [member of] V (X[Y]). (3)

Then F [member of] End(X[7]) and [I.sub.F] = R[Y]. Now it is easy to see that gF [member of] End(X[7]) and [I.sub.gF] = [I.sub.g]. It follows from (gF)([x.sub.1]) = (gF)([x.sub.2]) that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is not an automorphism of [I.sub.gF]. Hence X[Y] is not End-completely-regular.

Lemma 13. Let X and Y be two graphs. If at least one of X and Y is not End-completely-regular, then X [union] Y is not End-completely-regular (where X [union] Y is the disjoint union of X and Y).

Proof. Without loss of generality, we may suppose that X is not End-completely-regular. By Lemma 2, there exists f [member of] End(X) such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is not an automorphism of [I.sub.f]. Define a mapping F from T(X [union] Y) to itself by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (4)

Then F [member of] End(X [union] 7). Now it is easy to see that [I.sub.F] = [I.sub.f] [union] Y and F(x) = f(x) for any x [member of] V(X). Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is not an automorphism of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is not an automorphism of [I.sub.F]. Hence X [union] Y is not End-completely-regular.

Theorem 14. Let X and Y be two bipartite graphs. Then X[7] is End-completely-regular if and only if

(1) X = [K.sub.1] and Y is End-completely-regular or

(2) X is End-completely-regular and Y = [K.sub.1] or [K.sub.2].

Proof

Sufficiency. Since [K.sub.1][Y] = Y and X[[K.sub.1]] = X, we have immediately that [K.sub.1] [Y](X[[K.sub.1]]) is End-completely-regular if and only if Y(X) is End-completely-regular. If X = Y = [K.sub.2], then X[Y] = [K.sub.4]. Thus End(X[Y]) is a group. Since any group is a completely regular semigroup, X[Y] is End-completely-regular. If X = 2[K.sub.1] and Y = [K.sub.2], then X[Y] = 2[K.sub.2]. By Lemma 3, it is End-completely-regular. In the following, we show that X[Y] is End-completely-regular for the following cases (see Figure 1).

Case 1. X = [P.sub.2] and Y = [K.sub.2]. Let f [member of] End(X[Y]). If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Otherwise, f([x.sub.2]) = f([z.sub.1]) or f([x.sub.2]) = f([z.sub.2]). Without loss of generality, we can suppose f([x.sub.2]) = f([z.sub.1]). Since [z.sub.1] is adjacent to every vertex of {[z.sub.2], [y.sub.1], [y.sub.2]} and {[x.sub.1], [x.sub.2]} [member of] E(X[Y]), f([z.sub.1]) is adjacent to every vertex of {f([z.sub.2]), f([y.sub.1]), f([y.sub.2]), f([x.sub.1])}. Note that there is no vertex in X[Y] adjacent to 4 vertices. This is a contradiction. Hence f [member of] Aut(X[Y]) and so f is completely regular. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Without loss of generality, we can suppose f([x.sub.1]) = f([z.sub.1]). Then f([x.sub.2]) = f([z.sub.2]). Otherwise, a similar argument as above will show that f([x.sub.1]) is adjacent to every vertex of {f([x.sub.2]), f([y.sub.1]), f([y.sub.2]), f([z.sub.2])}, which yield a contradiction. Thus If [congruent to] [K.sub.4]. Since any endomorphism f maps a clique to a clique of the same size, f([I.sub.f]) = [I.sub.f]. By Lemma 2, f is completely regular. Hence [P.sub.2][[K.sub.2]] is End-completely-regular.

Case 2. X = [K.sub.1] [union] [K.sub.2] and Y = [K.sub.2]. Let f [member of] End(X[Y]). If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Otherwise, f([c.sub.2]) [member of] {f([a.sub.1]), f([a.sub.2]), f([b.sub.1]),f([b.sub.2])}. Without loss of generality, we can suppose f([c.sub.2]) = f([a.sub.1]). Since any endomorphism f maps a clique to a clique of the same size and there is only one clique of size 4 in X[Y], {f([a.sub.1]),f([a.sub.2]),f([b.sub.1]),f([b.sub.2])} = {[a.sub.1], [a.sub.2], [b.sub.1],[b.sub.2]}. Note that {[c.sub.1], [c.sub.2]} [member of] E(X[Y]). Then {f([c.sub.1]), f([c.sub.2])} = {f([c.sub.1]), f([a.sub.2])} [member of] E(X[Y]). Thus f([c.sub.1]) [member of] {f([a.sub.1]),f([a.sub.2]),f([b.sub.1]),f([b.sub.2])}, which is a contradiction. Clearly, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any x [member of] {[a.sub.1], [a.sub.2] ,[b.sub.1], [b.sub.2]}. Hence f [member of] Aut(X[Y]) and so f is completely regular. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some t [member of] {[a.sub.1], [a.sub.2], [b.sub.1], [b.sub.2]}. Without loss of generality, we can suppose f([c.sub.1]) = f([a.sub.1]). Then f([c.sub.2]) [member of] {f([a.sub.2]), f([b.sub.1]),f([b.sub.2])}. Thus [I.sub.f] [congruent to] [K.sub.4]. Hence f([I.sub.f]) = [I.sub.f] and f is completely regular. Consequently, ([K.sub.1] [union] [K.sub.2])[[K.sub.2]] is End-completely-regular.

Case 3. X = 2[K.sub.2] and Y = [K.sub.2]. Let f [member of] End(X[Y]). If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any x [member of] V(X[Y]), then f [member of] Aut(X[Y]) and so f is completely regular. If f(x) = f(y) for some x,y [member of] V(X[Y]) with x = y, without loss of generality, we can suppose f([a.sub.1]) = f([c.sub.1]). Since [b.sub.1], [b.sub.2], [c.sub.1], [c.sub.2] is a clique of size 4 in X[Y], f([b.sub.1]), f([b.sub.2]), f([c.sub.1]), f([c.sub.2]) is also a clique of size 4 in X[Y]. Note that [a.sub.2], [d.sub.1], [d.sub.2] are adjacent to [a.sub.1]. Then f([a.sub.2]), f([d.sub.1]), f([d.sub.2]) are adjacent to f([a.sub.1]) = f([c.sub.1]). Thus f([a.sub.2]), f([d.sub.1]),f([d.sub.2]) [member of] {f([b.sub.1]), f([b.sub.2]), f([c.sub.2])} and If [congruent to] [K.sub.4]. Hence f([I.sub.f]) = [I.sub.f] and f is completely regular. Consequently, (2[K.sub.2])[[K.sub.2]] is End-completely-regular.

Necessity. We only need to show that X[Y] is not End-completely-regular in the following cases.

Case 1 (X = [K.sub.2]). Then X[Y] =Y + Y. By Lemma 4, [K.sub.2][Y] is not End-completely-regular for the corresponding Y.

Case 2 (X = [P.sub.2]). Then [K.sub.2] is a retract of X. Since [K.sub.2][Y] is not End-completely-regular for Y = [P.sub.2], 2[K.sub.1], 2[K.sub.2], [K.sub.1] [union] [K.sub.2], by Lemma 12, [P.sub.2][Y] is not End-completely-regular for the corresponding Y.

Case 3 (X = 2[K.sub.1]). Then X[Y] = 2Y. If Y is bipartite, then X[Y] is also bipartite. By Lemma 3, (2[K.sub.1])[Y] is not End-completely-regular for the corresponding Y.

Case 4 (X = 2[K.sub.2]). Then X[Y] = 2(Y + Y). Since Y + Y is not End-completely-regular for Y = [P.sub.2], 2[K.sub.1], 2[K.sub.2], [K.sub.1] [union] [K.sub.2], by Lemma 13, (2[K.sub.2])[Y] is not End-completely-regular for the corresponding Y.

Case 5 (X = [K.sub.1] [union] [K.sub.2]). Then X[Y] = Y [union] (Y + Y). Since Y + Y is not End-completely-regular for Y = [P.sub.2], 2[K.sub.1], 2[K.sub.2], [K.sub.1] [union] [K.sub.2], by Lemma 13, ([K.sub.1] [union] [K.sub.2])[Y] is not End-completely-regular for the corresponding Y.

Next we start to seek the conditions for a lexicographic product of bipartite graphs X and Y under which X[Y] is End-inverse.

Theorem 15. Let X and Y be two graphs. If X[Y] is End-inverse, then both X and Y are End-inverse.

Proof. Since X[Y] is End-inverse, X[Y] is End-regular. By Lemma 1, both X and Y are End-regular. To show that X is End-inverse, we only need to prove that the idempotents of End(X) commute.

Let [f.sub.1] and [f.sub.2] be two idempotents in End(X). Define two mappings [g.sub.1] and [g.sub.2] from V(X[Y]) to itself by

[g.sub.1] ((x, y)) = ([f.sub.1] (x) ,y) [for all](x,y) [member of]V(X[Y]),

[g.sub.2] ((x, y)) = ([f.sub.2] (x) ,y) [for all](x,y) [member of]V(X[Y]). (5)

Then [g.sub.1] and [g.sub.2] are two idempotents of End(X[Y]) and so [g.sub.1][g.sub.2] = [g.sub.2][g.sub.1], since X[Y] is End-inverse. For any (x,y) [member of] V(X[Y]),we have

([g.sub.1][g.sub.2]) ((x, y)) = [g.sub.1] (([f.sub.2] (x), y)) = (([f.sub.1][f.sub.2]) (x), y)

= ([g.sub.2][g.sub.1]) ((x, y)) = (([f.sub.2][f.sub.1]) (x), y). (6)

Clearly, [f.sub.1][f.sub.2] = [f.sub.2][f.sub.1]. Hence X is End-inverse.

Similarly, let [f.sub.3] and [f.sub.4] be two idempotents in End(Y). Define two mappings [g.sub.3] and [g.sub.4] from V(X[Y]) to itself by

[g.sub.3] ((x, y)) = (x, [f.sub.3] (y)) [for all](x, y) [member of]V (X[Y]),

[g.sub.4] ((x, y)) = (x, [f.sub.4] (y)) [for all](x,y) [member of]V (X[Y]). (7)

Then [g.sub.3] and [g.sub.4] are two idempotents of End(X[Y]) and so [g.sub.3][g.sub.4] = [g.sub.4][g.sub.3], since X[Y] is End-inverse. For any (x,y) [member of] V(X[Y]), we have

([g.sub.3][g.sub.4]) ((x,y)) = (x, ([f.sub.3][f.sub.4]) (y)) = ([g.sub.4][g.sub.3]) ((x,y))

=(x, ([f.sub.4][f.sub.3]) (y)) (8)

Clearly, f3f4 = f4f3. Hence Y is End-inverse, as required.

The next theorem characterizes the End-inverse lexicographic products of bipartite graphs.

Theorem 16. Let X and Y be two bipartite graphs. Then X[Y] is End-inverse if and only if X[Y] is one of XJXJ, [K.sub.1][[K.sub.2]], [K.sub.2][[K.sub.1]], and [K.sub.2][[K.sub.2]].

Proof

Necessity. This follows directly from Lemma 6 and Theorem 15.

Sufficiency. It is easy to see that XJXJ = [K.sub.1], [K.sub.1][[K.sub.2]] = [K.sub.2][[K.sub.1]] = [K.sub.2], and [K.sub.2][[K.sub.2]] = K4 are End-inverse, since they are unretractive.

http://dx.doi.org/ 10.1155/2014/432073

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

The authors want to express their gratitude to the referees for their helpful suggestions and comments. This research was partially supported by the National Natural Science Foundation of China (nos. 11301151 and 11226047), the Key Project of the Education Department of Henan Province (no. 13A110249), and the Project of Science and Technology Department of Henan Province (no. 132300410411).

References

[1] E. Wilkeit, "Graphs with a regular endomorphism monoid," Archiv der Mathematik, vol. 66, no. 4, pp. 344-352,1996.

[2] S. Fan, "On end-regular graphs," Discrete Mathematics, vol. 159, no. 1-3, pp. 95-102,1996.

[3] H. Hou and Y. Luo, "Graphs whose endomorphism monoids are regular," Discrete Mathematics, vol. 308, no. 17, pp. 3888-3896, 2008.

[4] H. Hou, R. Gu, and X. Li, "End-completely-regular and endinverse joins of graphs," Ars Combinatoria. In press.

[5] H. Hou, Y. Luo, and X. Fan, "End-regular and end-orthodox joins of split graphs," Ars Combinatoria, vol. 105, pp. 305-318, 2012.

[6] H. L. Hou, Y. F. Luo, and R. Gu, "The join of split graphs whose half-strong endomorphisms form a monoid," Acta Mathematica Sinica, vol. 26, no. 6, pp. 1139-1148, 2010.

[7] W. Li and J. Chen, "Endomorphism--regularity of split graphs," European Journal of Combinatorics, vol. 22, no. 2, pp. 207-216, 2001.

[8] W. Li, "Graphs with regular monoids," Discrete Mathematics, vol. 265, no. 1-3, pp. 105-118, 2003.

[9] M. Bottcher and U. Knauer, "Endomorphism spectra of graphs," Discrete Mathematics, vol. 109, no. 1-3, pp. 45-57,1992.

[10] J. M. Howie, Fundamentals of Semigroup Theory, Clarendon Press, Oxford, UK, 1995.

[11] A. V Kelarev, J. Ryan, and J. Yearwood, "Cayley graphs as classifiers for data mining: the influence of asymmetries," Discrete Mathematics, vol. 309, no. 17, pp. 5360-5369, 2009.

[12] A. V Kelarev, Graph Algebras and Automata, Marcel Dekker, New York, NY, USA, 2003.

[13] U. Knauer, Algebraic Graph Theory: Morphisms, Monoids and Matrices, Walter de Gruyter, Berlin, Germany, 2011.

[14] P. Petrich and N. R. Reilly, Completely Regular Semigroups, John Wiley & Sons, New York, NY, USA, 1999.

[15] S. Fan, "End-regular graphs," Journal of Jinan University, vol. 18, pp. 1-7,1997

[16] W. Li, "Split graphs with completely regular endomorphism monoids," Journal of Mathematical Research and Exposition, vol. 26, no. 2, pp. 253-263, 2006.

[17] S. H. Fan, "The endomorphism monoid of the lexicographic product of two graphs," Acta Mathematica Sinica, vol. 38, no. 2, pp. 248-252,1995.

Hailong Hou and Rui Gu

School of Mathematics and Statistics, Henan University of Science and Technology, Luoyang, Henan 471003, China

Correspondence should be addressed to Hailong Hou; hailonghou@163.com

Received 20 February 2014; Accepted 6 April 2014; Published 17 April 2014

Academic Editor: Wu Tongsuo
COPYRIGHT 2014 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2014 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Hou, Hailong; Gu, Rui
Publication:The Scientific World Journal
Article Type:Report
Date:Jan 1, 2014
Words:5609
Previous Article:Exploration of potential roles of a new LOXL2 splicing variant using network knowledge in esophageal squamous cell carcinoma.
Next Article:An opportunistic routing mechanism combined with long-term and short-term metrics for WMN.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |