Maximal bipartite graphs with a unique minimum dominating set
Garrison Koch, Darren Narayan · 2025
Read Maximal bipartite graphs with a unique minimum dominating set by Garrison Koch, Darren Narayan (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-2511-01719.txt.
Introduction
Garrison Koch and Darren Narayan study graphs in which exactly one smallest dominating set exists. A dominating set is a group of vertices. Every vertex is in the group or next to one of its members. Fischermann and coauthors asked in 2003 how many edges a uniquely dominatable graph can have. They conjectured a bound and gave a construction meeting it.
Koch and Narayan ask how the answer changes when the graph must be bipartite, its vertices split into two camps with edges only across. They conjecture a bipartite bound and give constructions showing it is tight. They prove it for domination number two. They also prove it when the vertex count is three times the domination number. They also connect the constructions to perfect domination and exhibit graphs meeting both the general and bipartite bounds.
Catalog record
| CREATOR | Garrison Koch, Darren Narayan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 44 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-01719
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Maximal bipartite graphs with a unique minimum dominating set Garrison Koch, Darren Narayan Abstract . In 2003, Fischermann et al. considered the maximum size of uniquely-dominatable graphs, graphs whose dominating number is realized only by a unique dominating set. They conjectured a size bound and provide a general graph construction that shows the bound is tight [ 1 ] . In 2010, Shank and Fraboni prove Fischermann’s bound is true when γ = 2 \gamma=2 [ 2 ] . In this paper, we observe how Fischermann’s bound changes if we impart a different restriction on a graph — bipartiteness. We conjecture a bound on the maximum number of edges possible for uniquely-dominatable bipartite graphs. We provide constructions to demonstrate this bound is tight. We prove our bipartite bound is true for the γ = 2 \gamma=2 and n = 3 γ n=3\gamma cases. We also discuss perfect domination and how it relates to our extremal graph constructions. We provide constructions that meet both Fischermann’s bound for all graphs and our bound for bipartite graphs respectively, both of which are perfectly dominated. 1. Introduction A dominating set of a finite, simple graph G=(V,E) is a set of vertices D\subseteq V such that every vertex in V-D is adjacent to a vertex in D . The domination number, \gamma(G) is the minimum cardinality of a dominating set of G . In 1965, Vizing proved that the most number of edges a graph G can have given |V(G)|=n vertices and dominating number \gamma(G)=\gamma\geq 2 is \frac{1}{2}(n-\gamma)(n-\gamma+2) [ 3 ] . This will henceforth be referred to as Vizing’s bound . A newer dominating variant studied is called unique domination . As the name suggests, a uniquely-dominatable graph is a graph with only one (unique) minimum dominating set. In 2003, Fischermann et al. considered how Vizing’s bound could be reduced when they restrict their graphs to only uniquely-dominatable graphs. In their 2003 paper, Fischermann et al. conjecture the upper bound on the size of uniquely-dominatable graphs is \mathbf{m}(n,\gamma)={{n-\gamma}\choose{2}}-\gamma(\gamma-2) when n\geq 3\gamma and \gamma\geq 2 are the order and dominating number respectively [ 1 ] . We will call this Fischermann’s bound . To avoid confusion with the subsequent bound we will conjecture, Fischermann’s bound will use the above bolded \mathbf{m} when referenced. In their 2003 paper, Fischermann et al. construct uniquely-dominatable graphs with n vertices, domination number \gamma , and size \mathbf{m}(n,\gamma) [ 1 ] . In 2010, Shank and Fraboni proved the above bound is true when \gamma=2 [ 2 ] . Since then many other graph classes have been considered, such as by Hedetniemi as well as Gunther et al. who characterized how the bound behaves on certain tree graphs [ 4 ] [ 5 ] . The unique minimum dominating set problem has also been studied on dominating function variations such as on locating-dominating sets [ 6 ] . This leads us to the main conjecture of the paper. Conjecture 1 . Let G be a bipartite graph without isolated vertices with order n and dominating number \gamma . Let G have a unique minimum dominating set. If \gamma\geq 2 and n\geq 3\gamma , then the size of G , s(G) , is bounded above by m(n,\gamma)=2\gamma+2\Big\lceil\frac{\gamma}{2}\Big\rceil\Big\lfloor\frac{\gamma}{2}\Big\rfloor+\min\Big\{n-3\gamma,2\Big\lceil\frac{\gamma}{2}\Big\rceil-\Big\lfloor\frac{\gamma}{2}\Big\rfloor+1\Big\}\Big(2\Big\lceil\frac{\gamma}{2}\Big\rceil+1\Big)+\sum_{i=1}^{\Phi}\Big((2\Big\lceil\frac{\gamma}{2}\Big\rceil+1)+\Big\lceil\frac{i}{2}\Big\rceil\Big) where \Phi(n,\gamma)=\max(0,n-3\gamma-2\lceil\frac{\gamma}{2}\rceil-\lfloor\frac{\gamma}{2}\rfloor+1). We will henceforth refer to this as the bipartite bound , or simply Conjecture 1 . As we will discuss in Theorem 2 , a unique dominating set of size \gamma is not possible if n<3\gamma , hence the restriction seen above. Also, if \gamma=1 , the only bipartite graph possible is a K_{1,n-1} , which has size n-1 and clearly has a unique dominator if n\geq 3 . In Section 2.1 , we will provide a generalized bipartite construction to show this bound is tight. In Sections 2.3 and 2.2 , we prove the bound holds for the n=3\gamma and \gamma=2 cases. In Section 2.4 , we compare the bipartite bound to Fischermann’s bound in order to quantify how many edges we lose when we require bipartiteness. 2. Results Let us begin by defining some notation and terminology. Haynes defines the private neighborhood of a vertex v relative to a set of vertices S as pn(v,S)=\{u\in V:N(u)\cap S=\{v\}\} [ 7 ] . For example, u is a private neighbor of v with respect to the set S if u is adjacent to v and u is not adjacent to any other vertex in S . Haynes also defines the exterior private neighborhood of a vertex with respect to a set as epn(v,S)=pn(v,S)\cap(V-S) . That is to say, if u is a private neighbor of v with respect to S , u is also an exterior private neighbor if u\notin S . [ 8 ] . Private neighbors will be important for proving the bipartite bound when \gamma=2 . They are also pivotal in the construction of a perfectly dominated graphs. Next, we noted our bipartite bound conjecture is only true for n\geq 3\gamma . Theorem 2 . (From [ 1 ] ) If a graph G of order n without isolated vertices has a unique minimum dominating set D , then it is easy to see that the private exterior neighborhood epn(v,D)=N(v,G)\setminus N[D\setminus\{v\},G] of v with respect to D contains at least two vertices for each vertex v\in D . This observation implies that n\geq 3\gamma . Proof. For the sake of contradiction, assume v\in D has fewer than two exterior private neighbors with respect to the set D . Since G contains no isolated vertices, \exists u\in G such that \{u,v\}\in E(G) . Then the set D\cup\{u\}\setminus\{v\} is another minimum dominating set, which renders D not unique. ∎ Thus, throughout this paper, we analyze graphs whose order is at least three times its dominating size. 2.1. Tightness of Bipartite Bound In this section, we prove the bound given in Conjecture 1 is tight. To do so, we provide a generalized bipartite construction that is uniquely-dominatable and has the number of edges prescribed by the bound. First, we give a quick lemma that will aid in the final part of Theorem 4 ’s proof. Lemma 3 . Let n be a positive integer. Let the number of positive integers smaller than n and of the opposite parity (e.g. 9\rightarrow\{2,4,6,8\} ) be \tau(n) . Then, • \tau(n)=\lceil{\frac{n}{2}}\rceil=\frac{n}{2} if n is even. • \tau(n)=\lceil{\frac{n}{2}}\rceil-1=\lfloor{\frac{n}{2}}\rfloor if n is odd. Proof. The simple induction proof is left to the reader. ∎ Now, we are ready to prove our bipartite bound is tight. Theorem 4 . Let \mathcal{B}_{n,\gamma} be the set of all uniquely-dominatable bipartite graphs without isolated vertices with order n and dominating number \gamma . Then, for each choice of n\geq 3\gamma and \gamma\geq 2 , there exists a G\in\mathcal{B}_{n,\gamma} where s(G)=m(n,\gamma)=2\gamma+2\Big\lceil\frac{\gamma}{2}\Big\rceil\Big\lfloor\frac{\gamma}{2}\Big\rfloor+\min\Big\{n-3\gamma,2\Big\lceil\frac{\gamma}{2}\Big\rceil-\Big\lfloor\frac{\gamma}{2}\Big\rfloor+1\Big\}\Big(2\Big\lceil\frac{\gamma}{2}\Big\rceil+1\Big)+\sum_{i=1}^{\Phi}\Big((2\Big\lceil\frac{\gamma}{2}\Big\rceil+1)+\Big\lceil\frac{i}{2}\Big\rceil\Big) and \Phi(n,\gamma)=\max(0,n-3\gamma-2\lceil\frac{\gamma}{2}\rceil-\lfloor\frac{\gamma}{2}\rfloor+1). Proof. We will break this proof into three cases. Case 1: n=3\gamma . Notice in this case, the above bound simplifies to m(n,\gamma)=2\gamma+2\lceil\frac{\gamma}{2}\rceil\lfloor\frac{\gamma}{2}\rfloor. Let G have partite sets A and B . Let A=Y\cup D_{X} and B=X\cup D_{Y} . Let D_{X}=\{x_{1},x_{2},\ldots,x_{\lfloor\frac{\gamma}{2}\rfloor}\} . Let X=\{b_{1,1},b_{1,2},b_{2,1},b_{2,2},\ldots,b_{\lfloor\frac{\gamma}{2}\rfloor,1},b_{\lfloor\frac{\gamma}{2}\rfloor,2}\} . Let D_{Y}=\{y_{1},y_{2},\ldots,y_{\lceil{\frac{\gamma}{2}}\rceil}\} . Let Y=\{a_{1,1},a_{1,2},a_{2,1},a_{2,2},\ldots,a_{\lceil\frac{\gamma}{2}\rceil,1},a_{\lceil\frac{\gamma}{2}\rceil,2}\} . Note, |D_{X}|=\lfloor\frac{\gamma}{2}\rfloor , |D_{Y}|=\lceil\frac{\gamma}{2}\rceil , |X|=2\lfloor\frac{\gamma}{2}\rfloor , and |Y|=2\lceil\frac{\gamma}{2}\rceil . So, |A|=|Y|+|D_{X}|=\lceil\frac{3\gamma}{2}\rceil=\lceil\frac{n}{2}\rceil , and, |B|=|X|+|D_{Y}|=\lfloor\frac{3\gamma}{2}\rfloor=\lfloor\frac{n}{2}\rfloor , so |V(G)| indeed equals 3\gamma . Now, let \{b_{i,1},x_{i}\}\in E(G) and \{b_{i,2},x_{i}\}\in