✦ LIBER ✦

The Cycle-Path Indicator Polynomial of a Digraph

✍ Scribed by Ottavio M. D'Antona; Emanuele Munarini

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 126 KB
Volume: 25
Category: Article
ISSN: 0196-8858
DOI: 10.1006/aama.2000.0689

No coin nor oath required. For personal study only.

✦ Synopsis

A cycle-path cover of a digraph D is a spanning subgraph made of disjoint cycles and paths. In order to count such covers by types we introduce the cyclepath indicator polynomial of D. We show that this polynomial can be obtained by a deletion-contraction recurrence relation. Then we study some specializations of the cycle-path indicator polynomial, such as the geometric cover polynomial (the geometric version of the cover polynomial introduced by Chung and Graham), the cycle cover polynomial, and the path cover polynomial.

As an application, we consider chromatic arrangements of non-attacking rooks and the associated polynomial which is symmetric and generalizes the usual rook polynomial.

📜 SIMILAR VOLUMES

Digraphs with maximum number of paths an

Digraphs with maximum number of paths and cycles

✍ Yehoshua Perl 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 482 KB

A polynomial algorithm for the Hamiltoni

A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs

✍ Bang-Jensen, J�rgen; Gutin, Gregory; Yeo, Anders 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 382 KB 👁 2 views

We describe a polynomial algorithm for the Hamiltonian cycle problem for semicomplete multipartite digraphs. The existence of such an algorithm was conjectured in G.

A Polynomial Time Algorithm for Finding

A Polynomial Time Algorithm for Finding a Cycle Covering a Given Set of Vertices in a Semicomplete Multipartite Digraph

✍ Anders Yeo 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 181 KB

The Square of Paths and Cycles

✍ G.H. Fan; H.A. Kierstead 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 388 KB

The square of a path (cycle) is the graph obtained by joining every pair of vertices of distance two in the path (cycle). Let \(G\) be a graph on \(n\) vertices with minimum degree \(\delta(G)\). Posa conjectured that if \(\delta(G) \geqslant \frac{2}{3} n\), then \(G\) contains the square of a hami

A Proof of a Conjecture of Bondy Concern

A Proof of a Conjecture of Bondy Concerning Paths in Weighted Digraphs

✍ B. Bollobás; A.D. Scott 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 365 KB

Our aim in this note is to prove a conjecture of Bondy, extending a classical theorem of Dirac to edge-weighted digraphs: if every vertex has out-weight at least 1 then the digraph contains a path of weight at least 1. We also give several related conjectures and results concerning heavy cycles in e

On the existence of a specified cycle in

On the existence of a specified cycle in digraphs with constraints on degrees

✍ Abdelhamid Benhocine 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 326 KB 👁 1 views

We prove that Woodall's and GhouileHouri's conditions on degrees which ensure that a digraph is Hamiltonian, also ensure that it contains the analog of a directed Hamiltonian cycle but with one edge pointing the wrong way; that is, it contains two vertices that are connected in the same direction by