Handle bases and bounds on the number of subgraphs
type: Item
instance of: scholarly article
title: Handle bases and bounds on the number of subgraphs
zbMATH Open document ID: 0612.05035
DOI: 10.1016/0095-8956(87)90058-X
author: B. George
published in: Journal of Combinatorial Theory. Series B
publication date: 1987-01-01T00:00:00Z
review text: A handle basis for a finite strongly connected digraph G expresses G as an edge-disjoint union \(h_ 0,...,h_{d-1}\) of subgraphs such that \(h_ 0\) is a simple cycle, \(h_ 1,...,h_{d-1}\) are nontrivial simple paths, and each \(h_ i\), \(i>0\), meets the union of the previous h's at its endpoints. Here d means the cyclomatic number of G. It is shown that a subgraph of G is uniquely characterized by an integer valued function on the vertices (i.e., its boundary) and by the elements of a handle basis which it intersects. A subgraph H is said to be cyclically simple if, roughly speaking, no cycle has access to any other. The authors show that the number of such H with given boundary is at most \(2^{d-1}\). This generalizes a result of \textit{T. Foregger} [Proc. Am. Math. Soc. 49, 319-324 (1975; Zbl 0274.15007)] on the permanent of fully indecomposable nonnegative integer matrices. Finally the authors discuss a special case where the permanent is bounded by a Fibonacci number.
reviewed by: J.Sedláček
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 15A15
zbMATH DE Number: 3989379
zbMATH Keywords: handle basis
zbMATH Keywords: strongly connected digraph
zbMATH Keywords: cycle
zbMATH Keywords: paths
zbMATH Keywords: permanent
MaRDI profile type: Publication
cites work: Q5578815
cites work: The diagonal equivalence of a nonnegative matrix to a stochastic matrix
cites work: A graph theoretic upper bound on the permanent of a nonnegative integer matrix. I
cites work: A graph theoretic upper bound on the permanent of a nonnegative integer matrix. II. The extremal case
cites work: An Upper Bound for the Permanent of a Fully Indecomposable Matrix
cites work: Graph-theoretic characterization of the matrix property of full irreducibility without using a transversal
cites work: On minimal elementary bipartite graphs
full work available at URL: 0095-8956(87)90058-x
OpenAlex ID: W2032045362
Recommended article: Bounds on the number of complete subgraphs
Recommended article: Bounds for the number of mappings of graphs and for the number of subgraphs
Recommended article: Upper bounds for the \(k\)-subdomination number of graphs
Recommended article: On the number of certain subgraphs contained in graphs with a given number of edges
Recommended article: Q5724802
Recommended article: On the number of connected subgraphs of graphs
Recommended article: Counting subgraphs via homomorphisms
Recommended article: Counting Subgraphs via Homomorphisms
Recommended article: Q4853715
Recommended article: Q3348931
description: scientific article; zbMATH DE number 3989379