On Combinatorial Properties of Bands

In this paper we study the D-saturated property of bands defined in terms of their Cayley graphs Cay(S,C), where S is a band and C ? Z(S), the center of S. Also we characterize the Cayley graphs of bands. More generally, for a finite graph Γ =Cay(T, D), where T is a band and D ? Z(T), we give an algorithm for finding all bands S and C ? Z(S) such that Γ =Cay(S, C).     

A problem on generalized Cayley graphs of semigroups

Zhu (Semigroup Forum 84(3), 144–156, 2012) investigated some combinatorial properties of generalized Cayley graphs of semigroups. In Remark 3.8 of (Zhu, Semigroup Forum 84(3), 144–156, 2012), Zhu proposed the following question: It may be interesting to characterize semigroups S such that Cay(S,ω _l )=Cay(S,ω _r ). In this short note, we prove that for any regular semigroup S, Cay(S,ω _l )=Cay(S,ω _r ) if and only if S is a Clifford semigroup.     

On normal 2-geodesic transitive Cayley graphs

We investigate connected normal 2-geodesic transitive Cayley graphs Cay(T,S). We first prove that if Cay(T,S) is neither cyclic nor K_4[2], then 〈a〉?{1}??S for all a∈S. Next, as an application, we give a reduction theorem proving that each graph in this family which is neither a complete multipartite graph nor a bipartite 2-arc transitive graph, has a normal quotient that is either a complete graph or a Cayley graph in the family for a characteristically simple group. Finally we classify complete multipartite graphs in the family.     

On Cayley graphs of rectangular groups

In this paper, we first give a characterization of Cayley graphs of rectangular groups. Then, vertex-transitivity of Cayley graphs of rectangular groups is considered. Further, it is shown that Cayley graphs Cay(S,C) which are automorphism-vertex-transitive, are in fact Cayley graphs of rectangular groups, if the subsemigroup generated by C is an orthodox semigroup. Finally, a characterization of vertex-transitive graphs which are Cayley graphs of finite semigroups is concluded.     

On integral Cayley sum graphs

Let S be a subset of a finite abelian group G. The Cayley sum graph Cay⁺(G, S) of G with respect to S is a graph whose vertex set is G and two vertices g and h are joined by an edge if and only if g + h ∈ S. We call a finite abelian group G a Cayley sum integral group if for every subset S of G, Cay⁺(G, S) is integral i.e., all eigenvalues of its adjacency matrix are integers. In this paper, we prove that all Cayley sum integral groups are represented by Z₃ and Zn₂ ⁿ, n ≥ 1, where Z_k is the group of integers modulo k. Also, we classify simple connected cubic integral Cayley sum graphs.     

D-saturated property of the Cayley graphs of semigroups

Let D be a finite graph. A semigroup S is said to be Cayley D-saturated with respect to a subset T of S if, for all infinite subsets V of S, there exists a subgraph of Cay(S,T) isomorphic to D with all vertices in V. The purpose of this paper is to characterize the Cayley D-saturated property of a semigroup S with respect to any subset T⊆S. In particular, the Cayley D-saturated property of a semigroup S with respect to any subsemigroup T is characterized.     

The metric dimension of Cayley digraphs

A vertex x in a digraph D is said to resolve a pair u, v of vertices of D if the distance from u to x does not equal the distance from v to x. A set S of vertices of D is a resolving set for D if every pair of vertices of D is resolved by some vertex of S. The smallest cardinality of a resolving set for D, denoted by dim(D), is called the metric dimension for D. Sharp upper and lower bounds for the metric dimension of the Cayley digraphs Cay(Δ:Γ), where Γ is the group Z_n1⊕Z_n2⊕?⊕Z_nm and Δ is the canonical set of generators, are established. The exact value for the metric dimension of Cay({(0,1),(1,0)}:Z_n⊕Z_m) is found. Moreover, the metric dimension of the Cayley digraph of the dihedral group D_n of order 2n with a minimum set of generators is established. The metric dimension of a (di)graph is formulated as an integer programme. The corresponding linear programming formulation naturally gives rise to a fractional version of the metric dimension of a (di)graph. The fractional dual implies an integer dual for the metric dimension of a (di)graph which is referred to as the metric independence of the (di)graph. The metric independence of a (di)graph is the maximum number of pairs of vertices such that no two pairs are resolved by the same vertex. The metric independence of the n-cube and the Cayley digraph Cay(Δ:D_n), where Δ is a minimum set of generators for D_n, are established.     

On the genus of generalized unit and unitary Cayley graphs of a commutative ring

Let R be a commutative ring, U(R) be the set of all unit elements of R, G be a multiplicative subgroup of U(R) and S be a non-empty subset of G such that S ^?1={s ^?1:?s∈S}?S. In [16], K. Khashyarmanesh et al. defined a graph of R, denoted by Γ(R,G,S), which generalizes both unit and unitary Cayley graphs of R. In this paper, we derive several bounds for the genus of Γ(R,U(R),S). Moreover, we characterize all commutative Artinian rings R for which the genus of Γ(R,U(R),S) is one. This leads to the characterization of all commutative Artinian rings whose unit and unitary Cayley graphs have genus one.     

Special uniform approximations of continuous vector-valued functions. Part II: special approximations in CX(T)CY(S)

In this paper, which is a continuation of Timofte (J. Approx. Theory 119 (2002) 291–299, we give special uniform approximations of functions from C_XY(T×S) and C_∞(T×S,XY) by elements of the tensor products C_X(T)C_Y(S), respectively C₀(T,X)C₀(S,Y), for topological spaces T,S and Γ-locally convex spaces X,Y (all four being Hausdorff).     

Finite derivation type for semilattices of semigroups

In this paper we investigate how the combinatorial property finite derivation type (FDT) is preserved in a semilattice of semigroups. We prove that if $S= \mathcal{S}[Y,S_{\alpha}]$ is a semilattice of semigroups such that Y is finite and each S _?? (????Y) has FDT, then S has FDT. As a consequence we can show that a strong semilattice of semigroups $\mathcal{S}[Y,S_{\alpha},\lambda_{\alpha,\beta}]$ has FDT if and only if Y is finite and every semigroup S _?? (????Y) has FDT.     

Generalized Cayley graphs of semigroups II

Following Zhu (Semigroup Forum, 2011, doi:), we study generalized Cayley graphs of semigroups. The Cayley D-saturated property, a particular combinatorial property, of generalized Cayley graphs of semigroups is considered and most of the results in Kelarev and Quinn (Semigroup Forum 66:89–96, 2003), Yang and Gao (Semigroup Forum 80:174–180, 2010) are extended. In addition, for some basic graphs and their complete fission graphs, we describe all semigroups whose universal Cayley graphs are isomorphic to these graphs.     

On the Cayley graphs of completely simple semigroups

In this paper, the Cayley graphs of completely simple semigroups are investigated. The basic structure and properties of this kind of Cayley graph are given, and a condition is given for a Cayley graph of a completely simple semigroup to be a disjoint union of complete graphs. We also describe all pairs (S,A) such that S is a completely simple semigroup, A⊆S, and Cay (S,A) is a strongly connected bipartite Cayley graph.     

On distance two graphs of upper bound graphs

For a poset P=(X,≤), the upper bound graph (UB-graph) of P is the graph U=(X,E_U), where uv∈E_U if and only if u≠v and there exists m∈X such that u,v≤m. For a graph G, the distance two graph DS₂(G) is the graph with vertex set V(DS₂(G))=V(G) and u,v∈V(DS₂(G)) are adjacent if and only if d_G(u,v)=2. In this paper, we deal with distance two graphs of upper bound graphs. We obtain a characterization of distance two graphs of split upper bound graphs.     

On the chromatic number of circulant graphs

Given a set D of a cyclic group C, we study the chromatic number of the circulant graph G(C,D) whose vertex set is C, and there is an edge ij whenever i−j∈D∪−D. For a fixed set D={a,b,c:a<b<c} of positive integers, we compute the chromatic number of circulant graphs G(Z_N,D) for all N≥4bc. We also show that, if there is a total order of D such that the greatest common divisors of the initial segments form a decreasing sequence, then the chromatic number of G(Z,D) is at most 4. In particular, the chromatic number of a circulant graph on Z_N with respect to a minimum generating set D is at most 4. The results are based on the study of the so-called regular chromatic number, an easier parameter to compute. The paper also surveys known results on the chromatic number of circulant graphs.     

Existence theorems and necessary conditions for a general formulation of the minimum effort problem

The basic problem considered may be described briefly as follows. LetX,Y, andZ be normed linear spaces,T:D(T)→Y,S:D(S)→Z linear operators withD(T) \( \subseteq\) X andD(S) \( \subseteq\) X,Ω \( \subseteq\) X a convex set containing the zero elementθ, andJ a real-valued convex function defined onX×Y such that

1. J(x,y)?-0 for (x,y)teX×Y,
2. J(θ,θ)=0,
3. J(x,y)→+∞, as (∥x∥²+∥y∥²)^1/2→+∞.

Givenζ∈Y andη∈S[core _T Ω∩;D(S)], find an elementx=x ₀ which minimizesJ(x,ζ?Tx) on the set {x∈[Ω∩;D(S)∩;D(T)]:Sx=η}. The abovementioned problem, together with certain special cases, is analyzed using the classical techniques of functional analysis. Existence problems are considered for a certain class of closed linear operators. In particular, existence of an optimal solution is determined by evaluating a generalized Minkowski functional at the point (ζ,η) inY×Z. A necessary condition is presented for special cases, and corresponding characterizations of optimal solutions are made in terms of the adjoint operators. These results are applicable to linear minimum effort problems, constrained variational problems, optimal control of distributive systems, and certain ill-posed variational problems.     

Lower negative decision number in a graph

Let G=(V,E) be a graph. A function f:V(G)→{?1,1} is called bad if ∑ _v∈N(v) f(v)≤1 for every v∈V(G). A bad function f of a graph G is maximal if there exists no bad function g such that g≠f and g(v)≥f(v) for every v∈V. The minimum of the values of ∑ _v∈V f(v), taken over all maximal bad functions f, is called the lower negative decision number and is denoted by β _D ^* (G). In this paper, we present sharp lower bounds on this number for regular graphs and nearly regular graphs, and we also characterize the graphs attaining those bounds.     

Polynomial addition sets and polynomial digraphs

Let G be a group of order v, and f(x) be a nonzero integral polynomial. A (v, k, f(x))-polynomial addition set in G is a subset D of G with k distinct elements such that f(Σ_d∈Dd) = λΣ_g∈Gg for some integer λ. We discuss some general properties of polynomial addition sets. The relation between polynomial addition sets and polynomial Cayley digraphs is studied and, in particular, some new results on Cayley xⁿ-digraphs and strongly regular Cayley graphs are obtained. Finally, a complete list of polynomial addition sets with certain restrictions on parameters is given.