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.     

Abelian group matrices over the p-adic and rational integers

Let G be a finite abelian group of order n. Let Z and Q denote the rational integers and rationals, respectively. A group matrix for G over Z (or Q) is an n-square matrix of the form Σ_{g ∈ G}a_gP(g), where a_g ∈ Z (or Q) and P is the regular representation of G so that P(g) is an n-square permutation matrix and P(gh) = P(g)P(h) for all g, h ∈ G. It is known that if M is an arbitrary positive definite unimodular matrix over Z then there exists a matrix A over Q such that M = A^τA, where τ denotes transposition. This paper proves that the exact analogue of this theorem holds if one demands that M and A be group matrices for G over Z and Q, respectively. Furthermore, if M is a group matrix for G over the p-adic integers then necessary and sufficient conditions are given for the existence of a group matrix A for G over the p-adic numbers such that M = A^τA.     

Abelian Group Gradings on Full Matrix Rings

For positive integers ? and n, several authors studied ?_?-gradings of the full matrix ring M _n (k) over a field k. In this article, we show that every (G × H)-grading of M _n (k) can be constructed by a pair of compatible G-grading and H-grading of M _n (k), where G and H are any finite groups. When G and H are finite cyclic groups, we characterize all (G × H)-gradings which are isomorphic to a good grading. Moreover, the results can be generalized for any finite abelian group grading of M _n (k).     

Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.     

A method in graph theory

A unified approach to a variety of graph-theoretic problems is introduced. The k-closure C_k(G) of a simple graph G of order n is the graph obtained from G by recursively joining pairs of nonadjacent vertices with degree-sum at least k. It is shown that, for many properties P, one can find a suitable value of k (depending on P and n) such that if C_k(G) has P, then so does G. For instance, if P is the hamiltonian property, one may take k = n. Thus if C_n(G) is hamiltonian, then so is G; in particular, if n ? 3 and C_n(G) is complete, then G is hamiltonian. This condition for a graph to be hamiltonian is shown to imply the well-known conditions of Chvátal and Las Vergnas. The same method, applied to other properties, yields many new theorems of a similar nature.     

Matricial logarithmic derivatives

If θ is a norm on Cⁿ, then the mapping $\text{A→}\text{lim}{}_{\mathrm{h\downarrow 0}}\text{6I+hA6}{}_{\mathrm{\theta }}\text{?1}\text{/h}$ from M_n(C) (=C^{n × n}) into R is called the logarithmic derivative induced by the vector norm θ. In this paper we generalize this concept to a mapping γ from M_n(C) into M_k(R), where k ? n. Denoting by α(B) the spectral abscissa of a square matrix B (the largest of the real parts of the eigenvalues), we show, in particular, that α(A) ?α(γ(A)). As a byproduct we obtain simple sufficient conditions for the stability of a matrix.     

On the spanning connectivity of graphs

A k-containerC(u,v) of G between u and v is a set of k internally disjoint paths between u and v. A k-container C(u,v) of G is a k^*-container if it contains all vertices of G. A graph G is k^*-connected if there exists a k^*-container between any two distinct vertices. The spanning connectivity of G, κ^*(G), is defined to be the largest integer k such that G is w^*-connected for all 1?w?k if G is a 1^*-connected graph. In this paper, we prove that κ^*(G)?2δ(G)-n(G)+2 if (n(G)/2)+1?δ(G)?n(G)-2. Furthermore, we prove that κ^*(G-T)?2δ(G)-n(G)+2-|T| if T is a vertex subset with |T|?2δ(G)-n(G)-1.     

The primitive matrices of sandwich semigroups of generalized circulant Boolean matrices

Let Gn（C） be the sandwich semigroup of generalized circulant Boolean matrices with the sandwich matrix C and Gc（Jr~） the set of all primitive matrices in Gn（C）. In this paper, some necessary and sufficient conditions for A in the semigroup Gn（C） to be primitive are given. We also show that Gc（Jn） is a subsemigroup of Gn（C）.     

Goldschmidt’s 2-signalizer functor theorem

A solvableA-signalizer functor? assigns to any non-identity elementx of the abelian 2-subgroupA of the finite groupG anA-invariant solvable 2′-subgroupθ(C _G(x)) ofC _G(x) such thatθ(C _G(x)) ∩C _G(y) ??(C _G(y)) for allx, y ∈ A ^#.θ is called complete ifG has a solvableA-invariant 2′-subgroupK=θ(G) such thatC _k(x)=θ(C _G(x)) for everyx ∈ A#. This note contains an alternate proof of the completeness theorem below.     

The primitive Boolean matrices with the second largest scrambling index by Boolean rank

The scrambling index of an n × n primitive Boolean matrix A is the smallest positive integer k such that A ^k (A ^T) ^k = J, where A ^T denotes the transpose of A and J denotes the n×n all ones matrix. For an m×n Boolean matrix M, its Boolean rank b(M) is the smallest positive integer b such that M = AB for some m × b Boolean matrix A and b×n Boolean matrix B. In 2009, M. Akelbek, S. Fital, and J. Shen gave an upper bound on the scrambling index of an n×n primitive matrix M in terms of its Boolean rank b(M), and they also characterized all primitive matrices that achieve the upper bound. In this paper, we characterize primitive Boolean matrices that achieve the second largest scrambling index in terms of their Boolean rank.     

A characterization of transform absolute norms

Let 6x6 be a norm on Cⁿ. For A?M_n(C) denote by 6A6 the induced norm of A, by ?(A) the spectral radius of A. It is proved here that if inf_p6PAP^?16 = ?(A), then 6x6 is a transform absolute norm.     

k-fold coloring of planar graphs

A k-fold n-coloring of G is a mapping φ: V (G) → Zk(n) where Zk(n) is the collection of all ksubsets of {1,2,...,n} such that φ(u) ∩φ(v) = φ if uv ∈ E(G).If G has a k-fold n-coloring,i.e.,G is k-fold n-colorable.Let the smallest integer n such that G is k-fold n-colorable be the k-th chromatic number,denoted by χk(G).In this paper,we show that any outerplanar graph is k-fold 2k-colorable or k-fold χk(C*)-colorable,where C* is a shortest odd cycle of G.Moreover,we investigate that every planar graph with odd girth at least 10k-9(k 3) can be k-fold (2k + 1)-colorable.     

deBruijn-like sequences and the irregular chromatic number of paths and cycles

A deBruijn sequence of orderk, or a k-deBruijn sequence, over an alphabet A is a sequence of length |A|^k in which the last element is considered adjacent to the first and every possible k-tuple from A appears exactly once as a string of k-consecutive elements in the sequence. We will say that a cyclic sequence is deBruijn-like if for some k, each of the consecutive k-element substrings is distinct.A vertex coloring χ:V(G)→[k] of a graph G is said to be proper if no pair of adjacent vertices in G receive the same color. Let C(v;χ) denote the multiset of colors assigned by a coloring χ to the neighbors of vertex v. A proper coloring χ of G is irregular if χ(u)=χ(v) implies that C(u;χ)≠C(v;χ). The minimum number of colors needed to irregularly color G is called the irregular chromatic number of G. The notion of the irregular chromatic number pairs nicely with other parameters aimed at distinguishing the vertices of a graph. In this paper, we demonstrate a connection between the irregular chromatic number of cycles and the existence of certain deBruijn-like sequences. We then determine the exact irregular chromatic number of C_n and P_n for n≥3, thus verifying two conjectures given by Okamoto, Radcliffe and Zhang.     

On a class of degenerate extremal graph problems

Given a class ? of (so called “forbidden”) graphs, ex (n, ?) denotes the maximum number of edges a graphG ⁿ of ordern can have without containing subgraphs from ?. If ? contains bipartite graphs, then ex (n, ?)=O(n ^2?c ) for somec>0, and the above problem is calleddegenerate. One important degenerate extremal problem is the case whenC _2k , a cycle of 2k vertices, is forbidden. According to a theorem of P. Erd?s, generalized by A. J. Bondy and M. Simonovits [3₂, ex (n, {C _2k })=O(n ^1+1/k ). In this paper we shall generalize this result and investigate some related questions.     

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.     

Matrix Near-rings over Centralizer Near-rings

For a finite group G and a subgroup A of Aut(G), let M_A(G) denote the centralizer near-ring determined by A and G. The group G is an M_A(G)-module. Using the action of M_A(G) on G, one has the n × n generalized matrix near-ring Mat_n(M_A(G);G). The correspondence between the ideals of M_A(G) and those of Mat_n(M_A(G);G) is investigated. It is shown that if every ideal of M_A(G) is an annihilator ideal, then there is a bijection between the ideals of M_A(G) and those of Mat_n(M_A(G);G).1991 Mathematics Subject Classification: 16Y30     

Geometric conditions for the existence of positive eigenvalues of matrices

Finite-dimensional theorems of Perron-Frobenius type are proved. For A∈$\text{C}$ⁿⁿ and a nonnegative integer k, we let w_k (A) be the cone generated by A^k, A^k+1,…in $\text{C}$ⁿⁿ. We show that A satisfies the Perron-Schaefer condition if and only if the closure $\text{W}$_k(A) of w_k(A) is a pointed cone. This theorem is closely related to several known results. If k?v₀(A), the index of the eigenvalue 0 in spec A, we prove that A has a positive eigenvalue if and only if w_k(A) is a pointed nonzero cone or, equivalently $\text{W}$_k(A) is not a real subspace of $\text{C}$ⁿⁿ. Our proofs are elementary and based on a method of Birkhoff's. We discuss the relation of this method to Pringsheim's theorem.     

List multicoloring problems involving the k‐fold Hall numbers

We show that the four‐cycle has a k‐fold list coloring if the lists of colors available at the vertices satisfy the necessary Hall's condition, and if each list has length at least ?5k/3?; furthermore, the same is not true with shorter list lengths. In terms of h^(k)(G), the k ‐fold Hall number of a graph G, this result is stated as h^(k)(C₄)=2k??k/3?. For longer cycles it is known that h^(k)(C_n)=2k, for n odd, and 2k??k/(n?1)?≤h^(k)(C_n)≤2k, for n even. Here we show the lower bound for n even, and conjecture that this is the right value (just as for C₄). We prove that if G is the diamond (a four‐cycle with a diagonal), then h^(k)(G)=2k. Combining these results with those published earlier we obtain a characterization of graphs G with h^(k)(G)=k. As a tool in the proofs we obtain and apply an elementary generalization of the classical Hall–Rado–Halmos–Vaughan theorem on pairwise disjoint subset representatives with prescribed cardinalities. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 16–34, 2010.     

A note on k-potence preserving maps

Let M_n be the algebra of all n×n complex matrices and Γ_n the set of all k-potent matrices in M_n. Suppose ?:M_n→M_n is a map satisfying A-λB∈Γ_n implies ?(A)-λ?(B)∈Γ_n, where A, B∈M_n, λ∈C. Then either ? is of the form ?(A)=cTAT^-1, A∈M_n, or ? is of the form ?(A)=cTA^tT^-1, A∈M_n, where T∈M_n is an invertible matrix, c∈C satisfies c^k=c.     

On the equivalence of the Euler-Pommier operators in spaces of analytic functions

In the space A (θ) of all one-valued functions f(z) analytic in an arbitrary region G ? ? (0 ∈ G) with the topology of compact convergence, we establish necessary and sufficient conditions for the equivalence of the operators L ₁=α _n z ⁿ Δ ⁿ + ... + α₁ zΔ+α₀ E and L ₂= z ⁿ a _n (z)Δ ⁿ + ... + za ₁(z)Δ+a ₀(z)E, where δ: (Δ?)(z)=(f(z)-?(0))/z is the Pommier operator in A(G), n ∈ ?, α _n ∈ ?, a _k (z) ∈ A(G), 0≤k≤n, and the following condition is satisfied: Σ _j=s ^n?1 α _j+1 ∈ 0, s=0,1,...,n?1. We also prove that the operators z ^s+1Δ+β(z)E, β(z) ∈ A _R , s ∈ ?, and z ^s+1 are equivalent in the spaces A _R, 0?R?-∞, if and only if β(z) = 0.