✦ LIBER ✦

Walks on Directed Graphs and Matrix Polynomials

✍ Scribed by Miguel A. Méndez

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 166 KB
Volume: 91
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.2000.3105

No coin nor oath required. For personal study only.

✦ Synopsis

We give a matrix generalization of the family of exponential polynomials in one variable , k (x). Our generalization consists of a matrix of polynomials 8 k (X)= (8 (k) i, j (X)) n i, j=1 depending on a matrix of variables X=(x i, j ) n i, j=1 . We prove some identities of the matrix exponential polynomials which generalize classical identities of the ordinary exponential polynomials. We also introduce matrix generalizations of the decreasing factorial (x x+k&1), and the Laguerre polynomials. These polynomials have interesting combinatorial interpretations in terms of different kinds of walks on directed graphs.

📜 SIMILAR VOLUMES

Matrix-valued Szegő polynomials and quan

Matrix-valued Szegő polynomials and quantum random walks

✍ M. J. Cantero; L. Moral; F. Alberto Grünbaum; L. Velázquez 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 332 KB 👁 1 views

## Abstract We consider quantum random walks (QRW) on the integers, a subject that has been considered in the last few years in the framework of quantum computation. We show how the theory of CMV matrices gives a natural tool to study these processes and to give results that are analogous to those

Random walks on random simple graphs

✍ Martin Hildebrand 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 676 KB

This paper looks at random regular simple graphs and considers nearest neighbor random walks on such graphs. This paper considers walks where the degree d of each vertex is around (logn)", where a is a constant which is at least 2 and where n is the number of vertices. By extending techniques of Dou

On the distance matrix of a directed gra

On the distance matrix of a directed graph

✍ R. L. Graham; A. J. Hoffman; H. Hosoya 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 2 views

## Abstract In this note, we show how the determinant of the distance matrix __D(G__) of a weighted, directed graph __G__ can be explicitly expressed in terms of the corresponding determinants for the (strong) blocks __G~i~__ of __G__. In particular, when cof __D(G__), the sum of the cofactors of _

A Note on Graph Colorings and Graph Poly

A Note on Graph Colorings and Graph Polynomials

✍ Noga Alon; Michael Tarsi 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 230 KB

## dedicated to professor w. t. tutte on the occasion of his eightieth birtday It is known that the chromatic number of a graph G=(V, E) with V= [1, 2, ..., n] exceeds k iff the graph polynomial f G => ij # E, i<j (x i &x j ) lies in certain ideals. We describe a short proof of this result, using

On antimagic directed graphs

✍ Dan Hefetz; Torsten Mütze; Justus Schwartz 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB

## Abstract An antimagic labeling of an undirected graph __G__ with __n__ vertices and __m__ edges is a bijection from the set of edges of __G__ to the integers {1, …, __m__} such that all __n__ vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with th

On persistent directed graphs

✍ Jorgen Bang-Jensen; Tibor Jordán 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 209 KB