Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-17T07:47:59.021Z Has data issue: false hasContentIssue false

Counting Paths, Circuits, Chains, and Cycles in Graphs: a Unified Approach

Published online by Cambridge University Press:  20 November 2018

E. Biondi
Affiliation:
Institute di Elettrotecnica ed Elettronica del Politecnico di Milano, Milano, Italy
L. Divieti
Affiliation:
Institute di Elettrotecnica ed Elettronica del Politecnico di Milano, Milano, Italy
G. Guardabassi
Affiliation:
Institute di Elettrotecnica ed Elettronica del Politecnico di Milano, Milano, Italy
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The problem of counting partial subgraphs (or patterns, for short) in a given graph has been approached by several mathematicians from various points of view (see, e.g., [1; 3; 5; 13-15; 17-23; 26-29]; applications may also be found in [2; 8; 9; 16]). Specific algorithms have been presented and almost all of them are essentially based upon a careful analysis of the graph under consideration. In these cases, we say that a direct approach has been followed. Unfortunately, when large graphs are considered, all direct counting methods require rather cumbersome computations. For this reason, during the last few years many efforts have been made in finding suitable indirect counting methods. First, Biondi [5] faced the problem of counting cycles in non-oriented graphs by inspection of the complementary graph. More recently, a number of papers [1; 3; 21; 22; 28] have been concerned with counting trees in classes of non-oriented graphs having complementary graphs with special structural properties. However, to the best of our knowledge, no general indirect counting method is available in the literature.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1970