For graphs A, B, let ( BA) 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 ( TG) = ( TH) for every k-node tree T, then for every k-node forest F, ( FG) = ( GH). 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 ( FG) depends only on n and d.
Subgraphs smaller than the girth
1980
Abstract
For graphs A, B, let ( BA) 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 ( TG) = ( TH) for every k-node tree T, then for every k-node forest F, ( FG) = ( GH). 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 ( FG) depends only on n and d.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
prod_421778-doc_149833.pdf
solo utenti autorizzati
Descrizione: Subgraphs smaller than the girth
Tipologia:
Versione Editoriale (PDF)
Dimensione
534.34 kB
Formato
Adobe PDF
|
534.34 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
