On the average size of 1 1 -nearly independent vertex sets in graphs
Audace A. V. Dossou-Olory, Eric O. Andriantiana · 2025
Read On the average size of 1 1 -nearly independent vertex sets in graphs by Audace A. V. Dossou-Olory, Eric O. Andriantiana (2025) 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-2510-23670.txt.
Introduction
Audace A. V. Dossou-Olory and a co-author count vertex sets that are almost independent in a graph. A 1-nearly independent set is a set of vertices whose induced subgraph contains exactly one edge; with zero edges allowed instead, the notion becomes the independent set. The authors study the average size of such sets across all of them in a given graph or tree.
They determine which graphs on a fixed number of vertices, apart from the edgeless graph where the average is zero, make that average smallest or largest. For trees they pin down the minimum. The maximum for trees is shown to sit between half the vertex count and above it, once the tree is large enough. A family of trees built by the authors shows those bounds cannot be tightened in the limit, so the tree maximum is understood up to a small gap.
Catalog record
| CREATOR | Audace A. V. Dossou-Olory, Eric O. Andriantiana |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-23670
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the average size of 1 1 -nearly independent vertex sets in graphs Audace A. V. Dossou-Olory, Eric O. Andriantiana Abstract . A k k -nearly independent vertex subset of a graph G G is a set of vertices that induces a subgraph containing exactly k k edges. For k = 0 k=0 , this coincides with the classical notion of independent subsets. This paper investigates the average size, a v 1 ( G ) av_{1}(G) of the 1 1 -nearly independent vertex subsets of both graphs and trees of a given order n n . Let E n E_{n} denote the n n -vertex edgeless graph, so that a v 1 ( E n ) = 0 av_{1}(E_{n})=0 . We determine all n n -vertex graphs G ≠ E n G\neq E_{n} that minimize or maximize a v 1 av_{1} . Similarly, we identify the trees of order n n that achieve the minimum value of a v 1 av_{1} , and prove that the maximum value lies between n / 2 n/2 and ( n + 1 ) / 2 (n+1)/2 if n > 8 n>8 . Finally, we construct a family of n n -vertex trees which shows that the bounds are asymptotically sharp. 2020 Mathematics Subject Classification Primary 05C30, 05C69; secondary 05C35, 05C75 1. Introduction Counting substructures in graphs is a central topic in combinatorics and graph theory. Among these, the enumeration of subgraphs—particularly induced subgraphs, spanning subgraphs, independent sets and their generalisations—plays a crucial role in understanding graph complexity and structure. Key questions include which n -vertex graphs minimise or maximise the number or average size of independent sets, under various structural constraints? An independent vertex set in a graph G is a set of vertices, no two of which are adjacent. The number of independent vertex sets of G is also known as the Fibonacci number or Merrifield- Simmons index of G in the mathematical literature. Their enumeration has deep ties to certain models in statistical physics via the hard-core model, where each independent set is assigned a weight based on its size (see [ 9 ] ). Let i(G) denote the number of independent vertex sets (including the empty set) in graph G . Among n -vertex graphs, the minimum is achieved by the complete graph K_{n} with i(K_{n})=n+1 . For graphs with a fixed number of vertices and edges, a classic result of Kahn [ 8 ] shows that the number of independent sets is maximized by a disjoint union of complete bipartite graphs. Specifically, among d -regular bipartite graphs G on n vertices such that 2d|n , the maximum value of i(G) is achieved by the disjoint union of n/2d copies of K_{d,d} , confirming a conjecture of Alon and Kahn. In general graphs, Zhao [ 11 ] extended Kahn’s entropy method to show that among all graphs with maximum degree \Delta , the number of independent vertex sets is asymptotically maximized by a disjoint union of K_{\Delta,\Delta} . Among regular graphs, the minimum is less understood, but lower bounds have been given in terms of vertex degrees. There are many other work on extremising i(G) when G is restricted to various classes of n -vertex graphs such as graphs with a given minimum degree [ 6 , 7 ] , or given degree sequence [ 2 ] . A 1-nearly independent vertex set allows exactly one pair of adjacent vertices in the collection. This concept was introduced recently by Andriantiana and Shozi in [ 1 ] , where various of its properties are discussed and extremal n -vertex graphs and n -vertex trees are characterised. The analogous edge version [ 4 ] counts edge-subsets with one adjacent pair; the star minimises and the path maximises this number among n -vertex trees. These new generalisations open further directions for extremal and enumerative analyses. Let \mathcal{S}_{0}(G) denote the set of all independent vertex subsets of graph G=(V,E) . Define the average size of independent vertex sets of G by \bar{s}(G):=\frac{1}{i(G)}\sum_{I\in\mathcal{S}_{0}(G)}|I|. Andriantiana et al. [ 3 ] showed that among all n -vertex graphs, \bar{s} is maximised by the edgeless graph and minimised by K_{n} , while among trees, the path minimises \bar{s} and the star maximises it. See also the old short paper [ 10 ] which studies the asymptotic behaviour of \bar{s}(G) in terms of order and the chromatic number of G , and the recent results [ 5 ] giving a tight lower bound on the expected size of a uniformly choosen independent set in triangle-free graphs of bounded degree. In this manuscript, we investigate the average size av_{1} of 1 -nearly independent subsets in the class of graphs of fixed order n , and subsequently in the class of trees of order n . Both upper and lower bounds are established, along with characterizations of the graphs that attain these bounds. The paper is structured as follows. In Section 2 , we formally define av_{1} , compute explicit expressions of av_{1} for graphs that have less complicated structures, and establish some technical recursive formulas. These formulas will later be needed in proving our main theorems. Section 3 is devoted to the study of average among n -vertex graphs. In particular, graphs with the smallest and largest av_{1} are characterized. In Section 4 we show that the star is the n -vertex tree with the smallest av_{1} . We also prove that the maximum value of av_{1} is less than (n+1)/2 for n>8 . Moreover, we characterise an explicit family of n -vertex trees R_{n} with av_{1}(R_{n})=n/2+\delta_{n} for some 0<\delta_{n}<1/2 , thus matching our bounds. Finally, we provide further relations between 0 - and 1 -nearly independent vertex sets in graphs in Section 5 . 2. Preliminary results Throughout this paper, all graphs are simple. The number of elements of a finite set S is denoted by |S| . The empty sum is treated as 0 . Let G=(V,E) be a simple graph and l a non-negative integer. As defined in [ 1 ] , a set S\subseteq V is called a l -nearly independent vertex set of G if the graph induced by S in G contains exactly l edges. Thus 0 -nearly independent vertex sets are precisely the classical independent vertex sets. Denote by \mathcal{S}_{l}(G) the set of all l -nearly independent vertex sets of G , and set \displaystyle\sigma_{l}(G):=|\mathcal{S}_{l}(G)|\quad\text{and}\quad S_{l}(G):=\sum_{S\in\mathcal{S}_{l}(G)}|S|\,, that is \sigma_{l}(G) is the number of l -nearly independent vertex sets of G , while S_{l}(G) is the sum of the sizes of the l -nearly independent vertex sets of G . We are specifically interested in the average size of a l -nearly independent vertex set of G , which is given by av_{l}(G):=\frac{S_{l}(G)}{\sigma_{l}(G)}\,, provided that \sigma_{l}(G)\neq 0 . If \mathcal{S}_{l}(G)=\emptyset , then it is consistent to write av_{l}(G)=0 . We denote by \sigma_{l}(G,k) the number of l -nearly independent vertex sets of G that have cardinality k . Clearly, \sigma_{0}(G,0)=1 , while \sigma_{l}(G,0)=0 for all l>0 and \sigma_{1}(G,k)=0 for all k<2 . We define the l -nearly series I_{l}(G;x) by I_{l}(G;x)=\sum_{k\geq 0}\sigma_{l}(G,k)x^{k}\,, which has a finite number of terms since \sigma_{l}(G,k)=0 for all k>|V(G)| . We refer to