The cycle-path indicator polynomial of a digraph

DOI10.1006/AAMA.2000.0689MaRDI QIDQ1585495zbMATH OpenOpenAlexFDO

Authors Ottavio M. D'Antona, Emanuele Munarini

Publication date 16 November 2000

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/aama.2000.0689

zbMATH Keywords

cover polynomialcycle-path covercycle-path indicator polynomialdigraphrook polynomial

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38)

Review text

A cycle-path cover of a digraph is a spanning subgraph whose components are paths and cycles. The authors introduce what they call the cycle-path indicator polynomial of a digraph in order to count the cycle-path covers according to their type. They study the properties of this polynomial, in particular, the polynomial satisfies a deletion-contraction recurrence relation. They introduce various specializations, including one that is closely related to the cover polynomial of Chung and Graham, and they also show how a generalization of the rook polynomial can be obtained by the cycle-path indicator polynomial.

Recommendations

• The path-cycle symmetric function of a digraph
• scientific article; zbMATH DE number 3859168
• The matrix cover polynomial
• On the cover polynomial of a digraph
• The Digraph Drop Polynomial

Cites work

• A symmetric function generalization of the chromatic polynomial of a graph
• scientific article; zbMATH DE number 3127542 (Why is no real title available?)
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• scientific article; zbMATH DE number 1195749 (Why is no real title available?)
• scientific article; zbMATH DE number 3443655 (Why is no real title available?)
• scientific article; zbMATH DE number 1416069 (Why is no real title available?)
• scientific article; zbMATH DE number 3409479 (Why is no real title available?)
• Location of Zeros of Chromatic and Related Polynomials of Graphs
• On a class of polynomials obtained from the circuits in a graph and its application to characteristic polynomials of graphs
• On the cover polynomial of a digraph
• The partition polynomial of a finite set system
• The path-cycle symmetric function of a digraph

Cited in

(9)

• Variations sur le thème \({E+\overline {E} = XY}\) (Variations on the theme \({E+\overline {E} = XY})\)
• The path-cycle symmetric function of a digraph
• The \(m\)-path cover polynomial of a graph and a model for general coefficient linear recurrences
• The drop polynomial of a weighted digraph
• Complexity and approximability of the cover polynomial
• \(\{em,vk\}\)-cyclic path covering number of digraphs
• The Digraph Drop Polynomial
• CUMULANTS IN NONCOMMUTATIVE PROBABILITY THEORY III: CREATION AND ANNIHILATION OPERATORS ON FOCK SPACES
• On the counting complexity of the cover polynomial for simple graphs

This page was built for publication: The cycle-path indicator polynomial of a digraph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1585495)