Embedding cycles of various lengths into star graphs with both edge and vertex faults

The n-dimensional star graph S_n is an attractive alternative to the hypercube graph and is a bipartite graph with two partite sets of equal size. Let F_v and F_e be the sets of faulty vertices and faulty edges of S_n, respectively. We prove that S_n − F_v − F_e contains a fault-free cycle of every even length from 6 to n! − 2∣F_v∣ with ∣F_v∣ + ∣F_e∣ ? n − 3 for every n ? 4. We also show that S_n − F_v − F_e contains a fault-free path of length n! − 2∣F_v∣ − 1 (respectively, n! − 2∣F_v∣ − 2) between two arbitrary vertices of S_n in different partite sets (respectively, the same partite set) with ∣F_v∣ + ∣F_e∣ ? n − 3 for every n ? 4.     

Fault tolerance of vertex pancyclicity in alternating group graphs

We study fault tolerance of vertex k pancyclicity of the alternating group graph AG_n. A graph G is vertex k pancyclic, if for every vertex p∈G, there is a cycle going through p of every length from k to |G|. Xue and Liu [Z.-J. Xue, S.-Y. Liu, An optimal result on fault-tolerant cycle-embedding in alternating group graphs, Inform. Proc. Lett. 109 (2009) 1197-1201] put the conjecture that AG_n is (2n-7)-fault-tolerant vertex pancyclic, which means that if the number of faults |F|?2n-7, then AG_n-F is still vertex pancyclic. Chang and Yang [J.-M. Chang, J.-S. Yang, Fault-tolerant cycle-embedding in alternating group graphs, Appl. Math. Comput. 197 (2008) 760-767] showed that for the shortest cycles the fault-tolerance of AG_n is much lower. They noted that with n-2 faults one can cut all 3-cycles going through a given vertex p (it is easy to observe that the same set of faults cuts all 4- and 5-cycles going through p). On the other hand they show that AG_n is n-3-fault tolerant vertex 3 pancyclic. In this paper we show that the cycles of length ?6 are much more fault-tolerant. More precisely, we show that AG_n is (2n-6)-fault-tolerant vertex 6 pancyclic. This bound is optimal, because every vertex p has 2n-4 neighbors.     

Bipanconnectivity of faulty hypercubes with minimum degree

In this paper, we consider the conditionally faulty hypercube Q_n with n ? 2 where each vertex of Q_n is incident with at least m fault-free edges, 2 ? m ? n − 1. We shall generalize the limitation m ? 2 in all previous results of edge-bipancyclicity. We also propose a new edge-fault-tolerant bipanconnectivity called k-edge-fault-tolerant bipanconnectivity. A bipartite graph is k-edge-fault-tolerant bipanconnected if G − F remains bipanconnected for any F ⊂ E(G) with ∣F∣ ? k. For every integer m, under the same hypothesis, we show that Q_n is (n − 2)-edge-fault-tolerant edge-bipancyclic and bipanconnected, and the results are optimal with respect to the number of edge faults tolerated. This not only improves some known results on edge-bipancyclicity and bipanconnectivity of hypercubes, but also simplifies the proof.     

On the logarithmic coefficients of Bazilevic? functions

The objective of the present paper is to study the logarithmic coefficients of Bazilevic? functions. We obtain the inequality ∣γ_n∣ ? An⁻¹logn (A is an absolute constant) which holds for Bazilevic? functions.     

Strong linear preservers of rank reverse permutability on triangular matrices

Let F be a field with ∣F∣ > 2 and T_n(F) be the set of all n × n upper triangular matrices, where n ? 2. Let k ? 2 be a given integer. A k-tuple of matrices A₁, …, A_k ∈ T_n(F) is called rank reverse permutable if rank(A₁ A₂ ? A_k) = rank(A_k A_k−1 ? A₁). We characterize the linear maps on T_n(F) that strongly preserve the set of rank reverse permutable matrix k-tuples.     

Alexandrov’s inequality and conjectures on some Toeplitz matrices

We study determinant inequalities for certain Toeplitz-like matrices over C. For fixed n and N ? 1, let Q be the n × (n + N − 1) zero-one Toeplitz matrix with Q_ij = 1 for 0 ? j − i ? N − 1 and Q_ij = 0 otherwise. We prove that det(QQ^∗) is the minimum of det(RR^∗) over all complex matrices R with the same dimensions as Q satisfying ∣R_ij∣ ? 1 whenever Q_ij = 1 and R_ij = 0 otherwise. Although R has a Toeplitz-like band structure, it is not required to be actually Toeplitz. Our proof involves Alexandrov’s inequality for polarized determinants and its generalizations. This problem is motivated by Littlewood’s conjecture on the minimum 1-norm of N-term exponential sums on the unit circle. We also discuss polarized Bazin-Reiss-Picquet identities, some connections with k-tree enumeration, and analogous conjectured inequalities for the elementary symmetric functions of QQ^∗.     

On generalized absolute Cesàro summability

In this paper, a known result on ∣C, α; δ∣_k summability factors has been generalized for ∣C, α, γ; δ∣_k summability factors. Some new results have also been obtained.     

Landau’s theorem for functions with logharmonic Laplacian

In this paper, we show the existence of Landau constant for functions with logharmonic Laplacian of the form F(z) = ∣z∣²L(z) + K(z), ∣z∣ < 1, where L is logharmonic and K is harmonic. Moreover, the problem of minimizing the area is solved     

Estimation of flows in flow networks

Let G be a directed graph with an unknown flow on each edge such that the following flow conservation constraint is maintained: except for sources and sinks, the sum of flows into a node equals the sum of flows going out of a node. Given a noisy measurement of the flow on each edge, the problem we address, which we call the Most Probable Flow Estimation problem (MPFE), is to estimate the most probable assignment of flow for every edge such that the flow conservation constraint is maintained. We provide an algorithm called ΔY-mpfe for solving the MPFE problem when the measurement error is Gaussian (Gaussian-MPFE). The algorithm works in O(∣E∣ + ∣V∣²) when the underlying undirected graph of G is a 2-connected planar graph, and in O(∣E∣ + ∣V∣) when it is a 2-connected serial-parallel graph or a tree. This result is applicable to any Minimum Cost Flow problem for which the cost function is τ_e(X_e − μ_e)² for edge e where μ_e and τ_e are constants, and X_e is the flow on edge e. We show that for all topologies, the Gaussian-MPFE’s precision for each edge is analogous to the equivalent resistance measured in series to this edge in an electrical network built by replacing every edge with a resistor reflecting the measurement’s precision on that edge.     

New results on the energy of integral circulant graphs

Circulant graphs are an important class of interconnection networks in parallel and distributed computing. Integral circulant graphs play an important role in modeling quantum spin networks supporting the perfect state transfer as well. The integral circulant graph ICG_n(D) has the vertex set Z_n = {0, 1, 2, … , n − 1} and vertices a and b are adjacent if gcd(a − b, n) ∈ D, where D ⊆ {d : d∣n, 1 ? d < n}. These graphs are highly symmetric, have integral spectra and some remarkable properties connecting chemical graph theory and number theory. The energy of a graph was first defined by Gutman, as the sum of the absolute values of the eigenvalues of the adjacency matrix. Recently, there was a vast research for the pairs and families of non-cospectral graphs having equal energies. Following Bapat and Pati [R.B. Bapat, S. Pati, Energy of a graph is never an odd integer, Bull. Kerala Math. Assoc. 1 (2004) 129-132], we characterize the energy of integral circulant graph modulo 4. Furthermore, we establish some general closed form expressions for the energy of integral circulant graphs and generalize some results from Ili? [A. Ili?, The energy of unitary Cayley graphs, Linear Algebra Appl. 431 (2009), 1881-1889]. We close the paper by proposing some open problems and characterizing extremal graphs with minimal energy among integral circulant graphs with n vertices, provided n is even.     

Super connectivity of k-regular interconnection networks

Super connectivity is an important issue in interconnection networks. It has been shown that if a network possesses the super connectivity property, it has a high reliability and a small vertex failure rate. Many interconnection networks, like the hypercubes, twisted-cubes, crossed-cubes, möbius cubes, split-stars, and recursive circulant graphs, are proven to be super connected; and the augmented cubes are maximum connected. However, each network vertex has a higher degree as long as the number of vertices increases exponentially. For example, each vertex of the hypercube Q_n has a degree of n, and each vertex of the augmented cube AQ_n has a degree of 2n − 1. In this paper, we not only show that the augmented cube AQ_n is super connected for n = 1, 2 and n ? 4, but also propose a variation of AQ_n, denoted by AQ_n,i, such that V(AQ_n,i) = V(AQ_n), E(AQ_n,i) ⊆ E(AQ_n), and AQ_n,i is i-regular with n ? 3 and 3 ? i ? 2n − 1, in which AQ_n,i is also super connected. In addition, we state the diameter of AQ_n,i.     

Bounds on the vertex–edge domination number of a tree

A vertex–edge dominating set of a graph G is a set D of vertices of G such that every edge of G is incident with a vertex of D or a vertex adjacent to a vertex of D. The vertex–edge domination number of a graph G  , denoted by γ_ve(T)${\gamma }_{\mathrm{ve}}(T)$, is the minimum cardinality of a vertex–edge dominating set of G. We prove that for every tree T   of order n?3$n?3$ with l leaves and s   support vertices, we have (n−l−s+3)/4?γ_ve(T)?n/3$(n-l-s+3)/4?{\gamma }_{\mathrm{ve}}(T)?n/3$, and we characterize the trees attaining each of the bounds.     

Cycle embedding in star graphs with more conditional faulty edges

The star graph is one of the most attractive interconnection networks. The cycle embedding problem is widely discussed in many networks, and edge fault tolerance is an important issue for networks since edge failures may occur when a network is put into use. In this paper, we investigate the cycle embedding problem in star graphs with conditional faulty edges. We show that there exist fault-free cycles of all even lengths from 6 to n! in any n-dimensional star graph S_n (n ? 4) with ?3n − 10 faulty edges in which each node is incident with at least two fault-free edges. Our result not only improves the previously best known result where the number of tolerable faulty edges is up to 2n − 7, but also extends the result that there exists a fault-free Hamiltonian cycle under the same condition.     

k-Potence preserving maps without the linearity and surjectivity assumptions

Let M_n be the space of all n × n complex matrices, and let Γ_n be the subset of M_n consisting of all n × n k-potent matrices. We denote by Ψ_n the set of all maps on M_n satisfying A − λB ∈ Γ_n if and only if ?(A) − λ?(B) ∈ Γ_n for every A,B ∈ M_n and λ ∈ C. It was shown that ? ∈ Ψ_n if and only if there exist an invertible matrix P ∈ M_n and c ∈ C with c^k−1 = 1 such that either ?(A) = cPAP⁻¹ for every A ∈ M_n, or ?(A) = cPA^TP⁻¹ for every A ∈ M_n.     

On polyvectors of vector spaces and hyperplanes of projective Grassmannians

We investigate relationships between polyvectors of a vector space V, alternating multilinear forms on V, hyperplanes of projective Grassmannians and regular spreads of projective spaces. Suppose V is an n-dimensional vector space over a field F and that A_n-1,k(F) is the Grassmannian of the (k − 1)-dimensional subspaces of PG(V) (1  ? k ? n − 1). With each hyperplane H of A_n-1,k(F), we associate an (n − k)-vector of V (i.e., a vector of ∧^n−kV) which we will call a representative vector of H. One of the problems which we consider is the isomorphism problem of hyperplanes of A_n-1,k(F), i.e., how isomorphism of hyperplanes can be recognized in terms of their representative vectors. Special attention is paid here to the case n = 2k and to those isomorphisms which arise from dualities of PG(V). We also prove that with each regular spread of the projective space PG(2k-1,F), there is associated some class of isomorphic hyperplanes of the Grassmannian A_2k-1,k(F), and we study some properties of these hyperplanes. The above investigations allow us to obtain a new proof for the classification, up to equivalence, of the trivectors of a 6-dimensional vector space over an arbitrary field F, and to obtain a classification, up to isomorphism, of all hyperplanes of A_5,3(F).     

On general summability factor theorem of infinite series

A lower triangular matrix with nonzero principal diagonal entries is called a triangle. In this paper we obtain the sufficient conditions for ∑a_nλ_n to be summable ∣A∣_k whenever ∑a_n is summable ∣T∣_k for a triangle T.     

On the extendability of Bi-Cayley graphs of finite abelian groups

Let G be a finite group and A a nonempty subset (possibly containing the identity element) of G. The Bi-Cayley graph X=BC(G,A) of G with respect to A is defined as the bipartite graph with vertex set G×{0,1} and edge set {{(g,0),(sg,1)}∣g∈G,s∈A}. A graph Γ admitting a perfect matching is called n-extendable if ∣V(Γ)∣≥2n+2 and every matching of size n in Γ can be extended to a perfect matching of Γ. In this paper, the extendability of Bi-Cayley graphs of finite abelian groups is explored. In particular, 2-extendable and 3-extendable Bi-Cayley graphs of finite abelian groups are characterized.     

On p-quasi-hyponormal operators

A Hilbert space operator A ∈ B(H) is said to be p-quasi-hyponormal for some 0 < p ? 1, A ∈ p − QH, if A^∗(∣A∣^2p − ∣A^∗∣^2p)A ? 0. If H is infinite dimensional, then operators A ∈ p − QH are not supercyclic. Restricting ourselves to those A ∈ p − QH for which A⁻¹(0) ⊆ A^∗-1(0), A ∈ p_∗ − QH, a necessary and sufficient condition for the adjoint of a pure p_∗ − QH operator to be supercyclic is proved. Operators in p_∗ − QH satisfy Bishop’s property (β). Each A ∈ p_∗ − QH has the finite ascent property and the quasi-nilpotent part H₀(A − λI) of A equals (A − λI)^-1(0) for all complex numbers λ; hence f(A) satisfies Weyl’s theorem, and f(A^∗) satisfies a-Weyl’s theorem, for all non-constant functions f which are analytic on a neighborhood of σ(A). It is proved that a Putnam-Fuglede type commutativity theorem holds for operators in p_∗ − QH.