Dominion of Some Graphs
2025
Read Dominion of Some Graphs (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-2512-24115.txt.
Introduction
Julian Allagan and Benkam Bobga study a counting question in graph theory. Start with a dominating set, a set of vertices such that every other vertex sits next to one of them, and take the smallest possible size of such a set. The dominion of a graph counts how many different sets achieve that minimum.
The authors relate these two parameters, the minimum size and the number of ways to reach it, which look unrelated at first sight. They then compute dominions for concrete families: paths, some cycles, and the join of any two graphs, where every vertex of one graph is linked to every vertex of the other. Results of this kind give graph theorists exact values for structured networks and tools for thinking about how many equally good guard placements a network admits.
Catalog record
| YEAR | 2025 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-24115
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Dominion of Some Graphs Abstract Given a graph G = ( V , E ) G=(V,E) , a subset S ⊆ V S\subseteq V is a dominating set if every vertex in V ∖ S V\setminus S is adjacent to some vertex in S S . The dominating set with the least cardinality, γ \gamma , is called a γ \gamma -set which is commonly known as a minimum dominating set. The dominion of a graph G G , denoted by ζ ( G ) \zeta(G) , is the number of its γ \gamma -sets. Some relations between these two seemingly distinct parameters are established. In particular, we present the dominions of paths, some cycles and the join of any two graphs. Julian A.D. Allagan 1 , Benkam Bobga 2 1 Department of Mathematics, Computer Science and Engineering Technology Elizabeth City State University Elizabeth City, North Carolina, U.S.A 2 Department of Mathematics University of North Georgia Gainesville, Georgia, U.S.A email: [email protected], [email protected] (January 28, 2021) 1 Introduction A dominating set for a graph G=(V,E) is a subset S\subseteq V such that every vertex v\in V is either in S or has a neighbor u\in S . The vertex u\in S is said to cover the vertex v\in V if either u=v or uv\in E . A dominating set S is a minimal dominating set if no proper subset S^{\prime}\subset S is a dominating set. The domination number \gamma(G) of a graph G is the minimum cardinality among all dominating sets of G . Clearly, a graph G can have multiple minimum dominating sets. For simplicity, we refer to those sets as \gamma -sets . Dominating sets, in particular \gamma -sets, have been extensively researched. We recommend to the reader Haynes et al.’s book [ 8 ] and several other research works [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 9 ] on variants and applications of dominating sets. In this literature we found various versions of \gamma -set such as the perfect dominating set, the double dominating set, the strong dominating set, and the restrained dominating set. In general, each such type of \gamma -set has some specified properties. Here, we list five of the most commonly studied \gamma -sets along with their properties. Later in Example 1.1 , we illustrate each such \gamma -set. 1. Perfect \gamma -set requires that no two vertices in a \gamma -set cover the same vertex (outside the \gamma -set). 2. Connected \gamma -set requires that the graph induced by the \gamma -set be connected. 3. Total \gamma -set forbids isolated vertices in the subgraph induced by the \gamma -set. 4. Independent \gamma -set requires all vertices in a \gamma -set to be isolated vertices in the subgraph they induce. 5. clique \gamma set requires that the vertices in a \gamma -set induce a clique. Because a given graph may have multiple \gamma -sets, this article addresses a natural but fundamental question: How many \gamma -sets does a given graph have? To answer this question, we introduce the notion of dominion . The dominion (number) of a graph G=(V,E) , denoted by \zeta(G) , is the number of its \gamma -sets. In other words, \zeta(G):=|\{S:S\text{ is a dominating set in}\ G\ \text{and}\ |S|=\gamma\}| . For instance, given a complete graph G=K_{n} , it is obvious that each v\in V(G) covers the remaining n-1 vertices of G . Therefore \zeta(G)=n while \gamma(G)=1 . Also, for a star graph G=K_{1,n} of order n+1\geq 3 , it is easy to see that \gamma(G)=1=\zeta(G) since only the central vertex can cover all of the remaining n\geq 2 vertices. Example 1.1 . Here, we illustrate the \gamma -sets of a unicyclic graph G (see Figure 1 ). u v x y w z Figure 1: A sun graph G with \gamma(G)=3 and \zeta(G)=8 Consider the unicyclic graph G as shown in Figure 1 . It is easy to see that \gamma(G)=3 . We list all the \gamma -sets with properties which are among the five commonly studied, as previously mentioned. • \{u,v,w\} is a perfect \gamma -set, a connected \gamma -set, a total \gamma -set, and a clique \gamma -set. • \{x,y,z\} is a perfect \gamma -set, and an independent \gamma -set. • \{u,y,z\} , \{v,x,z\} , and \{w,x,y\} are independent \gamma -sets but not perfect, connected, clique or total. • \{u,v,z\} , \{u,w,y\} , and \{v,w,x\} are \gamma -sets which have none of the 5 special properties that we previously listed. We have \displaystyle\zeta(G)=\sum_{i=0}^{3}{3\choose i}=8 , the number of \gamma -sets of G . We present a generalization of the previous example for such unicyclic graphs which are commonly known as sun graphs . Proposition 1.2 . If G is a sun graph on 2n\geq 6 vertices, then \displaystyle\zeta(G)=\sum_{i=0}^{n}{n\choose i}=2^{n}. Proof. For each vertex on the cycle, and for each dominating set S\subseteq V(G) , either the vertex or its leaf neighbor must be in S . Therefore, we can form all \gamma -sets S in G from choosing subsets of the set of n leafs, and the cycle neighbors of unchosen leafs. This gives \displaystyle\sum_{i=0}^{n}{n\choose i} . Conversely, every S assembled by choosing either the vertex on the cycle or the leaf, for each leaf, is a \gamma -set for G . This gives \zeta(G)=2^{n} . ∎ 2 Dominion of Some Graphs Suppose P_{n}:=v_{1}-v_{2}-\ldots-v_{n-1}-v_{n} , denotes a path on n\geq 2 vertices. We establish each of the following claims: Claim 2.1 . There is no \gamma -set that includes both vertices v_{n-1},v_{n} . Proof. Suppose n=3k+1 . It is easy to see that \gamma(P_{3k+1})=k+1 and without loss, let’s assume that there is a \gamma -set S , with |S|=k+1 , that includes both v_{3k},v_{3k+1} . Since v_{3k-1} is covered by v_{3k} (and vice versa), this leaves exactly 3k-2 vertices of P_{3k+1} that are to be covered using the remaining k-1 vertices of S . Because each vertex of S covers at most 2 other vertices of P_{3k+1} , k-1 vertices can cover at most 3(k-1) vertices of the path, and 3(k-1)<3k-2 . A similar argument addresses the case when n=3k+2 and the case when n=3k follows from a pigeonhole principle argument, since \gamma(P_{3k})=k . ∎ Claim 2.2 . There is no \gamma -set that excludes both vertices v_{n-1},v_{n} . Proof. Suppose S is a \gamma -set of P_{n} that excludes both consecutive vertices v_{n-1},v_{n} . It follows that v_{n}\in V(P_{n}) is left uncovered. Hence, S is not a \gamma -set of P_{n} . ∎ Claim 2.3 . Every \gamma -set includes either v_{n-1} or v_{n} but not both. Claim 2.4 . When n=3k,k\geq 1 , \zeta(P_{n})=1 and the unique \gamma -set in P_{n} contains v_{n-1} . Moreover, when n=3k+2,k\geq 1 , there is only one \gamma -set in P_{n} containing v_{n} . Proof. When n=3k,k\geq 1 , we have \zeta(P_{n})=k and the conclusion follows by the pigeon-hold argument alluded in Claim 2.1 . Each of the sets of 3 consecutive vertices \{v_{3r+1},v_{3r+2},v_{3r+3}\} , r=0,\ldots,k-1 , must contain at least one vertex of any \gamma -set S , and since \gamma=k , each of those sets must contain exactly one element of S . Since S is dominating, the element