Enumerating simple paths from connected induced subgraphs

DOI10.1007/S00373-018-1966-9MaRDI QIDQ1756087zbMATH OpenOpenAlexWikidataFDO

Authors P.-L. Giscard, Paul Rochet

Publication date 11 January 2019

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.00289

zbMATH Keywords

directed graphdominating setsinclusion-exclusionself-avoiding walksHamiltonian pathssimple cycles

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30) Paths and cycles (05C38) Connectivity (05C40)

Abstract: We present an exact formula for the ordinary generating series of the simple paths between any two vertices of a graph. Our formula involves the adjacency matrix of the connected induced subgraphs and remains valid on weighted and directed graphs. As a particular case, we obtain a relation linking the Hamiltonian paths and cycles of a graph to its dominating connected sets.

Recommendations

• Enumeration of Hamiltonian Cycles and Paths in a Graph
• Enumerating Hamiltonian cycles
• On coefficients of path polynomials
• Algorithms to count paths and cycles
• Enumeration by e

Cites work

• scientific article; zbMATH DE number 3334023 (Why is no real title available?)
• scientific article; zbMATH DE number 3377269 (Why is no real title available?)
• A finite-difference sieve to count paths and cycles by length
• Algorithms to count paths and cycles
• Complexity of counting cycles using zeons
• Counting Paths and Packings in Halves
• Dynamic programming meets the principle of inclusion and exclusion
• Finding and counting given length cycles
• Inclusion and exclusion algorithm for the Hamiltonian path problem
• On the determination of redundancies in sociometric chains
• The number of \(n\)-cycles in a graph
• The self-avoiding walk.
• The traveling salesman problem in bounded degree graphs

Cited in

(4)

• A note on observables for counting trails and paths in graphs
• Enumeration by e
• A general purpose algorithm for counting simple cycles and simple paths of any length
• Counting paths of graphs via incidence matrices

This page was built for publication: Enumerating simple paths from connected induced subgraphs

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