Bicyclic graphs with the smallest and largest numbers of connected sets

Audace A. V. Dossou-Olory · 2026

Read Bicyclic graphs with the smallest and largest numbers of connected sets by Audace A. V. Dossou-Olory (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-26812.txt.

Introduction

Dossou-Olory counts connected vertex sets in bicyclic graphs, which are graphs with just two cycles. For an n-vertex graph, the count covers every nonempty set of vertices that forms one connected piece. The work finds which bicyclic graphs give the smallest such count. It also finds the largest and second largest counts. Exact extreme values are computed for the whole family. These results pin down how cycle structure shapes connected subsets.

Catalog record

CREATORAudace A. V. Dossou-Olory
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE30415
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.26812

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Bicyclic graphs with the smallest and largest numbers of connected sets Audace A. V. Dossou-Olory Abstract . For a graph G G with vertex set V V , let N ⁡ ( G ) \N(G) denote the number of nonempty subsets of V V that induce a connected graph in G G . In this paper, we focus on determining N ⁡ ( G ) \N(G) for G G in the family 𝔹 n \mathbb{B}_{n} of n n -vertex bicyclic graphs. We find in 𝔹 n \mathbb{B}_{n} the structures of those graphs that possess the smallest, the largest, as well as the second-largest values of N ⁡ ( G ) \N(G) . Moreover, we compute the extreme values of N ⁡ ( G ) \N(G) over 𝔹 n \mathbb{B}_{n} . 2020 Mathematics Subject Classification Primary 05C30; secondary 05C35, 05C69, 05C75 1. Introduction All graphs considered in this paper are undirected, simple (no loop and no parallel edge), and of finite order (i.e. the number of vertices). A connected set in a graph G=(V(G),E(G)) is a nonempty set S\subseteq V(G) that induces a connected subgraph in G . The edge set of the graph induced by S consists of those edges of G whose both endvertices belong to S . In this paper, we are interested in the overall number of connected sets in a connected graph G , henceforth denoted by \N(G) . Subgraphs constitute fundamental components of a graph, offering key insights into its intrinsic structure. For example, they can serve to identify essential building blocks and to uncover the functional characteristics of complex networks [ 11 ] . Over the past, much work has been devoted to determining the maximum and the minimum numbers of connected sets in different families of n -vertex graphs (i.e. graphs of order n ), and also to characterising graphs attaining the extreme values. As a trivial example, precisely the complete graph achieves the maximum number of connected sets among all graphs on n vertices. The literature contains a substantial number of research papers studying the extreme numbers of connected sets in acyclic graphs (i.e. in trees). As far as we know, this line of study on trees goes back to Székely and Wang [ 12 , 13 ] ; trees with given degree sequence were considered in [ 6 , 8 , 14 , 15 ] ; paper [ 7 ] studies trees with given segment sequence; trees with given diameter appeared in [ 9 ] ; paper [ 10 ] focuses on trees with given eccentric sequence; and many more, just to mention a few. We know that every n -vertex connected graph possesses n-1 edges or more, with the bound reached by trees only. A natural family of graphs after that of trees is perhaps the family of unicyclic graphs – connected n -vertex graphs having exactly n edges. In [ 2 ] , the structures of n -vertex unicyclic graphs that reach the extreme numbers of connected sets are completed derived, among other things. One of the questions at the end of paper [ 2 ] asks for constructive characterisation of the graphs that extremise the number of connected sets, over all connected graphs with prescribed order and number of cycles. In general, this problem can appear out of reach due to the various ways in which the cycles may intersect. However, special cases of so-called bicyclic graphs are still of interest. A bicyclic graph is a connected graph whose number of edges equals one more the number of vertices. Such a graph necessarily contains two or three different cycles. Unicyclic and bicyclic graphs are among the most popular tree-like structures, and various graph invariants and parameters have been studied in these families. In this paper, we shall determine close formulas, as a function of n , for the smallest and largest possible numbers of connected sets in a n -vertex bicyclic graph, and further derive all extreme graph structures. Some known extremal results on trees and unicyclic graphs will play an important role in our current context of determining the number of connected sets of a n -vertex bicyclic graph. Our main underlying trick relies on certain graph transformations that modify the number of connected sets, while preserving both the numbers of vertices and edges. Let us also mention other work related to the topic. We studied in [ 3 ] the two problems of maximising the number of connected sets of a unicyclic graph with prescribed order and girth, or prescribed order, girth, and number of pendant vertices. We determined in [ 4 ] the maximum number of connected sets in a connected graph with given order and number of cut vertices, the minimum number among all cut vertex-free connected graphs, and the extreme numbers as a function of both order and number of pendant vertices. However, the result on the maximum, given n vertices of which p are pendant, first appeared in [ 1 ] as a Nordhaus-Gaddum type. Paper [ 2 ] extended [ 4 ] to the maximum number of connected sets in unicyclic graphs with given order and number of cut vertices. In [ 5 ] , we investigated the maximum of \N(G) where G is a unicyclic graph with n vertices of which c are cut vertices, and found that there are generally two extremal structures. For each of the above mentionned graph families, all extremal graph structures were characterised. The current paper strictly focuses on n -vertex bicyclic graphs. We define our first notation and state some initial results in Section 2 ; our main finding are covered in Section 3 . 2. Preliminary Let G=(V(G),E(G)) be a connected graph. For u,v\in V(G) , we denote by \N(G)_{v} and \N(G)_{u,v} the number of connected sets in G that involve v , and those that contain both u and v , respectively. On the other hand, G-v denotes the graph that remains upon deleting vertex v in G ; more generally, G-S represents the graph obtained from G by deleting all elements of S . A u-v path in G is a path between vertices u and v , i.e. (u=)w_{0}w_{1}\ldots w_{m-1}w_{m}(=v) such that w_{i}w_{i+1}\in E(G) for all 0\leq i\leq m-1 . As usual, the n -vertex path will be denoted by P_{n} . A pendant vertex (or a leaf) in G is a vertex of degree 1 ; an edge incident with a pendant vertex is called a pendant edge . By C_{n}=v_{0}v_{1}v_{2}\ldots v_{n-1} we mean the cycle whose vertices are v_{0},v_{1},v_{2},\ldots,v_{n-1} in this order, i.e. v_{n-1} is adjacent to v_{0} , and v_{j}v_{j+1} is an edge for all 0\leq j\leq n-2 . We mention some known results that are relevant to us. Lemma 1 ( [ 12 ] ) . For the path P_{n} and u a leaf of P_{n} , we have \displaystyle\N(P_{n})=\binom{n+1}{2}\,,\quad\text{and}\quad\N(P_{n})_{u}=n\,. Lemma 2 ( [ 2 , 3 ] ) . For the cycle C_{n} and v\in V(C_{n}) , we have \displaystyle\N(C_{n})_{v}=1+\binom{n}{2}\,,\quad\text{and}\quad\N(C_{n})=n^{2}-n+1\,. At several occasions, we employ these two lemmas, without further reference. A graph G=(V(G),E(G)) is said to be bicyclic if |E(G)|=|V(G)|+1 and G is connected. Every such graph must have at least four vertices. We

Read the complete text