三对角逆M矩阵的判定

1、引言 三对角逆M矩阵是指同时为三对角矩阵和逆M矩阵的一类特殊矩阵．文用图论方法探讨三对角逆M矩阵结构,给出了三对角矩阵为逆M矩阵的充分必要条件．此条件提供了判定三对角矩阵是逆M矩阵的方法,但较复杂．文讨论了这类矩阵在Hadamard积下的封闭性．由于三对角逆M矩阵在理论和应用上都有一定价值,所以,寻求一种简单而实用的判定方法是必要的．本文通过对这类矩阵结构特点的研究找到了这样一种方法．同时,由此证明了这类矩阵在Hadamard积下的封闭性．     

Oppenheim不等式的一种类似

证明了实对称正定矩阵或实对称半正定矩阵与 M-矩阵的 Hadamard乘积满足实对称正定矩阵 Hadamard乘积的 Oppenheim不等式 .     

非奇异M-矩阵的逆矩阵和M-矩阵的Hadamard积的最小特征值下界估计

给出非奇异M-矩阵的逆矩阵和M-矩阵的Hadamard积的最小特征值下界新的估计式,这些估计式都只依赖于矩阵的元素.数值例子表明,新估计式在一定条件下改进了Fiedler和Markham的猜想,也改进了其它已有的结果.     

M-矩阵Hadamard积的最小特征值下界的新估计式

设B和A是非奇异M-矩阵,给出B和A-1的Hadamard积的最小特征值下界τ（B°A-1）的一个新估计式,理论证明和算例表明,本文所得新估计式改进了现有的一些结果．     

New inequalities for the minimum eigenvalue of M-matrices

Some new inequalities for the minimum eigenvalue of M-matrices are established. These inequalities improve the results in [G. Tian and T. Huang, Inequalities for the minimum eigenvalue of M-matrices, Electr. J. Linear Algebra 20 (2010), pp. 291–302].     

Proof of a conjecture on connectivity of Kronecker product of graphs

For a graph G, κ(G) denotes its connectivity. The Kronecker product G₁×G₂ of graphs G₁ and G₂ is the graph with the vertex set V(G₁)×V(G₂), two vertices (u₁,v₁) and (u₂,v₂) being adjacent in G₁×G₂ if and only if u₁u₂∈E(G₁) and v₁v₂∈E(G₂). Guji and Vumar [R. Guji, E. Vumar, A note on the connectivity of Kronecker products of graphs, Appl. Math. Lett. 22 (2009) 1360–1363] conjectured that for any nontrivial graph G, κ(G×K_n)=min{nκ(G),(n−1)δ(G)} when n≥3. In this note, we confirm this conjecture to be true.     

A Note on Generic Fiedler Matrices

In this paper, we first show that a generic m×n Fiedler matrix may have 2m-n-1 kinds of factorizations which are very complicated when m is much larger than n. In this work, two special cases are examined, one is an m×n Fiedler matrix being factored as a product of (m - n) Fiedler matrices, the other is an m×(m - 2) Fiedler matrix's factorization. Then we discuss the relation among the numbers of parameters of three generic m×n, n×p and m×p Fiedler matrices, and obtain some useful results.     

三对角逆M-矩阵

In this paper we study a class of inverse M-matrices:tridiagonal inverse M-matrices,Graph theory is used to discuss the structure and properties of tridiagonal inverse M-matrices,A sufficient and necessary condtion for a nonnegative tridiagonal matrix to be an inverse M-matrix is given.Finally,it is proved that the set of the inverses of M-matrices with unipathic is closed under Hadamard product.     

关于树的代数连通度的Fiedler不等式的新证明

设T为含n个顶点的树，L(T)为其Laplace矩阵，L(T)的次小特征值α(T)称为T的代数连通度，Fiedlcr给出如下关于α(T)的界的经典结论α(Pn)≤α(T)≤α(Sn)，其中Pn，Sn分别为含有n个顶点的路和星．Merris和Mass独立地证明了：α(T)=α(Sn)当且仅当T=Sn．通过重新组合由Fiedler向量所赋予的顶点的值，本给出上述不等式的新证明，并证明了：α(T)=α(Pn)当且仅当T=Pn。     

Proof of a conjecture of Metsch

In this paper we prove a conjecture of Metsch about the maximum number of lines intersecting a pointset in PG(2,q), presented at the conference “Combinatorics 2002”. As a consequence, we give a short proof of the famous Jamison, Brouwer and Schrijver bound on the size of the smallest affine blocking set in AG(2,q).     

一个特殊乘积的逆的矩阵不等式的加强

将两个正定矩阵的Khatri-Rao乘积的矩阵不等式(A*B)^-1≤A^-1*B^-1推广为(A*B)^-1≤（A^-1(α）^-1*B(α））^-1 (A(α′）*B^-1(α′）^-1)^-1≤（A^-1（α）*B（α）^-1) (A(α′）^-1*B^-1(α′））≤A^-1*B^-1,其中A(α）是A的顺序主子矩阵，而A（α′）是A（α）的余子矩阵，同时还给出了其等式成立的充分必要条件。     

Proof of a conjecture of Alan Hartman

A tree T is said to be bad, if it is the vertex‐disjoint union of two stars plus an edge joining the center of the first star to an end‐vertex of the second star. A tree T is good, if it is not bad. In this article, we prove a conjecture of Alan Hartman that, for any spanning tree T of K_2m, where m ≥ 4, there exists a (2m − 1)‐edge‐coloring of K_2m such that all the edges of T receive distinct colors if and only if T is good. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 7–17, 1999     

Proof of a conjecture on game domination

Let G(V, E) be a simple, undirected graph where V is the set of vertices and E is the set of edges. A b‐dimensional cube is a Cartesian product I₁×I₂×···×I_b, where each I_i is a closed interval of unit length on the real line. The cubicity of G, denoted by cub(G), is the minimum positive integer b such that the vertices in G can be mapped to axis parallel b‐dimensional cubes in such a way that two vertices are adjacent in G if and only if their assigned cubes intersect. An interval graph is a graph that can be represented as the intersection of intervals on the real line—i.e. the vertices of an interval graph can be mapped to intervals on the real line such that two vertices are adjacent if and only if their corresponding intervals overlap. Suppose S(m) denotes a star graph on m+1 nodes. We define claw number ψ(G) of the graph to be the largest positive integer m such that S(m) is an induced subgraph of G. It can be easily shown that the cubicity of any graph is at least ?log₂ψ(G)?. In this article, we show that for an interval graph G ?log₂ψ(G)??cub(G)??log₂ψ(G)?+2. It is not clear whether the upper bound of ?log₂ψ(G)?+2 is tight: till now we are unable to find any interval graph with cub(G)>?log₂ψ(G)?. We also show that for an interval graph G, cub(G)??log₂α?, where α is the independence number of G. Therefore, in the special case of ψ(G)=α, cub(G) is exactly ?log₂α₂?. The concept of cubicity can be generalized by considering boxes instead of cubes. A b‐dimensional box is a Cartesian product I₁×I₂×···×I_b, where each I_i is a closed interval on the real line. The boxicity of a graph, denoted box(G), is the minimum k such that G is the intersection graph of k‐dimensional boxes. It is clear that box(G)?cub(G). From the above result, it follows that for any graph G, cub(G)?box(G)?log₂α?. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 323–333, 2010     

Proof of a conjecture on monomial graphs

Let e be a positive integer, p be an odd prime, $q=p^e$, and ${\mathbb{F}}_q$ be the finite field of q elements. Let $f,g\in {\mathbb{F}}_q[X,Y]$. The graph $G_q(f,g)$ is a bipartite graph with vertex partitions $P={\mathbb{F}}_q^3$ and $L={\mathbb{F}}_q^3$, and edges defined as follows: a vertex $(p)=(p_1,p_2,p_3)\in P$ is adjacent to a vertex $[l]=[l_1,l_2,l_3]\in L$ if and only if $p_2+l_2=f(p_1,l_1)$ and $p_3+l_3=g(p_1,l_1)$. If $f=XY$ and $g=X{Y}^2$, the graph $G_q(XY,X{Y}^2)$ contains no cycles of length less than eight and is edge-transitive. Motivated by certain questions in extremal graph theory and finite geometry, people search for examples of graphs $G_q(f,g)$ containing no cycles of length less than eight and not isomorphic to the graph $G_q(XY,X{Y}^2)$, even without requiring them to be edge-transitive. So far, no such graphs $G_q(f,g)$ have been found. It was conjectured that if both f and g are monomials, then no such graphs exist. In this paper we prove the conjecture.