Cut vertex and unicyclic graphs with the maximum number of connected induced subgraphs
Notice bibliographique
Résumé
<p>Cut vertices are often used as a measure of nodes’ importance within a network. These are nodes whose failure disconnects a connected graph. Let <span class="math inline">\(N(G)\)</span> be the number of connected induced subgraphs of a graph <span class="math inline">\(G\)</span>. In this work, we investigate the maximum of <span class="math inline">\(N(G)\)</span> where <span class="math inline">\(G\)</span> is a unicyclic graph with <span class="math inline">\(n\)</span> nodes of which <span class="math inline">\(c\)</span> are cut vertices. For all valid <span class="math inline">\(n,c\)</span>, we give a full description of those maximal (that maximise <span class="math inline">\(N(.)\)</span>) unicyclic graphs. It is found that there are generally two maximal unicyclic graphs. For infinitely many values of <span class="math inline">\(n,c\)</span>, however, there is a unique maximal unicyclic graph with <span class="math inline">\(n\)</span> nodes and <span class="math inline">\(c\)</span> cut vertices. In particular, the well-known negative correlation between the number of connected induced subgraphs of trees and the Wiener index (sum of distances) fails for unicyclic graphs with <span class="math inline">\(n\)</span> nodes and <span class="math inline">\(c\)</span> cut vertices: for instance, the maximal unicyclic graph with <span class="math inline">\(n=3,4\mod 5\)</span> nodes and <span class="math inline">\(c=n-5>3\)</span> cut vertices is different from the unique graph that was shown by Tan et al. [<span><em>The Wiener index of unicyclic graphs given number of pendant vertices or cut vertices</em></span>. J. Appl. Math. Comput., 55:1–24, 2017] to minimise the Wiener index. Our main characterisation of maximal unicyclic graphs with respect to the number of connected induced subgraphs also applies to unicyclic graphs with <span class="math inline">\(n\)</span> nodes, <span class="math inline">\(c\)</span> cut vertices and girth at most <span class="math inline">\(g>3\)</span>, since it is shown that the girth of every maximal graph with <span class="math inline">\(n\)</span> nodes and <span class="math inline">\(c\)</span> cut vertices cannot exceed <span class="math inline">\(4\)</span>.</p>
Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.
Comment cette classification a été obtenuedéplier
Prédiction distillée sur la base complète
Imitation des enseignantsNi prévalence calibrée, ni vérité terrain. Validation humaine à venir. Apprise à partir de 10 348 étiquettes directes de Codex et de 10 348 étiquettes directes de Gemma. Le mode candidate est l'union des têtes enseignantes seuillées; le consensus est leur intersection. Ces sorties portent le statut machine_predicted_unvalidated et ne sont ni des étiquettes humaines ni des étiquettes directes de modèles de pointe.
Scores Codex et Gemma par catégorie
| Catégorie | Codex | Gemma |
|---|---|---|
| Métarecherche | 0,003 | 0,001 |
| Méta-épidémiologie (sens strict) | 0,001 | 0,001 |
| Méta-épidémiologie (sens large) | 0,002 | 0,000 |
| Bibliométrie | 0,000 | 0,002 |
| Études des sciences et des technologies | 0,001 | 0,001 |
| Communication savante | 0,000 | 0,000 |
| Science ouverte | 0,001 | 0,000 |
| Intégrité de la recherche | 0,000 | 0,001 |
| Charge utile insuffisante (le modèle a refusé de juger) | 0,000 | 0,000 |
Scores machine (provisoires)
Les deux têtes enseignantes du modèle étudiant, lues sur ce travail. Un score ordonne la base pour la relecture; il n'affirme jamais une catégorie, et le statut de validation accompagne chaque rangée tel quel.
Scores de référence d'un modèle non mature (critères de maturité non atteints, 7 itérations). Un score ordonne; il n'affirme jamais une catégorie.
score_only:v0-immature-baseline · tel quel depuis la passe de notation : score_only signifie que le nombre peut ordonner les travaux, et qu'aucune étiquette de catégorie n'en découleClassification
machine, non validéePrédiction automatique; un appel candidat d’une seule tête enseignante, pas un consensus.
Le détail, modèle par modèle et score par score, se trouve en fin de page sous « Comment cette classification a été obtenue ».