# End-Completely-Regular and End-Inverse Lexicographic Products of Graphs

Authors: Hailong Hou; Rui Gu
Journal: The Scientific World Journal
 (2014)

---

## Abstract

A graphX is said to be End-completely-regular (resp., End-inverse) if its endomorphism monoid End(X) is completely regular (resp., inverse). In this paper, we will show that if X[Y] is End-completely-regular (resp., End-inverse), then both X and Y are End-completely-regular (resp., End-inverse). 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 determine the End-completely-regular and End-inverse lexicographic products of bipartite graphs.


---

## Body

## 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 graphsX 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
1 and x
2 are adjacent in X, the edge connecting x
1 and x
2 is denoted by {
x
1
,
x
2
} and we write {
x
1
,
x
2
}
∈
E
(
X
). A subgraph H is called aninduced subgraph of X if for any a
,
b
∈
V
(
H
), {
a
,
b
}
∈
E
(
H
) if and only if {
a
,
b
}
∈
E
(
X
). A graph X is calledbipartite 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.LetX and Y be two graphs. Thejoin of X and Y, denoted by X
+
Y, is a graph such that V
(
X
+
Y
)
=
V
(
X
)
∪
V
(
Y
) and E
(
X
+
Y
)
=
E
(
X
)
∪
E
(
Y
)
∪
{
{
x
1
,
x
2
}
∣
x
1
∈
V
(
X
)
,
x
2
∈
V
(
Y
)
}. Thelexicographic product of X and Y, denoted by X
[
Y
], is a graph with vertex set V
(
X
[
Y
]
)
=
V
(
X
)
×
V
(
Y
), and with edge set E
(
X
[
Y
]
)
=
{
{
(
x
,
y
)
,
(
x
1
,
y
1
)
}
∣
{
x
,
x
1
}
∈
E
(
X
), or x
=
x
1 and {
y
,
y
1
}
∈
E
(
Y
)
}. Denote Y
x
=
{
(
x
,
y
)
∣
y
∈
V
(
Y
)
} for any x
∈
V
(
X
).LetX and Y be graphs. A mapping f from V
(
X
) to V
(
Y
) is called ahomomorphism (from X to Y) if {
x
1
,
x
2
}
∈
E
(
X
) implies that {
f
(
x
1
)
,
f
(
x
2
)
}
∈
E
(
Y
). A homomorphism f is called anisomorphism if f is bijective and f
-
1 is a homomorphism. A homomorphism (resp., isomorphism) f from X to itself is called anendomorphism (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 beunretractive if End
(
X
)
=
Aut
(
X
). For any f
∈
End
(
X
), it is easy to see that f
∈
Aut
(
X
) if and only if f is injective.Aretraction of a graph X is a homomorphism f from X to a subgraph Y of X such that the restriction f
|
Y of f to V
(
Y
) is the identity mapping on V
(
Y
). In this case, Y is called aretract 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 theendomorphic image of X under f, denoted by I
f, if V
(
I
f
)
=
f
(
V
(
X
)
) and {
f
(
a
)
,
f
(
b
)
}
∈
E
(
I
f
) if and only if there exist c
∈
f
-
1
(
f
(
a
)
) and d
∈
f
-
1
(
f
(
b
)
) such that {
c
,
d
}
∈
E
(
X
). By ρ
f we denote the equivalence relation on V
(
X
) induced by f; that is, for a
,
b
∈
V
(
X
), (
a
,
b
)
∈
ρ
f if and only if f
(
a
)
=
f
(
b
). Denote by [
a
]
ρ
f the equivalence class containing a
∈
V
(
X
) with respect to ρ
f.An elementa of a semigroup S is calledregular if there exists x
∈
S such that a
x
a
=
a. An element a of a semigroup S is calledcompletely regular if a
=
a
x
a and x
a
=
a
x hold for some x
∈
S. A semigroup S is calledregular (resp.,completely regular) if all its elements are regular (resp., completely regular). Aninverse 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]).
IfX
[
Y
] is End-regular, then both X and Y are End-regular.Lemma 2 (see [15]).
LetG be a graph and let f
∈
E
n
d
(
G
). Then f is completely regular if and only if f
|
I
f
∈
A
u
t
(
I
f
).Lemma 3 (see [15]).
LetX be a bipartite graph. Then X is End-completely-regular if and only if X is one of K
1, K
2, P
2, 2
K
1, 2
K
2, and K
1
⋃
K
2.Lemma 4 (see [4]).
LetX 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
1 or K
2.Lemma 5 (see [16]).
LetG be a graph and f
∈
E
n
d
(
G
). Then f is completely regular if and only if there exists g
∈
I
d
p
t
(
G
) such that ρ
g
=
ρ
f and I
g
=
I
f.Lemma 6 (see [4]).
LetX be a bipartite graph. Then X is End-inverse if and only if X
=
K
1 or X
=
K
2.Lemma 7 (see [17]).
LetX and Y be two graphs. Then E
n
d
(
X
[
Y
]
)
=
E
n
d
(
X
)
[
E
n
d
(
Y
)
] if and only if for any f
∈
E
n
d
(
X
[
Y
]
) and x
∈
V
(
X
), there exists x
′
∈
V
(
X
) such that f
(
Y
x
)
⊆
Y
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 ifX
[
Y
] is End-completely-regular, then both X and Y are End-completely-regular.Theorem 8.
LetX and Y be two graphs. If X
[
Y
] is End-completely-regular, then both X and Y are End-completely-regular.Proof.
By Lemma2, to show that X is End-completely-regular, it is only necessary to verify that f
|
I
f is an automorphism of I
f for each f
∈
End
(
X
). Define a mapping F from V
(
X
[
Y
]
) to itself by
(1)
F
(
(
x
,
y
)
)
=
(
f
(
x
)
,
y
)
∀
(
x
,
y
)
∈
V
(
X
[
Y
]
)
.
Then F
∈
End
(
X
[
Y
]
). Since X
[
Y
] is End-completely-regular, by Lemma 2, F
|
I
F is an automorphism of I
F. It is easy to see that I
F
=
I
f
[
Y
]. For any distinct x
1
,
x
2
∈
V
(
I
f
) and y
∈
V
(
Y
), F
(
(
x
1
,
y
)
)
=
(
f
(
x
1
)
,
y
) and F
(
(
x
2
,
y
)
)
=
(
f
(
x
2
)
,
y
) hold. Since F
|
I
F is an automorphism of I
F, (
f
(
x
1
)
,
y
)
≠
(
f
(
x
2
)
,
y
). Hence f
(
x
1
)
≠
f
(
x
2
) and so f
|
I
f is an automorphism of I
f.
Letg
∈
End
(
Y
). Define a mapping G from V
(
X
[
Y
]
) to itself by
(2)
G
(
(
x
,
y
)
)
=
(
x
,
g
(
y
)
)
∀
(
x
,
y
)
∈
V
(
X
[
Y
]
)
.
Then G
∈
End
(
X
[
Y
]
). Since X
[
Y
] is End-completely-regular, by Lemma 2, G
|
I
G is an automorphism of I
G. It is easy to see that I
G
=
X
[
I
g
]. For any x
∈
V
(
X
) and y
1
,
y
2
∈
V
(
I
g
), G
(
(
x
,
y
1
)
)
=
(
x
,
g
(
y
1
)
) and G
(
(
x
,
y
2
)
)
=
(
x
,
g
(
y
2
)
). Since G
|
I
G is an automorphism of I
G, (
x
,
g
(
y
1
)
)
≠
(
x
,
g
(
y
2
)
), we get that g
(
y
1
)
≠
g
(
y
2
) and so g
|
I
g is an automorphism of I
g, as required.The following example shows thatX and Y being End-completely-regular does not yield that X
[
Y
] is End-completely-regular.Example 9.
LetX and Y be two graphs with V
(
X
)
=
{
x
1
,
x
2
}, V
(
Y
)
=
{
y
1
,
y
2
}, E
(
X
)
=
{
{
x
1
,
x
2
}
}, and E
(
Y
)
=
ϕ. By Lemma 3, X and Y are End-completely-regular. It is easy to see that X
[
Y
]
≅
C
4. Also by Lemma 3, this is not End-completely-regular.In the following, we give some sufficient conditions forX
[
Y
] to be End-completely-regular. To this aim, we need the following result due to Fan [17].Lemma 10 (see [17]).
LetX and Y be two K
3-free connected graphs. If g
i
r
t
h
(
X
) or g
i
r
t
h
(
Y
) is odd, then E
n
d
(
X
[
Y
]
)
=
E
n
d
(
X
)
[
E
n
d
(
Y
)
], where E
n
d
(
X
)
[
E
n
d
(
Y
)
] is the wreath product of the monoids E
n
d
(
X
) and E
n
d
(
Y
).LetX and Y be two K
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.
LetX and Y be two K
3-free connected graphs with g
i
r
t
h
(
X
) or g
i
r
t
h
(
Y
) being odd, and assume that(1)
Xis End-completely-regular,
(2)
Y is unretractive.Then X
[
Y
] is End-completely-regular.Proof.
LetX and Y be two graphs satisfying the assumptions. To show that X
[
Y
] is End-completely-regular, we prove that for any F
∈
End
(
X
[
Y
]
), there exists an idempotent endomorphism G
∈
End
(
X
[
Y
]
) such that ρ
F
=
ρ
G and I
F
=
I
G.
LetF
∈
End
(
X
)
[
End
(
Y
)
]. Since End
(
X
[
Y
]
)
=
End
(
X
)
[
End
(
Y
)
], F
=
(
s
,
f
) for some s
∈
End
(
X
) and f
∈
End
(
Y
)
V
(
X
). Thus, for any u
∈
V
(
X
), there exists f
u
=
f
(
u
)
∈
End
(
Y
). Let X and Y be K
3-free connected graphs with girth
(
X
) or girth
(
Y
) being odd. By Lemma 7, for any u
∈
V
(
X
), F
(
Y
u
)
⊆
Y
v for some v
∈
V
(
X
). Note that Y is unretractive. Then F
(
Y
u
)
=
Y
v. Since X is End-completely-regular and s
∈
End
(
X
), by Lemma 5, there exists t
∈
Idpt
(
X
) such that ρ
t
=
ρ
s and I
t
=
I
s. Clearly, I
s is an induced subgraph of X. Hence I
F
=
I
s
[
Y
] is an induced subgraph of X
[
Y
].
SinceX is End-completely-regular, s
|
I
s is an automorphism of I
s. Thus for any u
∈
I
s, there exists only one vertex u
1
∈
I
s such that s
(
u
1
)
=
u. Then F
(
Y
u
1
)
=
Y
u. Now for any (
u
,
v
)
∈
I
F, there exists only one vertex (
u
1
,
v
1
)
∈
I
F such that F
(
(
u
1
,
v
1
)
)
=
(
u
,
v
). Define a mapping G from V
(
X
[
Y
]
) to itself in the following way. If (
x
,
y
)
∈
V
(
I
F
), then G
(
(
x
,
y
)
)
=
(
x
,
y
); if (
x
,
y
)
∉
V
(
I
F
), then F
(
(
x
,
y
)
)
=
(
u
,
v
) for some (
u
,
v
)
∈
V
(
I
F
). Now let G
(
(
x
,
y
)
)
=
(
u
1
,
v
1
), where (
u
1
,
v
1
) is the only vertex in V
(
I
F
) such that F
(
(
u
1
,
v
1
)
)
=
(
u
,
v
). Then it is easy to see that G is well-defined. Let (
x
,
y
)
∈
V
(
X
[
Y
]
). If (
x
,
y
)
∈
V
(
I
F
), then x
∈
I
s. Thus t
(
x
)
=
x. Hence G
(
(
x
,
y
)
)
=
(
x
,
y
)
∈
Y
t
(
x
). If (
x
,
y
)
∉
V
(
I
F
), then t
(
x
)
=
u
1. Hence G
(
(
x
,
y
)
)
=
(
u
1
,
v
1
)
∈
Y
t
(
x
). Therefore, G
(
(
x
,
y
)
)
∈
Y
t
(
x
) for any (
x
,
y
)
∈
V
(
X
[
Y
]
).
Let(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
∈
V
(
X
[
Y
]
) be such that {
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
}
∈
E
(
X
[
Y
]
). If (
x
1
,
y
1
)
,
(
x
2
,
y
2
)
∈
V
(
I
F
), then {
G
(
(
x
1
,
y
1
)
)
,
G
(
(
x
2
,
y
2
)
)
}
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
}
∈
E
(
X
[
Y
]
). If (
x
1
,
y
1
)
∈
V
(
I
F
) and (
x
2
,
y
2
)
∉
V
(
I
F
), then x
1
≠
x
2 and {
x
1
,
x
2
}
∈
E
(
X
). Thus G
(
(
x
1
,
y
1
)
)
∈
Y
t
(
x
1
) and G
(
(
x
2
,
y
2
)
)
∈
Y
t
(
x
2
). Since t
∈
Idpt
(
X
) and {
x
1
,
x
2
}
∈
E
(
X
), {
t
(
x
1
)
,
t
(
x
2
)
}
∈
E
(
X
). Hence {
G
(
(
x
1
,
y
1
)
)
,
G
(
(
x
2
,
y
2
)
)
}
∈
E
(
X
[
Y
]
). If (
x
1
,
y
1
)
∉
V
(
I
F
) and (
x
2
,
y
2
)
∉
V
(
I
F
), there are two cases.
Case
1. Assume that {
x
1
,
x
2
}
∈
E
(
X
). Then G
(
(
x
1
,
y
1
)
)
∈
Y
t
(
x
1
) and G
(
(
x
2
,
y
2
)
)
∈
Y
t
(
x
2
). Since t
∈
Idpt
(
X
) and {
x
1
,
x
2
}
∈
E
(
X
), {
t
(
x
1
)
,
t
(
x
2
)
}
∈
E
(
X
). Hence we have {
G
(
(
x
1
,
y
1
)
)
,
G
(
(
x
2
,
y
2
)
)
}
∈
E
(
X
[
Y
]
).
Case
2. Assume that x
1
=
x
2 and {
y
1
,
y
2
}
∈
E
(
Y
). Then we have (
x
1
,
y
1
)
,
(
x
2
,
y
2
)
∈
Y
x
1 and G
(
(
x
1
,
y
1
)
)
,
G
(
(
x
2
,
y
2
)
)
∈
Y
t
(
x
1
). Since G
|
Y
x
1 is an isomorphism from Y
x
1 to Y
t
(
x
1
), {
G
(
(
x
1
,
y
1
)
)
,
G
(
(
x
2
,
y
2
)
)
}
∈
E
(
X
[
Y
]
). Therefore, G
∈
End
(
X
[
Y
]
).
If(
x
,
y
)
∈
V
(
I
F
), then G
2
(
(
x
,
y
)
)
=
G
(
(
x
,
y
)
)
=
(
x
,
y
). If (
x
,
y
)
∉
V
(
I
F
), then G
(
(
x
,
y
)
)
∈
V
(
I
F
). Thus G
2
(
(
x
,
y
)
)
=
G
(
G
(
(
x
,
y
)
)
)
=
G
(
(
x
,
y
)
). Hence G
∈
Idpt
(
X
[
Y
]
). Clearly, I
G
=
I
F.
Suppose[
(
x
1
,
y
1
)
]
ρ
F
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
k
,
y
k
)
} for some (
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
k
,
y
k
)
∈
V
(
X
[
Y
]
). In fact, it is easy to prove that ρ
F
⊆
ρ
G
⊆
ρ
F. Let (
x
1
,
y
1
)
ρ
F
(
x
2
,
y
2
). Then, by the definition of G, we have G
(
(
x
1
,
y
1
)
)
=
G
(
(
x
2
,
y
2
)
)
=
(
u
1
,
v
1
) for some (
u
1
,
v
1
)
∈
V
(
I
F
) with F
(
(
x
1
,
y
1
)
)
=
F
(
u
1
,
v
1
)
=
F
(
(
x
2
,
y
2
)
). So (
x
1
,
y
1
)
ρ
G
(
x
2
,
y
2
) and thus ρ
F
⊆
ρ
G
⊆
ρ
F. Hence ρ
F
=
ρ
G.Next we start to seek the conditions for bipartite graphsX and Y under which X
[
Y
] is End-completely-regular.Lemma 12.
LetX be a graph and R be a retract of X. If R
[
Y
] is not End-completely-regular, then X
[
Y
] is not End-completely-regular.Proof.
LetR be a retract of X. Then there exists f
∈
Idpt
(
X
) such that I
f
=
R. Let g
∈
End
(
R
[
Y
]
). Since R
[
Y
] is not End-completely-regular, there exists g
∈
End
(
R
[
Y
]
) such that g is not completely regular. By Lemma 2, g
|
I
g is not an automorphism of I
g. Thus there exist x
1
,
x
2
∈
I
g with x
1
≠
x
2 such that g
(
x
1
)
=
g
(
x
2
). Define a mapping F from V
(
X
[
Y
]
) to itself by
(3)
F
(
(
x
,
y
)
)
=
(
f
(
x
)
,
y
)
∀
(
x
,
y
)
∈
V
(
X
[
Y
]
)
.
Then F
∈
End
(
X
[
Y
]
) and I
F
=
R
[
Y
]. Now it is easy to see that g
F
∈
End
(
X
[
Y
]
) and I
g
F
=
I
g. It follows from (
g
F
)
(
x
1
)
=
(
g
F
)
(
x
2
) that (
g
F
)
|
I
g
F is not an automorphism of I
g
F. Hence X
[
Y
] is not End-completely-regular.Lemma 13.
LetX and Y be two graphs. If at least one of X and Y is not End-completely-regular, then X
∪
Y is not End-completely-regular (where X
∪
Y is the disjoint union of X and Y).Proof.
Without loss of generality, we may suppose thatX is not End-completely-regular. By Lemma 2, there exists f
∈
End
(
X
) such that f
|
I
f is not an automorphism of I
f. Define a mapping F from V
(
X
∪
Y
) to itself by
(4)
F
(
x
)
=
{
f
(
x
)
,
x
∈
V
(
X
)
,
x
,
x
∈
V
(
Y
)
.
Then F
∈
End
(
X
∪
Y
). Now it is easy to see that I
F
=
I
f
∪
Y and F
(
x
)
=
f
(
x
) for any x
∈
V
(
X
). Since f
|
I
f is not an automorphism of I
f, F
|
I
F is not an automorphism of I
F. Hence X
∪
Y is not End-completely-regular.Theorem 14.
LetX and Y be two bipartite graphs. Then X
[
Y
] is End-completely-regular if and only if(1)
X
=
K
1 and Y is End-completely-regular or
(2)
X is End-completely-regular and Y
=
K
1 or K
2.Proof
h
h
h
h
h
h
h
Sufficiency. Since K
1
[
Y
]
=
Y and X
[
K
1
]
=
X, we have immediately that K
1
[
Y
]
(
X
[
K
1
]
) is End-completely-regular if and only if Y
(
X
) is End-completely-regular. If X
=
Y
=
K
2, then X
[
Y
]
=
K
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
1 and Y
=
K
2, then X
[
Y
]
=
2
K
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
2 and Y
=
K
2. Let f
∈
End
(
X
[
Y
]
). If [
x
1
]
ρ
f
=
{
x
1
}, then [
x
2
]
ρ
f
=
{
x
2
}. Otherwise, f
(
x
2
)
=
f
(
z
1
) or f
(
x
2
)
=
f
(
z
2
). Without loss of generality, we can suppose f
(
x
2
)
=
f
(
z
1
). Since z
1 is adjacent to every vertex of {
z
2
,
y
1
,
y
2
} and {
x
1
,
x
2
}
∈
E
(
X
[
Y
]
), f
(
z
1
) is adjacent to every vertex of {
f
(
z
2
)
,
f
(
y
1
)
,
f
(
y
2
)
,
f
(
x
1
)
}. Note that there is no vertex in X
[
Y
] adjacent to 4 vertices. This is a contradiction. Hence f
∈
Aut
(
X
[
Y
]
) and so f is completely regular. If [
x
1
]
ρ
f
≠
{
x
1
}, then f
(
x
1
)
=
f
(
z
1
) or f
(
x
1
)
=
f
(
z
2
). Without loss of generality, we can suppose f
(
x
1
)
=
f
(
z
1
). Then f
(
x
2
)
=
f
(
z
2
). Otherwise, a similar argument as above will show that f
(
x
1
) is adjacent to every vertex of {
f
(
x
2
)
,
f
(
y
1
)
,
f
(
y
2
)
,
f
(
z
2
)
}, which yield a contradiction. Thus I
f
≅
K
4. Since any endomorphism f maps a clique to a clique of the same size, f
(
I
f
)
=
I
f. By Lemma 2, f is completely regular. Hence P
2
[
K
2
] is End-completely-regular.
Case
2.
X
=
K
1
∪
K
2 and Y
=
K
2. Let f
∈
End
(
X
[
Y
]
). If [
c
1
]
ρ
f
=
{
c
1
}, then [
c
2
]
ρ
f
=
{
c
2
}. Otherwise, f
(
c
2
)
∈
{
f
(
a
1
)
,
f
(
a
2
)
,
f
(
b
1
)
,
f
(
b
2
)
}. Without loss of generality, we can suppose f
(
c
2
)
=
f
(
a
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
1
)
,
f
(
a
2
)
,
f
(
b
1
)
,
f
(
b
2
)
}
=
{
a
1
,
a
2
,
b
1
,
b
2
}. Note that {
c
1
,
c
2
}
∈
E
(
X
[
Y
]
). Then {
f
(
c
1
)
,
f
(
c
2
)
}
=
{
f
(
c
1
)
,
f
(
a
1
)
}
∈ E
(
X
[
Y
]
). Thus f
(
c
1
)
∈
{
f
(
a
1
)
,
f
(
a
2
)
,
f
(
b
1
)
,
f
(
b
2
)
}, which is a contradiction. Clearly, [
x
]
ρ
f
=
{
x
} for any x
∈
{
a
1
,
a
2
,
b
1
,
b
2
}. Hence f
∈
Aut
(
X
[
Y
]
) and so f is completely regular. If [
c
1
]
ρ
f
≠
{
c
1
}, then f
(
c
1
)
=
f
(
t
) for some t
∈
{
a
1
,
a
2
,
b
1
,
b
2
}. Without loss of generality, we can suppose f
(
c
1
)
=
f
(
a
1
). Then f
(
c
2
)
∈
{
f
(
a
2
)
,
f
(
b
1
)
,
f
(
b
2
)
}. Thus I
f
≅
K
4. Hence f
(
I
f
)
=
I
f and f is completely regular. Consequently, (
K
1
∪
K
2
)
[
K
2
] is End-completely-regular.
Case
3.
X
=
2
K
2 and Y
=
K
2. Let f
∈
End
(
X
[
Y
]
). If [
x
]
ρ
f
=
{
x
} for any x
∈
V
(
X
[
Y
]
), then f
∈
Aut
(
X
[
Y
]
) and so f is completely regular. If f
(
x
)
=
f
(
y
) for some x
,
y
∈
V
(
X
[
Y
]
) with x
≠
y, without loss of generality, we can suppose f
(
a
1
)
=
f
(
c
1
). Since b
1, b
2, c
1, c
2 is a clique of size 4 in X
[
Y
], f
(
b
1
), f
(
b
2
), f
(
c
1
), f
(
c
2
) is also a clique of size 4 in X
[
Y
]. Note that a
2, d
1, d
2 are adjacent to a
1. Then f
(
a
2
), f
(
d
1
), f
(
d
2
) are adjacent to f
(
a
1
)
=
f
(
c
1
). Thus f
(
a
2
)
,
f
(
d
1
)
,
f
(
d
2
)
∈
{
f
(
b
1
)
,
f
(
b
2
)
,
f
(
c
2
)
} and I
f
≅
K
4. Hence f
(
I
f
)
=
I
f and f is completely regular. Consequently, (
2
K
2
)
[
K
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
2
)
. Then X
[
Y
]
=
Y
+
Y. By Lemma 4, K
2
[
Y
] is not End-completely-regular for the corresponding Y.
Case
2  (
X
=
P
2
)
. Then K
2 is a retract of X. Since K
2
[
Y
] is not End-completely-regular for Y
=
P
2, 2
K
1
,
2
K
2
,
K
1
∪
K
2, by Lemma 12, P
2
[
Y
] is not End-completely-regular for the corresponding Y.
Case
3  (
X
=
2
K
1
)
. Then X
[
Y
]
=
2
Y. If Y is bipartite, then X
[
Y
] is also bipartite. By Lemma 3, (
2
K
1
)
[
Y
] is not End-completely-regular for the corresponding Y.
Case
4  (
X
=
2
K
2
)
. Then X
[
Y
]
=
2
(
Y
+
Y
). Since Y
+
Y is not End-completely-regular for Y
=
P
2, 2
K
1
,
2
K
2
,
K
1
∪
K
2, by Lemma 13, (
2
K
2
)
[
Y
] is not End-completely-regular for the corresponding Y.
Case
5  (
X
=
K
1
∪
K
2
)
. Then X
[
Y
]
=
Y
∪
(
Y
+
Y
). Since Y
+
Y is not End-completely-regular for Y
=
P
2, 2
K
1
,
2
K
2
,
K
1
∪
K
2, by Lemma 13, (
K
1
∪
K
2
)
[
Y
] is not End-completely-regular for the corresponding Y.Figure 1
GraphsP
2
[
K
2
], (
K
1
∪
K
2
)
[
K
2
], and (
2
K
2
)
[
K
2
].Next we start to seek the conditions for a lexicographic product of bipartite graphsX and Y under which X
[
Y
] is End-inverse.Theorem 15.
LetX and Y be two graphs. If X
[
Y
] is End-inverse, then both X and Y are End-inverse.Proof.
SinceX
[
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.
Letf
1 and f
2 be two idempotents in End
(
X
). Define two mappings g
1 and g
2 from V
(
X
[
Y
]
) to itself by
(5)
g
1
(
(
x
,
y
)
)
=
(
f
1
(
x
)
,
y
)
∀
(
x
,
y
)
∈
V
(
X
[
Y
]
)
,
g
2
(
(
x
,
y
)
)
=
(
f
2
(
x
)
,
y
)
∀
(
x
,
y
)
∈
V
(
X
[
Y
]
)
.
Then g
1 and g
2 are two idempotents of End
(
X
[
Y
]
) and so g
1
g
2
=
g
2
g
1, since X
[
Y
] is End-inverse. For any (
x
,
y
)
∈
V
(
X
[
Y
]
), we have
(6)
(
g
1
g
2
)
(
(
x
,
y
)
)
=
g
1
(
(
f
2
(
x
)
,
y
)
)
=
(
(
f
1
f
2
)
(
x
)
,
y
)
=
(
g
2
g
1
)
(
(
x
,
y
)
)
=
(
(
f
2
f
1
)
(
x
)
,
y
)
.
Clearly, f
1
f
2
=
f
2
f
1. Hence X is End-inverse.
Similarly, letf
3 and f
4 be two idempotents in End
(
Y
). Define two mappings g
3 and g
4 from V
(
X
[
Y
]
) to itself by
(7)
g
3
(
(
x
,
y
)
)
=
(
x
,
f
3
(
y
)
)
∀
(
x
,
y
)
∈
V
(
X
[
Y
]
)
,
g
4
(
(
x
,
y
)
)
=
(
x
,
f
4
(
y
)
)
∀
(
x
,
y
)
∈
V
(
X
[
Y
]
)
.
Then g
3 and g
4 are two idempotents of End
(
X
[
Y
]
) and so g
3
g
4
=
g
4
g
3, since X
[
Y
] is End-inverse. For any (
x
,
y
)
∈
V
(
X
[
Y
]
), we have
(8)
(
g
3
g
4
)
(
(
x
,
y
)
)
=
(
x
,
(
f
3
f
4
)
(
y
)
)
=
(
g
4
g
3
)
(
(
x
,
y
)
)
=
(
x
,
(
f
4
f
3
)
(
y
)
)
.
Clearly, f
3
f
4
=
f
4
f
3. Hence Y is End-inverse, as required.The next theorem characterizes the End-inverse lexicographic products of bipartite graphs.Theorem 16.
LetX and Y be two bipartite graphs. Then X
[
Y
] is End-inverse if and only if X
[
Y
] is one of K
1
[
K
1
], K
1
[
K
2
], K
2
[
K
1
], and K
2
[
K
2
].Proof
h
h
h
h
h
h
h
Necessity. This follows directly from Lemma 6 and Theorem 15.
Sufficiency. It is easy to see that K
1
[
K
1
]
=
K
1, K
1
[
K
2
]
=
K
2
[
K
1
]
=
K
2, and K
2
[
K
2
]
=
K
4 are End-inverse, since they are unretractive.



---

*Source: 432073-2014-04-17.xml*