Graphs with small diameter determined by their <Emphasis Type="Italic">D</Emphasis>-spectra

Let G be a connected graph with vertex set V(G) = {v₁, v₂,..., v _n }. The distance matrix D(G) = (d _ij )_n×n is the matrix indexed by the vertices of G, where d _ij denotes the distance between the vertices v _i and v _j . Suppose that λ₁(D) ≥ λ₂(D) ≥... ≥ λ _n (D) are the distance spectrum of G. The graph G is said to be determined by its D-spectrum if with respect to the distance matrix D(G), any graph having the same spectrum as G is isomorphic to G. We give the distance characteristic polynomial of some graphs with small diameter, and also prove that these graphs are determined by their D-spectra.     

Length-type parameters of finite groups with almost unipotent automorphisms

Let α be an automorphism of a finite group G. For a positive integer n, let E _G,n (α) be the subgroup generated by all commutators [...[[x,α],α],…,α] in the semidirect product G 〈α〉 over x ∈ G, where α is repeated n times. By Baer’s theorem, if E _G,n (α)=1, then the commutator subgroup [G,α] is nilpotent. We generalize this theorem in terms of certain length parameters of E _G,n (α). For soluble G we prove that if, for some n, the Fitting height of E _G,n (α) is equal to k, then the Fitting height of [G,α] is at most k + 1. For nonsoluble G the results are in terms of the nonsoluble length and generalized Fitting height. The generalized Fitting height h*(H) of a finite group H is the least number h such that F _h* (H) = H, where F ₀* (H) = 1, and F _i+1* (H) is the inverse image of the generalized Fitting subgroup F*(H/F _i *(H)). Let m be the number of prime factors of the order |α| counting multiplicities. It is proved that if, for some n, the generalized Fitting height E _G,n (α) of is equal to k, then the generalized Fitting height of [G,α] is bounded in terms of k and m. The nonsoluble length λ(H) of a finite group H is defined as the minimum number of nonsoluble factors in a normal series each of whose factors either is soluble or is a direct product of nonabelian simple groups. It is proved that if λE _G,n (α)= k, then the nonsoluble length of [G,α] is bounded in terms of k and m. We also state conjectures of stronger results independent of m and show that these conjectures reduce to a certain question about automorphisms of direct products of finite simple groups.     

Super Edge-connectivity and Zeroth-order General Randić Index for −1 ≤ <Emphasis Type="Italic">α</Emphasis> &lt; 0

Let G be a connected graph with order n, minimum degree δ = δ(G) and edge-connectivity λ = λ(G). A graph G is maximally edge-connected if λ = δ, and super edge-connected if every minimum edgecut consists of edges incident with a vertex of minimum degree. Define the zeroth-order general Randi? index \(R_\alpha ^0\left( G \right) = \sum\limits_{x \in V\left( G \right)} {d_G^\alpha \left( x \right)} \), where d_G(x) denotes the degree of the vertex x. In this paper, we present two sufficient conditions for graphs and triangle-free graphs to be super edge-connected in terms of the zeroth-order general Randi? index for ?1 ≤ α < 0, respectively.     

Note on a conjecture for the sum of signless Laplacian eigenvalues

For a simple graph G on n vertices and an integer k with 1 ? k ? n, denote by \(\mathcal{S}^+_k\) (G) the sum of k largest signless Laplacian eigenvalues of G. It was conjectured that \(\mathcal{S}^+_k(G)\leqslant{e}(G)+(^{k+1}_{\;\;2})\) (G) ? e(G) + (k+1 2), where e(G) is the number of edges of G. This conjecture has been proved to be true for all graphs when k ∈ {1, 2, n ? 1, n}, and for trees, unicyclic graphs, bicyclic graphs and regular graphs (for all k). In this note, this conjecture is proved to be true for all graphs when k = n ? 2, and for some new classes of graphs.     

Possible isolation number of a matrix over nonnegative integers

Let ?₊ be the semiring of all nonnegative integers and A an m × n matrix over ?₊. The rank of A is the smallest k such that A can be factored as an m × k matrix times a k×n matrix. The isolation number of A is the maximum number of nonzero entries in A such that no two are in any row or any column, and no two are in a 2 × 2 submatrix of all nonzero entries. We have that the isolation number of A is a lower bound of the rank of A. For A with isolation number k, we investigate the possible values of the rank of A and the Boolean rank of the support of A. So we obtain that the isolation number and the Boolean rank of the support of a given matrix are the same if and only if the isolation number is 1 or 2 only. We also determine a special type of m×n matrices whose isolation number is m. That is, those matrices are permutationally equivalent to a matrix A whose support contains a submatrix of a sum of the identity matrix and a tournament matrix.     

On a classical theorem on the diameter and minimum degree of a graph

In this work, we obtain good upper bounds for the diameter of any graph in terms of its minimum degree and its order, improving a classical theorem due to Erd¨os, Pach, Pollack and Tuza.We use these bounds in order to study hyperbolic graphs(in the Gromov sense). To compute the hyperbolicity constant is an almost intractable problem, thus it is natural to try to bound it in terms of some parameters of the graph. Let H(n, δ_0) be the set of graphs G with n vertices and minimum degree δ_0, and J(n, Δ) be the set of graphs G with n vertices and maximum degree Δ. We study the four following extremal problems on graphs: a(n, δ_0) = min{δ(G) | G ∈ H(n, δ_0)}, b(n, δ_0) = max{δ(G) |G ∈ H(n, δ_0)}, α(n, Δ) = min{δ(G) | G ∈ J(n, Δ)} and β(n, Δ) = max{δ(G) | G ∈ J(n, Δ)}. In particular, we obtain bounds for b(n, δ_0) and we compute the precise value of a(n, δ_0), α(n, Δ) andβ(n, Δ) for all values of n, δ_0 and Δ, respectively.     

Linear preservers of row-dense matrices

Let M_m,n be the set of all m × n real matrices. A matrix A ∈ M_m,n is said to be row-dense if there are no zeros between two nonzero entries for every row of this matrix. We find the structure of linear functions T: M_m,n → M_m,n that preserve or strongly preserve row-dense matrices, i.e., T(A) is row-dense whenever A is row-dense or T(A) is row-dense if and only if A is row-dense, respectively. Similarly, a matrix A ∈ M_n,m is called a column-dense matrix if every column of A is a column-dense vector. At the end, the structure of linear preservers (strong linear preservers) of column-dense matrices is found.     

On the pronormality of subgroups of odd index in finite simple symplectic groups

A subgroup H of a group G is pronormal if the subgroups H and H ^g are conjugate in 〈H,H ^g 〉 for every g ∈ G. It was conjectured in [1] that a subgroup of a finite simple group having odd index is always pronormal. Recently the authors [2] verified this conjecture for all finite simple groups other than PSL _n (q), PSU _n (q), E ₆(q), ² E ₆(q), where in all cases q is odd and n is not a power of 2, and P Sp_2n (q), where q ≡ ±3 (mod 8). However in [3] the authors proved that when q ≡ ±3 (mod 8) and n ≡ 0 (mod 3), the simple symplectic group P Sp²ⁿ (q) has a nonpronormal subgroup of odd index, thereby refuted the conjecture on pronormality of subgroups of odd index in finite simple groups.The natural extension of this conjecture is the problem of classifying finite nonabelian simple groups in which every subgroup of odd index is pronormal. In this paper we continue to study this problem for the simple symplectic groups P Sp_2n (q) with q ≡ ±3 (mod 8) (if the last condition is not satisfied, then subgroups of odd index are pronormal). We prove that whenever n is not of the form 2 ^m or 2 ^m (2^2k +1), this group has a nonpronormal subgroup of odd index. If n = 2 ^m , then we show that all subgroups of P Sp_2n (q) of odd index are pronormal. The question of pronormality of subgroups of odd index in P Sp_2n (q) is still open when n = 2 ^m (2^2k + 1) and q ≡ ±3 (mod 8).     

Thompson’s conjecture for the alternating group of degree 2<Emphasis Type="Italic">p</Emphasis> and 2<Emphasis Type="Italic">p</Emphasis>+1

For a finite group G denote by N(G) the set of conjugacy class sizes of G. In 1980s, J.G.Thompson posed the following conjecture: If L is a finite nonabelian simple group, G is a finite group with trivial center and N(G) = N(L), then G ? L. We prove this conjecture for an infinite class of simple groups. Let p be an odd prime. We show that every finite group G with the property Z(G) = 1 and N(G) = N(A _i ) is necessarily isomorphic to A _i , where i ∈ {2p, 2p + 1}.     

A new characterization of symmetric group by NSE

Let G be a group and ω(G) be the set of element orders of G. Let k ∈ ω(G) and m _k (G) be the number of elements of order k in G. Let nse(G) = {m _k (G): k ∈ ω(G)}. Assume r is a prime number and let G be a group such that nse(G) = nse(S _r ), where S _r is the symmetric group of degree r. In this paper we prove that G ? S _r , if r divides the order of G and r ² does not divide it. To get the conclusion we make use of some well-known results on the prime graphs of finite simple groups and their components.     

Realizability of Two-dimensional Linear Groups over Rings of Integers of Algebraic Number Fields

Given the ring of integers O _K of an algebraic number field K, for which natural numbers n there exists a finite group G???GL(n, O _K ) such that O _K G, the O _K -span of G, coincides with M(n, O _K ), the ring of (n?×?n)-matrices over O _K ? The answer is known if n is an odd prime. In this paper we study the case n?=?2; in the cases when the answer is positive for n?=?2, for n?=?2m there is also a finite group G???GL(2m, O _K ) such that O _K G?=?M(2m, O _K ).     

Unicyclic graphs with bicyclic inverses

A graph is nonsingular if its adjacency matrix A(G) is nonsingular. The inverse of a nonsingular graph G is a graph whose adjacency matrix is similar to A(G)^?1 via a particular type of similarity. Let H denote the class of connected bipartite graphs with unique perfect matchings. Tifenbach and Kirkland (2009) characterized the unicyclic graphs in H which possess unicyclic inverses. We present a characterization of unicyclic graphs in H which possess bicyclic inverses.     

A stability result using the matrix norm to bound the permanent

We prove a stability version of a general result that bounds the permanent of a matrix in terms of its operator norm. More specifically, suppose A is an n × n matrix over C (resp. R), and let P denote the set of n × n matrices over C (resp. R) that can be written as a permutation matrix times a unitary diagonal matrix. Then it is known that the permanent of A satisfies |per(A)| ≤ ||A|| ⁿ ₂ with equality iff A/||A||₂ ∈ P (where ||A||₂ is the operator 2-norm of A). We show a stability version of this result asserting that unless A is very close (in a particular sense) to one of these extremal matrices, its permanent is exponentially smaller (as a function of n) than ||A|| ⁿ ₂. In particular, for any fixed α, β > 0, we show that |per(A)| is exponentially smaller than ||A|| ⁿ ₂ unless all but at most αn rows contain entries of modulus at least ||A||₂(1?β).     

Distance domination of generalized de Bruijn and Kautz digraphs

Let G = (V,A) be a digraph and k ≥ 1 an integer. For u, v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each vertex of V D is distance k-dominated by some vertex of D. The distance k-domination number of G, denoted by γ _k (G), is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs G _B (n, d) and generalized Kautz digraphs G _K (n, d) are good candidates for interconnection networks. Denote Δ _k := (∑ _j=0 ^k d ^j )^?1. F. Tian and J. Xu showed that ?nΔ _k ? γ _k (G _B (n, d)) ≤?n/d ^k? and ?nΔ _k ? ≤ γ _k (G _K (n, d)) ≤ ?n/d ^k ?. In this paper, we prove that every generalized de Bruijn digraph G _B (n, d) has the distance k-domination number ?nΔ _k ? or ?nΔ _k ?+1, and the distance k-domination number of every generalized Kautz digraph G _K (n, d) bounded above by ?n/(d ^k?1+d ^k )?. Additionally, we present various sufficient conditions for γ _k (G _B (n, d)) = ?nΔ _k ? and γ _k (G _K (n, d)) = ?nΔ _k ?.     

On dihedrants admitting arc-regular group actions

We consider Cayley graphs Γ over dihedral groups, dihedrants for short, which admit an automorphism group G acting regularly on the arc set of Γ. We prove that, if D _2n ≤G≤Aut(Γ) is a regular dihedral subgroup of G of order 2n such that any of its index 2 cyclic subgroups is core-free in G, then Γ belongs to the family of graphs of the form \((K_{n_{1}}\otimes\cdots\otimes K_{n_{\ell}})[K_{m}^{\mathrm{c}}]\), where 2n=n ₁???n _? m, and the numbers n _i are pairwise coprime. Applications to 1-regular dihedrants and Cayley maps on dihedral groups are also given.     

Nonsingularity,positive definiteness,and positive invertibility under fixed-point data rounding

For a real square matrix A and an integer d ? 0, let A _(d) denote the matrix formed from A by rounding off all its coefficients to d decimal places. The main problem handled in this paper is the following: assuming that A _(d) has some property, under what additional condition(s) can we be sure that the original matrix A possesses the same property? Three properties are investigated: nonsingularity, positive definiteness, and positive invertibility. In all three cases it is shown that there exists a real number α(d), computed solely from A _(d) (not from A), such that the following alternative holdsif d > α(d), then nonsingularity (positive definiteness, positive invertibility) of A _(d) implies the same property for A if d < α(d) and A _(d) is nonsingular (positive definite, positive invertible), then there exists a matrix A′ with A′_(d) = A _(d) which does not have the respective property.For nonsingularity and positive definiteness the formula for α(d) is the same and involves computation of the NP-hard norm ‖ · ‖_∞,1; for positive invertibility α(d) is given by an easily computable formula.     

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.     

Turán-Type Results for Complete <Emphasis Type="Italic">h</Emphasis>-Partite Graphs in Comparability and Incomparability Graphs

We consider an h-partite version of Dilworth’s theorem with multiple partial orders. Let P be a finite set, and let <₁,...,< _r be partial orders on P. Let G(P, <₁,...,< _r ) be the graph whose vertices are the elements of P, and x, y ∈ P are joined by an edge if x< _i y or y< _i x holds for some 1 ≤ i ≤ r. We show that if the edge density of G(P, <₁, ... , < _r ) is strictly larger than 1 ? 1/(2h ? 2) ^r , then P contains h disjoint sets A ₁, ... , A _h such that A ₁ < _j ... < _j A _h holds for some 1 ≤ j ≤ r, and |A ₁| = ... = |A _h | = Ω(|P|). Also, we show that if the complement of G(P, <) has edge density strictly larger than 1 ? 1/(3h ? 3), then P contains h disjoint sets A ₁, ... , A _h such that the elements of A _i are incomparable with the elements of A _j for 1 ≤ i < j ≤ h, and |A ₁| = ... = |A _h | = |P|^1?o(1). Finally, we prove that if the edge density of the complement of G(P, <₁, <₂) is α, then there are disjoint sets A, B ? P such that any element of A is incomparable with any element of B in both <₁ and <₂, and |A| = |B| > n ^1?γ(α), where γ(α) → 0 as α → 1. We provide a few applications of these results in combinatorial geometry, as well.     

On perturbation theory for points of discrete spectrum of dissipative operator functions

We consider the operator function L(α, θ) = A(α) ? θR of two complex arguments, where A(α) is an analytic operator function defined in some neighborhood of a real point α ₀ ∈ ? and ranging in the space of bounded operators in a Hilbert space ?. We assume that A(α) is a dissipative operator for real α in a small neighborhood of the point α ₀ and R is a bounded positive operator; moreover, the point α ₀ is a normal eigenvalue of the operator function L(α, θ ₀) for some θ ₀ ∈ ?, and the number θ ₀ is a normal eigenvalue of the operator function L(α ₀ θ). We obtain analogs and generalizations of well-known results for self-adjoint operator functions A(α) on the decomposition of α- and θ-eigenvalues in neighborhoods of the points α ₀ and θ ₀, respectively, and on the representation of the corresponding eigenfunctions by series.     

Conditional connectivity of bubble sort graphs

A subset F ? V (G) is called an R ^k -vertex-cut of a graph G if G ? F is disconnected and each vertex of G ? F has at least k neighbors in G ? F. The R ^k -vertex-connectivity of G, denoted by κ ^k (G), is the cardinality of a minimum R ^k -vertex-cut of G. Let B _n be the bubble sort graph of dimension n. It is known that κ _k (B _n ) = 2 ^k (n ? k ? 1) for n ≥ 2k and k = 1, 2. In this paper, we prove it for k = 3 and conjecture that it is true for all k ∈ N. We also prove that the connectivity cannot be more than conjectured.