Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Counting five-node subgraphs

Abstract : We propose exact count formulae for the 21 topologically distinct non-induced connected subgraphs on five nodes, in simple, unweighted and undirected graphs. We prove the main result using short and purely combinatorial arguments that can be adapted to derive count formulae for larger subgraphs. To illustrate, we give analytic results for some regular graphs, and present a short empirical application on real-world network data. We also discuss the well-known result that induced subgraph counts follow as linear combinations of non-induced counts
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal-enac.archives-ouvertes.fr/hal-03097484
Contributor : Laurence Porte <>
Submitted on : Tuesday, January 5, 2021 - 1:16:00 PM
Last modification on : Tuesday, February 2, 2021 - 2:16:14 PM
Long-term archiving on: : Wednesday, April 7, 2021 - 9:19:48 AM

File

2009.11318.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03097484, version 1
  • ARXIV : 2009.11318

Collections

Citation

Steve Lawford. Counting five-node subgraphs. 2021. ⟨hal-03097484⟩

Share

Metrics

Record views

35

Files downloads

21