Packing independent sets and transversals
Partial sum of eigenvalues of random graphs
Let be a graph on vertices and let be the eigenvalues of its adjacency matrix. For random graphs we investigate the sum of eigenvalues , for , and show that a typical graph has , where is the number of edges of . We also show bounds for the sum of eigenvalues within a given range in terms of the number of edges. The approach for the proofs was first used in Rocha (2020) to bound the partial sum of eigenvalues of the Laplacian matrix.
Pentadiagonal Companion Matrices
The class of sparse companion matrices was recently characterized in terms of unit Hessenberg matrices. We determine which sparse companion matrices have the lowest bandwidth, that is, we characterize which sparse companion matrices are permutationally similar to a pentadiagonal matrix and describe how to find the permutation involved. In the process, we determine which of the Fiedler companion matrices are permutationally similar to a pentadiagonal matrix. We also describe how to find a Fiedler...
Perfect matching preservers.
Perfect matchings in -regular graphs.
Periodic graphs.
Permanents of Hessenberg (0,1)-matrices.
Pfaffian orientation and enumeration of perfect matchings for some Cartesian products of graphs.
Porous media equation on locally finite graphs
In this paper, we consider two typical problems on a locally finite connected graph. The first one is to study the Bochner formula for the Laplacian operator on a locally finite connected graph. The other one is to obtain global nontrivial nonnegative solution to porous-media equation via the use of Aronson-Benilan argument. We use the curvature dimension condition to give a characterization two point graph. We also give a porous-media equation criterion about stochastic completeness of the graph....
Positive Q-matrices of graphs
The Q-matrix of a connected graph = (V,E) is , where ∂(x,y) is the graph distance. Let q() be the range of q ∈ (-1,1) for which the Q-matrix is strictly positive. We obtain a sufficient condition for the equality q(̃) = q() where ̃ is an extension of a finite graph by joining a square. Some concrete examples are discussed.
Power indices of trace zero symmetric Boolean matrices
The power index of a square Boolean matrix A is the least integer d such that Ad is a linear combination of previous nonnegative powers of A. We determine the maximum power indices for the class of n×n primitive symmetric Boolean matrices of trace zero, the class of n×n irreducible nonprimitive symmetric Boolean matrices, and the class of n×n reducible symmetric Boolean matrices of trace zero, and characterize the extreme matrices respectively.
Principal eigenvectors of irregular graphs.
Properties determined by the Ihara zeta function of a graph.