Premium
Subgraphs smaller than the girth
Author(s) -
Simoncini Luca,
Taylor Herbert
Publication year - 1980
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190040111
Subject(s) - combinatorics , mathematics , girth (graph theory) , tree (set theory) , node (physics) , path (computing) , discrete mathematics , physics , computer science , computer network , quantum mechanics
For graphs A , B , let ( B A ) denote the number of subsets of nodes of A for which the induced subgraph is B . If G and H both have girth > k , and if ( T G ) = ( T H ) for every k ‐node tree T , then for every k ‐node forest F , ( F G ) = ( G H ). Say the spread of a tree is the number of nodes in a longest path. If G is regular of degree d , on n nodes, with girth > k , and if F is a forest of total spread ≤ k , then the value of ( F G ) depends only on n and d .