A relationship between stochastic matrices and eigenvalues of products

Let {B₁,…,B_n} be a set of n rank one n×n row stochastic matrices. The next two statements are equivalent: (1) If A is an n×n nonnegative matrix, then 1 is an eigenvalue ofB_kA for each k=1,…,n if and only if A is row stochastic. (2) The n×n row stochastic matrix S whose kth row is a row of B_k for k=1,…,n is nonsingular. For any set {B₁, B₂,…, B_p} of fewer than n row stochastic matrices of order n×n and of any rank, there exists a nonnegative n×n matrix A which is not row stochastic such that 1 is eigenvalue of every B_kA, k=1,…,p.     

Connected graphs with maximal Q-index: The one-dominating-vertex case

By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then H_n,k, the graph obtained from the star K_1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges.     

Capacity and uniform algebras

Let A be a uniform algebra on a compact space X, let M be the maximal ideal space of A, and consider an element ? of A. Choose a component W of $\text{C}$??(X). In 1963 Bishop showed that {$\text{y}\text{in}\text{M ¦ ?(y) ? W}$} can be made into a one-dimensional complex analytic space provided there is a subset G of W having positive area such that for each λ in $\text{G {y}\text{in}\text{M ¦ ?(y) = λ}}$ is finite. We show that the hypothesis of “positive area” may be replaced by “positive exterior capacity” and that no weaker condition will suffice.     

Exotic n-universal graphs

An n-universal graph is a graph that contains as an induced subgraph a copy of every graph on n vertices. It is shown that for each positive integer n > 1 there exists an n-universal graph G on 4ⁿ - 1 vertices such that G is a (v, k, λ)-graph, and both G and its complement G¯ are 1-transitive in the sense of W. T. Tutte and are of diameter 2. The automorphism group of G is a transitive rank 3 permutation group, i.e., it acts transitively on (1) the vertices of G, (2) the ordered pairs uv of adjacent vertices of G, and (3) the ordered pairs xy of nonadjacent vertices of G.     

Lower bounds for the clique and the chromatic numbers of a graph

G is any simple graph with m edges and n vertices where these vertices have vertex degrees d(1)≥d(2)≥?≥d(n), respectively. General algorithms for the exact calculation of χ(G), the chromatic number of G, are almost always of ‘branch and bound’ type; this type of algorithm requires an easily constructed lower bound for χ(G). In this paper it is shown that, for a number of such bounds (many of which are described here for the first time), the bound does not exceed cl(G) where cl(G) is the clique number of G.In 1972 Myers and Liu showed that cl(G)≥n?(n?2m?n). Here we show that cl(G)≥ n?[n?(2m?n)(1+c²_v)^{$\text{1}\text{2}$}], where c_v is the vertex degree coefficient of variation in G, that cl(G)≥ Bondy's constructive lower bound for χ(G), and that cl(G)≥n?(n?W(G)), where W(G) is the largest positive integer such that W(G)≤d(W(G)+1) [W(G)+1 is the Welsh and Powell upper bound for χ(G)]. It is also shown that cl(G)+$\text{1}\text{3}$>n?(n?L(G))≥n?(n?λ₁) and that χ(G)≥ n?(n?λ₁); λ₁ is the largest eigenvalue of A, the adjacency matrix of G, and L(G) is a newly defined single-valued function of G similar to W(G) in its construction from the vertex degree sequence of G [L(G)≥W(G)].Finally, a ‘greedy’ lower bound for cl(G) is constructed from A and it is shown that this lower bound is never less than Bondy's bound; thereafter, for 150 random graphs with varying numbers of vertices and edge densities, the values of lower bounds given in this paper are listed, thereby illustrating that this last greedily obtained lower bound is almost always better than each of the other bounds.     

The evolution of the min-min random graph process

We study the following min-min random graph process G=(G₀,G₁,…): the initial state G₀ is an empty graph on n vertices (n even). Further, G_M+1 is obtained from G_M by choosing a pair {v,w} of distinct vertices of minimum degree uniformly at random among all such pairs in G_M and adding the edge {v,w}. The process may produce multiple edges. We show that G_M is asymptotically almost surely disconnected if M≤n, and that for M=(1+t)n, constant, the probability that G_M is connected increases from 0 to 1. Furthermore, we investigate the number X of vertices outside the giant component of G_M for M=(1+t)n. For constant we derive the precise limiting distribution of X. In addition, for n⁻¹ln⁴n≤t=o(1) we show that tX converges to a gamma distribution.     

Sufficient Condition to Resolve Costa's First Conjecture

In this work, we give a sufficient condition to resolve Costa's first conjecture for each positive integer n and d with n ≥ 4. Precisely, we show that if there exists a local ring (A, M) such that λ _A (M) = n, and if there exists an (n + 2)-presented A-submodule of M ^m , where m is a positive integer (for instance, if M contains a regular element), then we may construct an example of (n + 4, d)-ring which is neither an (n + 3, d)-ring nor an (n + 4, d ? 1)-ring. Finally, we construct a local ring (B, M) such that λ _B (M) = 0 (resp., λ _B (M) = 1) and so we exhibit for each positive integer d, an example of a (4, d)-ring (resp., (5, d)-ring) which is neither a (4, d ? 1)-ring (resp., neither a (5, d ? 1)-ring) nor a (2, d′)-ring (resp., nor a (3, d′)-ring) for each positive integer d′.     

On q-trees

We show that a graph G with n vertices is a q-tree if and only if its chromatic polynomial is P(G, λ) = λ(λ – 1) ? (λ – q + 1) (λ – q)^n-q where n ≥q.     

Power inequalities and spectral dominance of generalized matrix norms

A generalized matrix norm G dominates the spectral radius for all A?M_n(C) (i) if for some positive integer k the rule G(A^k) ? G(A)^k holds for all A?M_n(C) and (ii) if and only if for each A?M_n(C) there exists a constant γ_A such that G(A^k) ? γ_AG(A)^kfor all positive integers k. Other results and examples are also given concerning spectrally dominant generalized matrix norms.     

The minimum genus of a two-point universal graph

A graph G is two-point universal if, given any two vertices A and B, there is a vertex jointed to both, a vertex joined to neither, a vertex joined to A but not B, and a vertex joined to B but not A. Erdös asked whether there is an infinite family of such graphs of some genus γ. In this note, we show that the number of vertices of a two-point universal graph of genus γ satisfies n ≤ 216(2γ + 1)² so that there are most finitely many of each genus.     

About noncommuting graphs

The noncommuting graph ?(G) of a nonabelian finite group G is defined as follows: The vertices of ?(G) are represented by the noncentral elements of G, and two distinct vertices x and y are joined by an edge if xy ≠ yx. In [1], the following was conjectured: Let G and H be two nonabelian finite groups such that ?(G) ? ?(H); then ¦G¦ = ¦H¦. Here we give some counterexamples to this conjecture.     

Small diameter interchange graphs of classes of matrices of zeros and ones

Let $\text{A}$(R, S) denote the class of all m×n matrices of 0's and 1's having row sum vector R and column sum vector S. The interchange graph G(R, S) is the graph where the vertices are the matrices in $\text{A}$(R, S) and where two matrices are joined by an edge provided they differ by an interchange. We characterize those $\text{A}$(R, S) for which the graph G(R, S) has diameter at most 2 and those $\text{A}$(R, S) for which G(R, S) is bipartite.     

On the rank spread of graphs

For a simple graph G?=?(𝒱, ?) with vertex-set 𝒱?=?{1,?…?,?n}, let 𝒮(G) be the set of all real symmetric n-by-n matrices whose graph is G. We present terminology linking established as well as new results related to the minimum rank problem, with spectral properties in graph theory. The minimum rank mr(G) of G is the smallest possible rank over all matrices in 𝒮(G). The rank spread r _v (G) of G at a vertex v, defined as mr(G)???mr(G???v), can take values ??∈?{0,?1,?2}. In general, distinct vertices in a graph may assume any of the three values. For ??=?0 or 1, there exist graphs with uniform r _v (G) (equal to the same integer at each vertex v). We show that only for ??=?0, will a single matrix A in 𝒮(G) determine when a graph has uniform rank spread. Moreover, a graph G, with vertices of rank spread zero or one only, is a λ-core graph for a λ-optimal matrix A in 𝒮(G). We also develop sufficient conditions for a vertex of rank spread zero or two and a necessary condition for a vertex of rank spread two.     

A trace inequality for M-matrices and the symmetrizability of a real matrix by a positive diagonal matrix

The question of whether a real matrix is symmetrizable via multiplication by a diagonal matrix with positive diagonal entries is reduced to the corresponding question for M-matrices and related to Hadamard products. In the process, for a nonsingular M-matrix A, it is shown that tr(A^-1A^T) ? n, with equality if and only if A is symmetric, and that the minimum eigenvalue of A^-1 ° A is ? 1 with equality in the irreducible case if and only if A is positive diagonally symmetrizable.     

An extremal property of the permanent and the determinant

Given an n × n matrix A, define the n! × n! matrix Ã, with rows and columns indexed by the permutation group S_n, with (σ, τ) entry Πⁿ_i=1a_{τ(i), σ(i)}. It is shown that if A is positive semidefinite, then det A is the smallest eigenvalue of Ã; it is conjectured that per A is the largest eigenvalue of Ã, and the conjecture proved for n⩽3. Several known and some unknown inequalities are derived as consequences.     

On the Perron-Frobenius eigenvector for nonnegative integral matrices whose largest eigenvalue is integral

We first derive the bound |det(λI − A)|⩽λ^k − λ^k₀ (λ₀⩽λ), where A is a k × k nonnegative real matrix and λ₀ is the spectral radius of A. If A is irreducible and integral, and its largest nonnegative eigenvalue is an integer n, then we use this inequality to derive the upper bound n^k−1 on the components of the smallest integer eigenvector corresponding to n. Finer information on the components is also derived.     

Asymptotical Formulas For Solutions Of Linear Differential Systems Of The First Order

In this paper a system of differential equations y′ ? A(·,λ)y = 0 is considered on the finite interval [a,b] where λ ∈ C, A(·, λ):= λ A₁+ A ₀ +λ _?1A_?1(·,λ) and A ₁,A ₀, A _{? 1} are n × n matrix-functions. The main assumptions: A ₁ is absolutely continuous on the interval [a, b], A ₀ and A _{- 1}(·,λ) are summable on the same interval when ¦λ¦ is sufficiently large; the roots φ₁(x),…,φ_n (x) of the characteristic equation det (φ E — A ₁) = 0 are different for all x ∈ [a,b] and do not vanish; there exists some unlimited set Ω ? C on which the inequalities Re(λφ₁(x)) ≤ … ≤ Re (λφ_n(x)) are fulfilled for all x ∈ [a,b] and for some numeration of the functions φ_j(x). The asymptotic formula of the exponential type for a fundamental matrix of solutions of the system is obtained for sufficiently large ¦λ¦. The remainder term of this formula has a new type dependence on properties of the coefficients A ₁ (x), A _o (x) and A _{- 1} (x).     

Maximum nullity of outerplanar graphs and the path cover number

Let G=(V,E) be a graph with V={1,2,…,n}. Define S(G) as the set of all n×n real-valued symmetric matrices A=[a_ij] with a_ij≠0,i≠j if and only if ij∈E. By M(G) we denote the largest possible nullity of any matrix A∈S(G). The path cover number of a graph G, denoted P(G), is the minimum number of vertex disjoint paths occurring as induced subgraphs of G which cover all the vertices of G.There has been some success with relating the path cover number of a graph to its maximum nullity. Johnson and Duarte [5], have shown that for a tree T,M(T)=P(T). Barioli et al. [2], show that for a unicyclic graph G,M(G)=P(G) or M(G)=P(G)-1. Notice that both families of graphs are outerplanar. We show that for any outerplanar graph G,M(G)?P(G). Further we show that for any partial 2-path G,M(G)=P(G).