𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Enumeration of acyclic walks in a graph

✍ Scribed by Darko Babić; Ante Graovac

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
436 KB
Volume
45
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Computer enumeration of walks on directe
Computer enumeration of walks on directed graphs
✍ K. Balasubramanian 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 526 KB

A vectorized computer code is developed for the enumeration of walks through the matrix power method for directed graphs. Application of this code to several graphs is considered. It is shown that the coefficients in the generating functions for signed graphs are much smaller in magnitude. It is sho

The number of walks in a graph
The number of walks in a graph
✍ A Dress; I Gutman 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 349 KB

The aim of this note is to call attention to a simple regularity regarding the number of walks in a finite graph G. Let wk denote the number of walks of length k(> 0) in G. Then Wi+,, 5 W&Wzb holds for all a, b E NJ while equality holds exclusively either (I) for all a, b E No (in case G is a regula

Efficient enumeration of all minimal sep
Efficient enumeration of all minimal separators in a graph
✍ Hong Shen; Weifa Liang 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 796 KB

This paper presents an efficient algorithm for enumerating all minimal a-b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = (V,E). Our algorithm requires O(n3R,b) time, which improves the known result of 0(n4R,b) time for solving this problem, whe

Generating the Acyclic Orientations of a
Generating the Acyclic Orientations of a Graph
✍ Matthew B Squire 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 206 KB

The acyclic orientations of a graph are related to its chromatic polynomial, to its reliability, and to certain hyperplane arrangements. In this paper, an algorithm for listing the acyclic orientations of a graph is presented. The algorithm is shown to Ž . require O n time per acyclic orientation ge