论文标题
切入最大连接的诱导子图数量的顶点和独立图形
Cut vertex and unicyclic graphs with the maximum number of connected induced subgraphs
论文作者
论文摘要
剪切顶点通常用作网络中节点重要性的量度。它们是那些失败断开图的节点。令n（g）为图$ g $的连接感应子图的数量。在这项工作中，我们调查了N（g）的最大值，其中$ g $是一个单车图，其中$ n $ nodes是$ c $ cut cut的顶点。对于所有有效的$ n，c $，我们全面描述了这些最大值（最大化n（。））unicclic图。发现通常有两个最大的独立图。但是，对于$ n，c $的无限值，有一个带有$ n $ nodes和$ c $ cut顶点的唯一最大独立图。特别是，与$ n $ nodes的单轮截图和$ c $ cut Cut顶点的连接感应子图的数量与维也纳指数（距离之和）之间的众所周知的负相关性：例如，$ n = 3,4 \ n = 3,4 \ mod 5 $ c = n-5 $ c = n-5 $ c = n-5> 3 $ c = n-5 $ c = n-5 $ c = n-5> 3 $ c $ c $ cut cut顶点： al。 J. Appl。数学。 Comput。，55：1--24，2017]，以最大程度地减少Wiener索引。关于连接引起的子图数的数量，我们对最大的Unicyclic图的主要特征也适用于带有$ n $ nodes，$ c $ cub cut Vertices和$ g> 3 $的独轮图图，因为它表明，每个最大值的girth a $ n $ n $ nodes and $ n $ c $ cut cut $ cut $ $ $ cut $ $ $ $ $ 4 $ 4 $ 4。
Cut vertices are often used as a measure of nodes' importance within a network. They are those nodes whose failure disconnects a graph. Let N(G) be the number of connected induced subgraphs of a graph $G$. In this work, we investigate the maximum of N(G) where $G$ is a unicyclic graph with $n$ nodes of which $c$ are cut vertices. For all valid $n,c$, we give a full description of those maximal (that maximise N(.)) unicyclic graphs. It is found that there are generally two maximal unicyclic graphs. For infinitely many values of $n,c$, however, there is a unique maximal unicyclic graph with $n$ nodes and $c$ 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 $n$ nodes and $c$ cut vertices: for instance, the maximal unicyclic graph with $n=3,4\mod 5$ nodes and $c=n-5>3$ cut vertices is different from the unique graph that was shown by Tan et al.~[{\em The Wiener index of unicyclic graphs given number of pendant vertices or cut vertices}. 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 $n$ nodes, $c$ cut vertices and girth at most $g>3$, since it is shown that the girth of every maximal graph with $n$ nodes and $c$ cut vertices cannot exceed $4$.
