Connectivity of Strong Products of Graphs

The strong product ${G\boxtimes H}$ of graphs G = (V ₁, E ₁) and H = (V ₂, E ₂) is the graph with vertex set ${V(G \boxtimes H)=V_1\times V_2}$ , where two distinct vertices ${(x_1, x_2), (y_1, y_2)\in V_1\times V_2}$ are adjacent in ${G\boxtimes H}$ if and only if x _i  = y _i or ${x_i y_i\in E_i}$ for i = 1, 2. We introduce so called I-sets and L-sets in the strong product ${G\boxtimes H}$ and prove that every minimum separating set in ${G\boxtimes H}$ is either an I-set or an L-set in ${G\boxtimes H}$ . Some bounds and exact results for connectivity of strong products follow from this characterization. The result is then generalized to an arbitrary number of factors in the strong product.     

The maximal Fejér operator on the spacesH p (R×···×R)

It is shown that the maximal operator of the Fejér means of a tempered distribution is bounded from thed-dimensional Hardy spaceH _p (R×···×R) toL _p (R ^d ) (1/2<p<∞) and is of weak type (H ₁ ^?i ,L ₁) (i=1,…,d), where the Hardy spaceH ₁ ^?i is defined by a hybrid maximal function. As a consequence, we obtain that the Fejér means of a functionf ∈H ₁ ^?i ?L(logL) ^d?1 converge a.e. to the function in question. Moreover, we prove that the Fejér means are uniformly bounded onH _p (R×···×R) whenever 1/2<p<∞. Thus, in casef ∈H _p (R×···×R) the Fejér means converge tof inH _p (R×···×R) norm. The same results are proved for the conjugate Fejér means, too.     

Some remarks on the existence of optimal controls for quasilinear systems

Let a quasilinear control system having the state space \(\bar X \subseteq R^n \) be governed by the vector differential equation $$\dot x = G(u(t))x,$$ wherex(0) =x ₀ andU is the family of all bounded measurable functions from [0,T] intoU, a compact and convex subset ofR ^m.LetG:U ?R be a bounded measurable nonlinear function, such thatG(U) is compact and convex.G ^?1 can be convex onG(U) or concave. The main results of the paper establish the existence of a controlu ∈U which minimizes the cost functional $$I(u) = \int_0^T {L(u(t))x(t)dt,} $$ whereL(·) is convex. A practical example of application for chemical reactions is worked out in detail.     

A Note on the Roman Bondage Number of Planar Graphs

A Roman dominating function on a graph G = (V(G), E(G)) is a labelling ${f : V(G)\rightarrow \{0,1,2\}}$ satisfying the condition that every vertex with label 0 has at least a neighbour with label 2. The Roman domination number γ _R (G) of G is the minimum of ${\sum_{v \in V(G)}{f(v)}}$ over all such functions. The Roman bondage number b _R (G) of G is the minimum cardinality of all sets ${E\subseteq E(G)}$ for which γ _R (G \ E) > γ _R (G). Recently, it was proved that for every planar graph P, b _R (P) ≤ Δ(P) + 6, where Δ(P) is the maximum degree of P. We show that the Roman bondage number of every planar graph does not exceed 15 and construct infinitely many planar graphs with Roman bondage number equal to 7.     

Rainbow Connection Number, Bridges and Radius

Let G be a connected graph. The notion of rainbow connection number rc(G) of a graph G was introduced by Chartrand et al. (Math Bohem 133:85–98, 2008). Basavaraju et al. (arXiv:1011.0620v1 [math.CO], 2010) proved that for every bridgeless graph G with radius r, ${rc(G)\leq r(r+2)}$ and the bound is tight. In this paper, we show that for a connected graph G with radius r and center vertex u, if we let D ^r  = {u}, then G has r?1 connected dominating sets ${ D^{r-1}, D^{r-2},\ldots, D^{1}}$ such that ${D^{r} \subset D^{r-1} \subset D^{r-2} \cdots\subset D^{1} \subset D^{0}=V(G)}$ and ${rc(G)\leq \sum_{i=1}^{r} \max \{2i+1,b_i\}}$ , where b _i is the number of bridges in E[D ⁱ , N(D ⁱ )] for ${1\leq i \leq r}$ . From the result, we can get that if ${b_i\leq 2i+1}$ for all ${1\leq i\leq r}$ , then ${rc(G)\leq \sum_{i=1}^{r}(2i+1)= r(r+2)}$ ; if b _i  > 2i + 1 for all ${1\leq i\leq r}$ , then ${rc(G)= \sum_{i=1}^{r}b_i}$ , the number of bridges of G. This generalizes the result of Basavaraju et al. In addition, an example is given to show that there exist infinitely graphs with bridges whose rc(G) is only dependent on the radius of G, and another example is given to show that there exist infinitely graphs with bridges whose rc(G) is only dependent on the number of bridges in G.     

The reconstruction problem for certain infinite graphs

We are concerned with the notion of the degree-type (D _G ⁱ )_i∈ω of a graphG, whereD _G ⁱ is defined to be the number of vertices inG with degreei. In the first section the following results are proven:

1. IfG is a connected, locally finite, countably infinite graph such that there exists ani so thatD _G ⁱ andD _G ⁱ⁺¹ are both finite and different from 0, thenG is reconstructible.
2. Locally finite, countably infinite graphsG, for which infinitely manyD _G ⁱ are different from 0 but only finitely manyD _G ⁱ are infinite, are reconstructible.

In the second section we give some results about the reconstructibility of certain locally finite countably infinite interval graphs and show that a reconstruction of a planar, infinite graph has to be planar too.     

Isotone maps on lattices

Let ${\mathcal{L} = (Li | i \in I)}$ be a family of lattices in a nontrivial lattice variety V, and let ${\varphi_{i} : L_{i} \rightarrow M}$ , for ${i \in I}$ , be isotone maps (not assumed to be lattice homomorphisms) to a common lattice M (not assumed to lie in V). We show that the maps ${\varphi_{i}}$ can be extended to an isotone map ${\varphi : L \rightarrow M}$ , where ${L = {\rm Free}_{V} \mathcal{L}}$ is the free product of the L _i in V. This was known for V = L, the variety of all lattices. The above free product L can be viewed as the free lattice in V on the partial lattice P formed by the disjoint union of the L _i . The analog of the above result does not, however, hold for the free lattice L on an arbitrary partial lattice P. We show that the only codomain lattices M for which that more general statement holds are the complete lattices. On the other hand, we prove the analog of our main result for a class of partial lattices P that are not-quite-disjoint unions of lattices. We also obtain some results similar to our main one, but with the relationship lattices : orders replaced either by semilattices : orders or by lattices : semilattices. Some open questions are noted.     

When is the radical associated with a module a torsion?

For an arbitrary R-module M we consider the radical (in the sense of Maranda)G _M, namely, the largest radical among all radicalsG, such thatG(M). We determine necessary and sufficient on M in order for the radicalG(M) to be a torsion. In particular,G(M) is a torsion if and only if M is a pseudo-injective module.     

2-Reducible Two Paths and an Edge Constructing a Path in (2k + 1)-Edge-Connected Graphs

Let k ≥ 5 be an odd integer and G = (V(G), E(G)) be a k-edge-connected graph. For ${X\subseteq V(G),e(X)}$ denotes the number of edges between X and V(G) ? X. We here prove that if ${\{s_i,t_i\}\subseteq X_i\subseteq V(G)(i=1,2),f}$ is an edge between s ₁ and ${s_2,X_1\cap X_2=\emptyset,e(X_1)\le 2k-3,e(X_2)\le 2k-2}$ , and e(Y) ≥ k + 1 for each ${Y\subseteq V(G)}$ with ${Y\cap\{s_1,t_1,s_2,t_2\}=\{s_1,t_2\}}$ , then there exist paths P ₁ and P ₂ such that P _i joins s _i and ${t_i,V(P_i)\subseteq X_i}$ (i = 1, 2) and ${G-f-E(P_1\cup P_2)}$ is (k ? 2)-edge-connected, and in fact we give a generalization of this result.     

Minimal decompositions of graphs into mutually isomorphic subgraphs

SupposeG _n={G ₁, ...,G _k } is a collection of graphs, all havingn vertices ande edges. By aU-decomposition ofG _n we mean a set of partitions of the edge setsE(G _t ) of theG _i , sayE(G _t )== \(\sum\limits_{j = 1}^r {E_{ij} } \) E _ij , such that for eachj, all theE _ij , 1≦i≦k, are isomorphic as graphs. Define the functionU(G _n) to be the least possible value ofr aU-decomposition ofG _n can have. Finally, letU _k (n) denote the largest possible valueU(G) can assume whereG ranges over all sets ofk graphs havingn vertices and the same (unspecified) number of edges. In an earlier paper, the authors showed that $$U_2 (n) = \frac{2}{3}n + o(n).$$ In this paper, the value ofU _k (n) is investigated fork>2. It turns out rather unexpectedly that the leading term ofU _k (n) does not depend onk. In particular we show $$U_k (n) = \frac{3}{4}n + o_k (n),k \geqq 3.$$      

Eulerian graphs and automorphisms of a maximal graph

Let R be a commutative ring with identity. Let Γ(R) denote the maximal graph corresponding to the non-unit elements of R, i.e., Γ(R) is a graph with vertices the non-unit elements of R, where two distinct vertices a and b are adjacent if and only if there is a maximal ideal of R containing both. In this paper, we have shown that, for any finite ring R which is not a field, Γ(R) is a Euler graph if and only if R has odd cardinality. Moreover, for any finite ring R ? R ₁×R ₂× · · · ×R _n, where the R _i is a local ring of cardinality p _i ^αi for all i, and the p _i’s are distinct primes, it is shown that Aut(Γ(R)) is isomorphic to a finite direct product of symmetric groups. We have also proved that clique(G(R)’) = χ(G(R)’) for any semi-local ring R, where G(R)’ denote the comaximal graph associated to R.     

The Dual Group of a Dense Subgroup

Throughout this abstract, G is a topological Abelian group and $\hat G$ is the space of continuous homomorphisms from G into the circle group ${\mathbb{T}}$ in the compact-open topology. A dense subgroup D of G is said to determine G if the (necessarily continuous) surjective isomorphism $\hat G \to \hat D$ given by $h \mapsto h\left| D \right.$ is a homeomorphism, and G is determined if each dense subgroup of G determines G. The principal result in this area, obtained independently by L. Außenhofer and M. J. Chasco, is the following: Every metrizable group is determined. The authors offer several related results, including these. 1. There are (many) nonmetrizable, noncompact, determined groups. 2. If the dense subgroup D _i determines G _i with G _i compact, then $ \oplus _i D_i $ determines Π_i G _i. In particular, if each G _i is compact then $ \oplus _i G_i $ determines Π_i G _i. 3. Let G be a locally bounded group and let G ⁺ denote G with its Bohr topology. Then G is determined if and only if G ⁺ is determined. 4. Let non $\left( {\mathcal{N}} \right)$ be the least cardinal κ such that some $X \subseteq {\mathbb{T}}$ of cardinality κ has positive outer measure. No compact G with $w\left( G \right) \geqslant non\left( {\mathcal{N}} \right)$ is determined; thus if $\left( {\mathcal{N}} \right) = {\mathfrak{N}}_1 $ (in particular if CH holds), an infinite compact group G is determined if and only if w(G) = ω. Question. Is there in ZFC a cardinal κ such that a compact group G is determined if and only if w(G) < κ? Is $\kappa = non\left( {\mathcal{N}} \right)?\kappa = {\mathfrak{N}}_1 ?$      

Difference Sets in {\mathbb{Z}}_4^m and {\mathbb{F}}_2^{2m}

Let R=GR(4,m) be the Galois ring of cardinality 4^m and let T be the Teichmüller system of R. For every map λ of T into { -1,+1} and for every permutation Π of T, we define a map φ _λ ^Π of Rinto { -1,+1} as follows: if x∈R and if x=a+2b is the 2-adic representation of x with x∈T and b∈T, then φ _λ ^Π (x)=λ(a)+2Tr(Π(a)b), where Tr is the trace function of R . For i=1 or i=-1, define D _i as the set of x in R such thatφ _λ ^Π =i. We prove the following results: 1) D _i is a Hadamard difference set of (R,+). 2) If φ is the Gray map of R into ${\mathbb{F}}_2^{2m}$ , then (D _i) is a difference set of ${\mathbb{F}}_2^{2m}$ . 3) The set of D _i and the set of φ(D _i) obtained for all maps λ and Π, both are one-to-one image of the set of binary Maiorana-McFarland difference sets in a simple way. We also prove that special multiplicative subgroups of R are difference sets of kind D _i in the additive group of R. Examples are given by means of morphisms and norm in R.     

On the SIG-Dimension of Trees Under the L ∞-Metric

Let ${{\mathcal P},}$ where ${|{\mathcal P}| \geq 2,}$ be a set of points in d-dimensional space with a given metric ρ. For a point ${p \in {\mathcal P},}$ let r _p be the distance of p with respect to ρ from its nearest neighbor in ${{\mathcal P}.}$ Let B(p,r _p ) be the open ball with respect to ρ centered at p and having the radius r _p . We define the sphere-of-influence graph (SIG) of ${{\mathcal P}}$ as the intersection graph of the family of sets ${\{B(p,r_p)\ | \ p\in {\mathcal P}\}.}$ Given a graph G, a set of points ${{\mathcal P}_G}$ in d-dimensional space with the metric ρ is called a d-dimensional SIG-representation of G, if G is isomorphic to the SIG of ${{\mathcal P}_G.}$ It is known that the absence of isolated vertices is a necessary and sufficient condition for a graph to have a SIG-representation under the L _∞-metric in some space of finite dimension. The SIG-dimension under the L _∞-metric of a graph G without isolated vertices is defined to be the minimum positive integer d such that G has a d-dimensional SIG-representation under the L _∞-metric. It is denoted by SIG _∞(G). We study the SIG-dimension of trees under the L _∞-metric and almost completely answer an open problem posed by Michael and Quint (Discrete Appl Math 127:447–460, 2003). Let T be a tree with at least two vertices. For each ${v\in V(T),}$ let leaf-degree(v) denote the number of neighbors of v that are leaves. We define the maximum leaf-degree as ${\alpha(T) = \max_{x \in V(T)}}$ leaf-degree(x). Let ${ S = \{v\in V(T)\|\}}$ leaf-degree{(v) = α}. If |S| = 1, we define β(T) = α(T) ? 1. Otherwise define β(T) = α(T). We show that for a tree ${T, SIG_\infty(T) = \lceil \log_2(\beta + 2)\rceil}$ where β = β (T), provided β is not of the form 2 ^k ? 1, for some positive integer k ≥ 1. If β = 2 ^k ? 1, then ${SIG_\infty (T) \in \{k, k+1\}.}$ We show that both values are possible.     

On conjugate characteristic polynomial of a graph

Let $c=a+b\sqrt{m}$ and $\overline{c}=a-b\sqrt{m}$ , where a and b are two nonzero integers and m is a positive integer such that m is not a perfect square. We say that A ^c =[c _ij ] is the conjugate adjacency matrix of a graph G if c _ij =c for any two adjacent vertices i and j, $c_{ij}=\overline{c}$ for any two nonadjacent vertices i and j, and c _ij =0 if i=j. Let P _G ^c (λ)=|λ I?A ^c | denote the conjugate characteristic polynomial of G. Further, let e=e(G) and Δ=Δ(G) be the number of edges and number of triangles of G, respectively. Let G and H be two graphs of order n and let e(G)=e(H). In this work we prove that c ₃(G)=c ₃(H) if and only if Δ(G)=Δ(H) and $\Delta(\overline{G})=\Delta(\overline{H})$ , where $\overline{G}$ denotes the complement of G and c _k is the coefficient which corresponds to λ ^n?k with respect to P _G ^c (λ). Besides, we here give the conjugate spectrum and conjugate characteristic polynomial of all connected graphs of order n=2,3,4,5, with respect to the constant $c=1+\sqrt{2}$ .     

Ultrapowers ofL 1(μ) and the subsequence splitting principle

We study the ultrapowers $L_1 (\mu )_\mathfrak{U} $ of aL ₁(μ) space, by describing the components of the well-known representation $L_1 (\mu )_\mathfrak{U} = L_1 (\mu _\mathfrak{U} ) \oplus _1 L_1 (\nu _\mathfrak{U} )$ , and we give a representation of the projection from $L_1 (\mu )_\mathfrak{U} $ onto $L_1 (\mu _\mathfrak{U} )$ . Moreover, the subsequence splitting principle forL ₁(μ) motivates the following question: if $\mathfrak{V}$ is an ultrafilter on ? and $[f_i ] \in L_1 (\mu )_\mathfrak{V} $ , is it possible to find a weakly convergent sequence (g _i ) ?L ₁(μ) following $\mathfrak{V}$ and a disjoint sequence (h _i ) ?L ₁(μ) such that [f _i ]=[g _i ]+[h _i ]? If $\mathfrak{V}$ is a selective ultrafilter, we find a positive answer by showing that $f = [f_i ] \in L_1 (\mu )_\mathfrak{V} $ belongs to $L_1 (\mu _{_\mathfrak{V} } )$ if and only if its representatives {f _i } are weakly convergent following $\mathfrak{V}$ and $f \in L_1 (\nu _\mathfrak{V} )$ if and only if it admits a representative consisting of pairwise disjoint functions. As a consequence, we obtain a new proof of the subsequence splitting principle. If $\mathfrak{V}$ is not a p-point then the above characterizations of $L_1 (\nu _{_\mathfrak{V} } )$ and $L_1 (\nu _{_\mathfrak{V} } )$ fail and the answer to the question is negative.     

A Congruence Connecting Latin Rectangles and Partial Orthomorphisms

A partial orthomorphism of ${\mathbb{Z}_{n}}$ is an injective map ${\sigma : S \rightarrow \mathbb{Z}_{n}}$ such that ${S \subseteq \mathbb{Z}_{n}}$ and ??(i)?Ci ? ??(j)? j (mod n) for distinct ${i, j \in S}$ . We say ?? has deficit d if ${|S| = n - d}$ . Let ??(n, d) be the number of partial orthomorphisms of ${\mathbb{Z}_{n}}$ of deficit d. Let ??(n, d) be the number of partial orthomorphisms ?? of ${\mathbb{Z}_n}$ of deficit d such that ??(i) ? {0, i} for all ${i \in S}$ . Then ??(n, d) =???(n, d)n ²/d ² when ${1\,\leqslant\,d < n}$ . Let R _{k, n} be the number of reduced k ×?n Latin rectangles. We show that $$R_{k, n} \equiv \chi (p, n - p)\frac{(n - p)!(n - p - 1)!^{2}}{(n - k)!}R_{k-p,\,n-p}\,\,\,\,(\rm {mod}\,p)$$ when p is a prime and ${n\,\geqslant\,k\,\geqslant\,p + 1}$ . In particular, this enables us to calculate some previously unknown congruences for R _{n, n} . We also develop techniques for computing ??(n, d) exactly. We show that for each a there exists??? _a such that, on each congruence class modulo??? _a , ??(n, n-a) is determined by a polynomial of degree 2a in n. We give these polynomials for ${1\,\leqslant\,a\,\leqslant 6}$ , and find an asymptotic formula for ??(n, n-a) as n ?? ??, for arbitrary fixed a.     

Teichmüller spaces for pointed Fuchsian groups

Let T(G) be the Teichmüller space of a Fuchsian group G and T(G) be the pointed Teichmüller space of a corresponding pointed Fuchsian group G.We will discuss the existence of holomorphic sections of the projection from the space M(G) of Beltrami coefficients for G to T(G) and of that from T(G) to T(G) as well.We will also study the biholomorphic isomorphisms between two pointed Teichmüller spaces.     

Every group is a maximal subgroup of a naturally occurring free idempotent generated semigroup

The study of the free idempotent generated semigroup IG(E) over a biordered set E has recently received a deal of attention. Let G be a group, let \(n\in\mathbb{N}\) with n≥3 and let E be the biordered set of idempotents of the wreath product \(G\wr \mathcal{T}_{n}\) . We show, in a transparent way, that for e∈E lying in the minimal ideal of \(G\wr\mathcal{T}_{n}\) , the maximal subgroup of e in IG(E) is isomorphic to G. It is known that \(G\wr\mathcal{T}_{n}\) is the endomorphism monoid End F _n (G) of the rank n free G-act F _n (G). Our work is therefore analogous to that of Brittenham, Margolis and Meakin for rank 1 idempotents in full linear monoids. As a corollary we obtain the result of Gray and Ru?kuc that any group can occur as a maximal subgroup of some free idempotent generated semigroup. Unlike their proof, ours involves a natural biordered set and very little machinery.     

An example of asymmetry of convolution operators

Esistono un gruppo compatto non commutativoG ^～ ed un operatore di convoluzioneT tale che: perp∈[2,4] e perq∈[1,2),T∈L _p ^p (G ^～) eT?L _q ^q (G ^～).