Accéder directement au contenu Accéder directement à la navigation
Pré-publication, Document de travail

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
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

https://hal-enac.archives-ouvertes.fr/hal-03097484
Contributeur : Laurence Porte Connectez-vous pour contacter le contributeur
Soumis le : mardi 5 janvier 2021 - 13:16:00
Dernière modification le : mardi 19 octobre 2021 - 11:02:55
Archivage à long terme le : : mercredi 7 avril 2021 - 09:19:48

Fichier

2009.11318.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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

Collections

Citation

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

Partager

Métriques

Consultations de la notice

28

Téléchargements de fichiers

155