On pseudo walk matrices

Alexander Farrugia

Author(s)

Alexander Farrugia Department of Mathematics, University of Malta Junior College,Msida,Malta

Abstract

A pseudo walk matrix associated with a graph G having adjacency matrix A is a matrix with columns v; Av; A2v; : : : ; Ar 1v (for a specific r) where the Gram matrix of these columns contains particular walk enumerations in G. For any subset S of the Cartesian product of the vertex set V(G) with itself, we consider the total number of walks N0(S); N1(S); N2(S); : : : of length 0; 1; 2; : : : in G that start from vertex i and end at vertex j for all (i; j) 2 S. We present a method that, given such a set S, produces a walk vector v (with possibly complex entries) such that the Gram matrix of the columns of the pseudo walk matrix resulting from this walk vector is the Hankel matrix whose skew diagonals contain the values N0(S); : : : ; N2r 2(S). Various results on such pseudo walk matrices are derived, particularly on closed pseudo walk matrices whose set S contains only the pairs (v; v) for all v 2 V(G). Moreover, a result akin to the classic Harary-Sachs coefficient theorem in chemical graph theory that computes any coefficient of the characteristic polynomial of the companion matrix of a pseudo walk matrix is conveyed.

Publication Details

Page(s) 8-15

DOI DOI not available

Published Journal: Discrete Mathematics Letters, Volume: 1, Issue: 0, Year: 2019

Request the full text from PASTIC

Keywords

walk vector, graph walks, pseudo walk matrix, coefficient theorem, closed pseudo walk matrix

References

. .which can be verified as being be verified by inspection. , : .

Biggs N. .1993 .. , : .

Cardoso D. M.,Zerafa C. .2010 .Main eigenvalues and ( ; )-regular sets. Linear Algebra Appl, 432 : 2399-2408.

Cvetkovic D.,Rowlinson P.,S. K. P. .2009 .Simic´, An Introduction to the Theory of Graph Spectra. , : .

Cvetkovic D.,Rowlinson P.,Z P.,Yoon M. G. .2011 .. Classe Sci. Math. Natur. Sci. Math, 143(36) : 81-88.

Debono M. .2012 .Threshold Graphs as Models of Real-World Networks. Master's thesis, : .

Erdo P. .1963 .˝s, A. Re´nyi, Asymmetric graphs. (Acta Math. Hung.), 14(3-4) : 295-315.

Farrugia A. .2016 .On strongly asymmetric and controllable primitive graphs. Discrete Appl. Math, 211 : 58-67.

Godsil C. .2012 .. , 16(4) : 733-744.

Hagos E. M. .2002 .Some results on graph spectra. Linear Algebra Appl, 356 : 103-111.

Harary F. .1962 .The determinant of the adjacency matrix of a graph. SIAM Rev, 4(3) : 202-210.

Horn R. A.,Johnson C. R. .2013 .. , : .

Powers D. L.,M. M. Sulaiman D. L. .1982 .The walk partition and colorations of a graph. Linear Algebra Appl, 48 : 145-159.

Rowlinson P. .2007 .The main eigenvalues of a graph: a survey. Appl. Anal. Discr. Math. 1, : 445-471.

Sachs H. .1964 .Beziehungen zwischen den in einem graphen enthaltenen Kreisen und seinem charakteristischen polynom. Publ. Math. Debrecen, 11 : 119-134.

Shrikhande S. S. .1965 .. J. Indian Statist. Assoc, 3 : 30-37.