Network Decontamination with a Single Agent

Faults and viruses often spread in networked environments by propagating from site to neighboring sites. We model this process of network contamination by graphs. Consider a graph \(G=(V,E)\), whose vertex set is contaminated and our goal is to decontaminate the set \(V\) using mobile decontamination agents that traverse along the edge set of \(G\). Temporal immunity, \(\tau (G) \ge 0\), is defined as the time that a decontaminated vertex of \(G\) can remain continuously exposed to some contaminated neighbor without getting infected itself. The immunity number of \(G\), \(\iota _k(G)\), is the least \(\tau (G)\) that is required to decontaminate \(G\) using \(k\) agents. We study immunity number for some classes of graphs corresponding to network topologies and present upper bounds on \(\iota _1(G)\), in some cases, with matching lower bounds. Variations of this problem have been extensively studied in literature, but proposed algorithms have been restricted to monotone strategies, where a vertex, once decontaminated, may not be recontaminated. We exploit nonmonotonicity to give bounds which are strictly better than those derived using monotone strategies.     

Robust optimization for routing problems on trees

The prize-collecting travelling salesman problem (pc-tsp) is a known variant of the classical travelling salesman problem. In the pc-tsp, we are given a weighted graph \(G=(V,E)\) with edge weights \(\ell :E\rightarrow {\mathbb {R}}_+\), a special vertex \(r\in V\), penalties \(\pi :V\rightarrow {\mathbb {R}}_+\) and the goal is to find a closed tour K such that \(r\in V(K)\) and such that the cost \(\ell (K)+\pi (V{\setminus } V(K))\), which is the sum of the weights of the edges in the tour and the cost of the vertices not spanned by K, is minimized. In this paper, we study the pc-tsp from a viewpoint of robust optimization. In our setting, an operator must find a closed tour in a (known) edge-weighted tree \(T=(V,E)\) starting and ending in the depot r while some of the edges may be blocked by “avalanches” defining the scenario \(\xi \). The cost \(f(K,\xi )\) of a tour K in scenario \(\xi \) is the cost resulting from “shortcutting” K, i.e. from restricting K to the nodes which are reachable from r in scenario \(\xi \), i.e. in the graph \(T {\setminus } \xi =(V,E{\setminus }\xi )\). In the absolute robust version of the problem one searches for a tour which minimizes the worst-case cost over all scenarios, while in the deviation robust counterpart, the regret, that is, the deviation from an optimum solution for a particular scenario, is sought to be minimized. We show that both versions of the problem can be solved in polynomial time on trees.     

On the eigenvalues and spectral radius of starlike trees

Let \(k\ge 1\) and \(n_1,\ldots ,n_k\ge 1\) be some integers. Let \(S(n_1,\ldots ,n_k)\) be a tree T such that T has a vertex v of degree k and \(T{\setminus } v\) is the disjoint union of the paths \(P_{n_1},\ldots ,P_{n_k}\), that is \(T{\setminus } v\cong P_{n_1}\cup \cdots \cup P_{n_k}\) so that every neighbor of v in T has degree one or two. The tree \(S(n_1,\ldots ,n_k)\) is called starlike tree, a tree with exactly one vertex of degree greater than two, if \(k\ge 3\). In this paper we obtain the eigenvalues of starlike trees. We find some bounds for the largest eigenvalue (for the spectral radius) of starlike trees. In particular we prove that if \(k\ge 4\) and \(n_1,\ldots ,n_k\ge 2\), then \(\frac{k-1}{\sqrt{k-2}}<\lambda _1(S(n_1,\ldots ,n_k))<\frac{k}{\sqrt{k-1}}\), where \(\lambda _1(T)\) is the largest eigenvalue of T. Finally we characterize all starlike trees that all of whose eigenvalues are in the interval \((-2,2)\).     

A characterization of the desarguesian and the Figueroa planes of order $$q^{3}$$

Let \(\Pi \) be a plane of order \(q^{3}\), \(q>2\), admitting \(G\cong PGL(3,q)\) as a collineation group. By Dempwolff (Geometriae Dedicata 18:101–112, 1985) the plane \(\Pi \) contains a G-invariant subplane \(\pi _{0}\) isomorphic to PG(2, q) on which G acts 2-transitively. In this paper it is shown that, if the homologies of \(\pi _{0}\) contained in G extend to \(\Pi \) then \(\Pi \) is either the desarguesian or the Figueroa plane.     

Packing chromatic number versus chromatic and clique number

The packing chromatic number \(\chi _{\rho }(G)\) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets \(V_i\), \(i\in [k]\), where each \(V_i\) is an i-packing. In this paper, we investigate for a given triple (a, b, c) of positive integers whether there exists a graph G such that \(\omega (G) = a\), \(\chi (G) = b\), and \(\chi _{\rho }(G) = c\). If so, we say that (a, b, c) is realizable. It is proved that \(b=c\ge 3\) implies \(a=b\), and that triples \((2,k,k+1)\) and \((2,k,k+2)\) are not realizable as soon as \(k\ge 4\). Some of the obtained results are deduced from the bounds proved on the packing chromatic number of the Mycielskian. Moreover, a formula for the independence number of the Mycielskian is given. A lower bound on \(\chi _{\rho }(G)\) in terms of \(\Delta (G)\) and \(\alpha (G)\) is also proved.     

Some new Kirkman signal sets

A decomposition of the blocks of an \(\textsf {STS}(v)\) into partial parallel classes of size m is equivalent to a Kirkman signal set \(\textsf {KSS}(v,m)\). We give decompositions of \(\textsf {STS}(4v-3)\) into classes of size \(v-1\) when \(v \equiv 3 \pmod {6}\), \(v \not = 3\). We also give decompositions of \(\textsf {STS}(v)\) into classes of various sizes when v is a product of two arbitrary integers that are both congruent to \(3 \pmod {6}\). These results produce new families of \(\textsf {KSS}(v,m)\).     

A new theorem on the prime-counting function

For \(x>0\), let \(\pi (x)\) denote the number of primes not exceeding x. For integers a and \(m>0\), we determine when there is an integer \(n>1\) with \(\pi (n)=(n+a)/m\). In particular, we show that, for any integers \(m>2\) and \(a\leqslant \lceil e^{m-1}/(m-1)\rceil \), there is an integer \(n>1\) with \(\pi (n)=(n+a)/m\). Consequently, for any integer \(m>4\), there is a positive integer n with \(\pi (mn)=m+n\). We also pose several conjectures for further research; for example, we conjecture that, for each \(m=1,2,3,\ldots \), there is a positive integer n such that \(m+n\) divides \(p_m+p_n\), where \(p_k\) denotes the k-th prime.     

Negative Ricci curvature on some non-solvable Lie groups

We show that for any non-trivial representation \((V, \pi )\) of \(\mathfrak {u}(2)\) with the center acting as multiples of the identity, the semidirect product \(\mathfrak {u}(2) \ltimes _\pi V\) admits a metric with negative Ricci curvature that can be explicitly obtained. It is proved that \(\mathfrak {u}(2) \ltimes _\pi V\) degenerates to a solvable Lie algebra that admits a metric with negative Ricci curvature. An n-dimensional Lie group with compact Levi factor \(\mathrm {SU}(2)\) admitting a left invariant metric with negative Ricci is therefore obtained for any \(n \ge 7\).     

A generalization of zero divisor graphs associated to commutative rings

Let R be a commutative ring with a nonzero identity element. For a natural number n, we associate a simple graph, denoted by \(\Gamma ^n_R\), with \(R^n\backslash \{0\}\) as the vertex set and two distinct vertices X and Y in \(R^n\) being adjacent if and only if there exists an \(n\times n\) lower triangular matrix A over R whose entries on the main diagonal are nonzero and one of the entries on the main diagonal is regular such that \(X^TAY=0\) or \(Y^TAX=0\), where, for a matrix \(B, B^T\) is the matrix transpose of B. If \(n=1\), then \(\Gamma ^n_R\) is isomorphic to the zero divisor graph \(\Gamma (R)\), and so \(\Gamma ^n_R\) is a generalization of \(\Gamma (R)\) which is called a generalized zero divisor graph of R. In this paper, we study some basic properties of \(\Gamma ^n_ R\). We also determine all isomorphic classes of finite commutative rings whose generalized zero divisor graphs have genus at most three.     

Relationships Between the 2-Metric Dimension and the 2-Adjacency Dimension in the Lexicographic Product of Graphs

Given a connected simple graph \(G=(V(G),E(G))\), a set \(S\subseteq V(G)\) is said to be a 2-metric generator for G if and only if for any pair of different vertices \(u,v\in V(G)\), there exist at least two vertices \(w_1,w_2\in S\) such that \(d_G(u,w_i)\ne d_G(v,w_i)\), for every \(i\in \{1,2\}\), where \(d_G(x,y)\) is the length of a shortest path between x and y. The minimum cardinality of a 2-metric generator is the 2-metric dimension of G, denoted by \(\dim _2(G)\). The metric \(d_{G,2}: V(G)\times V(G)\longmapsto {\mathbb {N}}\cup \{0\}\) is defined as \(d_{G,2}(x,y)=\min \{d_G(x,y),2\}\). Now, a set \(S\subseteq V(G)\) is a 2-adjacency generator for G, if for every two vertices \(x,y\in V(G)\) there exist at least two vertices \(w_1,w_2\in S\), such that \(d_{G,2}(x,w_i)\ne d_{G,2}(y,w_i)\) for every \(i\in \{1,2\}\). The minimum cardinality of a 2-adjacency generator is the 2-adjacency dimension of G, denoted by \({\mathrm {adim}}_2(G)\). In this article, we obtain closed formulae for the 2-metric dimension of the lexicographic product \(G\circ H\) of two graphs G and H. Specifically, we show that \(\dim _2(G\circ H)=n\cdot {\mathrm {adim}}_2(H)+f(G,H),\) where \(f(G,H)\ge 0\), and determine all the possible values of f(G, H).     

Upper Bounds for the Paired-Domination Numbers of Graphs

A set \(S\subseteq V\) is a paired-dominating set if every vertex in \(V{\setminus } S\) has at least one neighbor in S and the subgraph induced by S contains a perfect matching. The paired-domination number of a graph G, denoted by \(\gamma _{pr}(G)\), is the minimum cardinality of a paired-dominating set of G. A conjecture of Goddard and Henning says that if G is not the Petersen graph and is a connected graph of order n with minimum degree \(\delta (G)\ge 3\), then \(\gamma _{pr}(G)\le 4n/7\). In this paper, we confirm this conjecture for k-regular graphs with \(k\ge 4\).     

Quasi-classical generalized CRF structures

In an earlier paper, we studied manifolds M endowed with a generalized F structure \(\Phi \in \mathrm{End}(TM\oplus T^*M)\), skew-symmetric with respect to the pairing metric, such that \(\Phi ^3+\Phi =0\). Furthermore, if \(\Phi \) is integrable (in some well-defined sense), \(\Phi \) is a generalized CRF structure. In the present paper, we study quasi-classical generalized F and CRF structures, which may be seen as a generalization of the holomorphic Poisson structures (it is well known that the latter may also be defined via generalized geometry). The structures that we study are equivalent to a pair of tensor fields \((A\in \mathrm{End}(TM),\pi \in \wedge ^2TM)\), where \(A^3+A=0\) and some relations between A and \(\pi \) hold. We establish the integrability conditions in terms of \((A,\pi )\). They include the facts that A is a classical CRF structure, \(\pi \) is a Poisson bivector field and \(\mathrm{im}\,A\) is a (non)holonomic Poisson submanifold of \((M,\pi )\). We discuss the case where either \(\mathrm{ker}\,A\) or \(\mathrm{im}\,A\) is tangent to a foliation and, in particular, the case of almost contact manifolds. Finally, we show that the dual bundle of \(\mathrm{im}\,A\) inherits a Lie algebroid structure and we briefly discuss the Poisson cohomology of \(\pi \), including an associated spectral sequence and a Dolbeault type grading.     

Polynomially peripheral range-preserving maps between Banach algebras

Let A and B be two Banach function algebras and p a two variable polynomial \(p(z,w)=zw+az+bw+c\), (\(a,b,c\in {\mathbb {C}}\)). We characterize the general form of a surjection \(T: A \longrightarrow B\) which satisfies \(\mathrm{Ran}_\pi (p(Tf,Tg))\cap \mathrm{Ran}_\pi (p(f,g))\ne \emptyset , (f,g\in A\) and \(c\ne ab)\), where \(\mathrm{Ran}_\pi (f)\) is the peripheral range of f.     

The distortion dimension of $$\mathbb $$-rank 1 lattices

Let \(X=G/K\) be a symmetric space of noncompact type and rank \(k\ge 2\). We prove that horospheres in X are Lipschitz \((k-2)\)-connected if their centers are not contained in a proper join factor of the spherical building of X at infinity. As a consequence, the distortion dimension of an irreducible \(\mathbb {Q}\)-rank-1 lattice \(\Gamma \) in a linear, semisimple Lie group G of \(\mathbb R\)-rank k is \(k-1\). That is, given \(m< k-1\), a Lipschitz m-sphere S in (a polyhedral complex quasi-isometric to) \(\Gamma \), and a \((m+1)\)-ball B in X (or G) filling S, there is a \((m+1)\)-ball \(B'\) in \(\Gamma \) filling S such that \({{\mathrm{vol}}}B'\sim {{\mathrm{vol}}}B\). In particular, such arithmetic lattices satisfy Euclidean isoperimetric inequalities up to dimension \(k-1\).     

Lengths of words in transformation semigroups generated by digraphs

Given a simple digraph D on n vertices (with \(n\ge 2\)), there is a natural construction of a semigroup of transformations \(\langle D\rangle \). For any edge (a, b) of D, let \(a\rightarrow b\) be the idempotent of rank \(n-1\) mapping a to b and fixing all vertices other than a; then, define \(\langle D\rangle \) to be the semigroup generated by \(a \rightarrow b\) for all \((a,b) \in E(D)\). For \(\alpha \in \langle D\rangle \), let \(\ell (D,\alpha )\) be the minimal length of a word in E(D) expressing \(\alpha \). It is well known that the semigroup \(\mathrm {Sing}_n\) of all transformations of rank at most \(n-1\) is generated by its idempotents of rank \(n-1\). When \(D=K_n\) is the complete undirected graph, Howie and Iwahori, independently, obtained a formula to calculate \(\ell (K_n,\alpha )\), for any \(\alpha \in \langle K_n\rangle = \mathrm {Sing}_n\); however, no analogous non-trivial results are known when \(D \ne K_n\). In this paper, we characterise all simple digraphs D such that either \(\ell (D,\alpha )\) is equal to Howie–Iwahori’s formula for all \(\alpha \in \langle D\rangle \), or \(\ell (D,\alpha ) = n - \mathrm {fix}(\alpha )\) for all \(\alpha \in \langle D\rangle \), or \(\ell (D,\alpha ) = n - \mathrm {rk}(\alpha )\) for all \(\alpha \in \langle D\rangle \). We also obtain bounds for \(\ell (D,\alpha )\) when D is an acyclic digraph or a strong tournament (the latter case corresponds to a smallest generating set of idempotents of rank \(n-1\) of \(\mathrm {Sing}_n\)). We finish the paper with a list of conjectures and open problems.     

Inscribed and circumscribed polygons that characterize inner product spaces

Let X be a real normed space with unit sphere S. We prove that X is an inner product space if and only if there exists a real number \(\rho =\sqrt{(1+\cos \frac{2k\pi }{2m+1})/2}, (k=1,2,\ldots ,m; m=1,2,\ldots )\), such that every chord of S that supports \(\rho S\) touches \(\rho S\) at its middle point. If this condition holds, then every point \(u\in S\) is a vertex of a regular polygon that is inscribed in S and circumscribed about \(\rho S\).     

On Star–Wheel Ramsey Numbers

For two given graphs \(G_1\) and \(G_2\), the Ramsey number \(R(G_1,G_2)\) is the least integer r such that for every graph G on r vertices, either G contains a \(G_1\) or \(\overline{G}\) contains a \(G_2\). In this note, we determined the Ramsey number \(R(K_{1,n},W_m)\) for even m with \(n+2\le m\le 2n-2\), where \(W_m\) is the wheel on \(m+1\) vertices, i.e., the graph obtained from a cycle \(C_m\) by adding a vertex v adjacent to all vertices of the \(C_m\).     

Essentially hyponormal multiplication operators on the Dirichlet space

On the Dirichlet space D, we show that there is a multiplier f of D such that \(M_f\) is not essentially hyponormal, i.e. \(\pi (M_f)\) is not hyponormal in the Calkin algebra \(B(D)/\mathcal {K}(D)\).     

Semidefinite bounds for nonbinary codes based on quadruples

For nonnegative integers q, n, d, let \(A_q(n,d)\) denote the maximum cardinality of a code of length n over an alphabet [q] with q letters and with minimum distance at least d. We consider the following upper bound on \(A_q(n,d)\). For any k, let \(\mathcal{C}_k\) be the collection of codes of cardinality at most k. Then \(A_q(n,d)\) is at most the maximum value of \(\sum _{v\in [q]^n}x(\{v\})\), where x is a function \(\mathcal{C}_4\rightarrow {\mathbb {R}}_+\) such that \(x(\emptyset )=1\) and \(x(C)=\!0\) if C has minimum distance less than d, and such that the \(\mathcal{C}_2\times \mathcal{C}_2\) matrix \((x(C\cup C'))_{C,C'\in \mathcal{C}_2}\) is positive semidefinite. By the symmetry of the problem, we can apply representation theory to reduce the problem to a semidefinite programming problem with order bounded by a polynomial in n. It yields the new upper bounds \(A_4(6,3)\le 176\), \(A_4(7,3)\le 596\), \(A_4(7,4)\le 155\), \(A_5(7,4)\le 489\), and \(A_5(7,5)\le 87\).     

Strong extensions for q-summing o perators acting in p-convex Banach function s paces for $$1 \le p \le q$$1≤ p≤ q

Let \(1\le p\le q<\infty \) and let X be a p-convex Banach function space over a \(\sigma \)-finite measure \(\mu \). We combine the structure of the spaces \(L^p(\mu )\) and \(L^q(\xi )\) for constructing the new space \(S_{X_p}^{\,q}(\xi )\), where \(\xi \) is a probability Radon measure on a certain compact set associated to X. We show some of its properties, and the relevant fact that every q-summing operator T defined on X can be continuously (strongly) extended to \(S_{X_p}^{\,q}(\xi )\). Our arguments lead to a mixture of the Pietsch and Maurey-Rosenthal factorization theorems, which provided the known (strong) factorizations for q-summing operators through \(L^q\)-spaces when \(1 \le q \le p\). Thus, our result completes the picture, showing what happens in the complementary case \(1\le p\le q\).