Subdomination in Graphs with Upper-Bounded Vertex Degree

Abstract

We find a lower bound for the k-subdomination number on the set of graphs with a given upper bound for vertex degrees. We study the cases where the proposed lower bound is sharp, construct the optimal graphs and indicate the corresponding k-subdominating functions. The results are interpreted in terms of social structures.

1. Introduction

Two-tier voting models, where voting inside separate citizens’ groups is performed in the first stage and specially selected electors implement the choice of groups on the whole society level during the second voting stage, have been known for a long time. Voting of conformal agents also reduces to two-tier voting models, when an agent’s vote depends on both her own beliefs and her social environment [1,2]. In the first stage, an agent decides whether to vote “for” or “against” depending on the beliefs of the majority in their environment, which includes the agent themselves; in the second stage, aggregation of the agents’ votes provides a decision.

Mathematical properties of two-tier voting procedures have been intensively studied for more than half a century, whereas thorough attention has been brought to the question of how much the results of two-tier voting can differ from direct voting under conditions of various social structures modeled by the graph of social interactions.

It is known that the graph of social interactions of n agents (represented by the graph vertices) where $n-2$ vertices with negative opinion are connected to two vertices with positive opinion almost unanimously votes “for” at the second stage of the two-level majority procedure, although almost all members of the society have negative opinion. Therefore, it makes sense to study restrictions on the graph of social interactions that allow one to alleviate this imbalance. Typically the research is done in terms of the so called domination number, which is the difference between the numbers of agents with positive and negative opinions.

Paper [3] studies the case of regular graphs (i.e., graphs with a fixed degree of vertices), which is remarkable because the domination number in such graphs turns out to be relatively large; that is, the voting result is positive only if a significant share of the society has positive opinions. Regular graphs can be used to approximate the cases with a limited number of contacts (neighboring vertices in the graph of social connections), which is very natural for real graphs of social interactions (the so-called “Dunbar number” and its analogues). However, the equality constraint on the degree of the vertices is quite strong and purely regular graphs are rare in reality. Therefore, it is of interest to generalize the results for regular graphs to wider classes of social interaction graphs.

To take into account cognitive limitations of humans, it makes sense to consider the case where the number of connections (the vertex degree in the graph of social interactions) is upper-bounded by a number $\Delta$ but no lower bound on the number of social connections is imposed.

This article has the following structure. The problem formulation is presented in Section 2. After a brief literature survey given in Section 3, in Section 4 we find a lower bound for the k-subdomination number on the set of graphs with a given nonstrict upper bound $\Delta$ for vertex degrees (see the formal definitions below). For the cases where the proposed lower bound is sharp we construct optimal graphs and indicate the corresponding k-subdominating functions. In the Conclusion we provide interpretations of these optimal graphs in terms of social structures.

2. Problem Formulation

Let G be a graph of order $n=\left|V\right|$ with vertex set $V=V\left(G\right)$ and edge set $E\left(G\right)$. Let $N\left[v\right]$ be the closed neighborhood of vertex $v\in V$ containing all vertices adjacent to v and v itself. For any real-valued function $f\left(v\right)$ defined for all $v\in V$ and any $S\subseteq V$, let $f\left(S\right)={\sum }_{v\in S}f\left(v\right)$. The weight of f is $f\left(V\right)$. A k-subdominating function (k-SDF) is a function $f:V\to \{-1,1\}$ such that $f\left(N\right[v\left]\right)>0$ for at least vertices $v\in V$.

Function f assigns an opinion that belongs to $\{-1,1\}$ to each vertex $v\in V$ of the graph. For any vertex $v\in V$, the value $f\left(v\right)=1$ means a positive opinion and the intention to vote “for”, while $f\left(v\right)=-1$ means a negative opinion and the intention to vote “against”. We will also say that a vertex $v\in V$ is “happy” if $f\left(v\right)=1$ and “unhappy” otherwise. A social agent (a vertex) listens to the opinions of its closed neighborhood before voting. On the voting day, vertex v decides to vote “for” if $f\left(N\right[v\left]\right)>0$ and “against” otherwise. By definition, the final decision is positive if and only if the opinion function is a k-subdominating function. We will also refer to a k-subdominating function as to an approving opinion function.

Let $\mathcal{G}$ be some family of graphs and let ${\gamma }_{ks}^{}\left(\mathcal{G}\right)$ be the minimum value of $f\left(V\right)$ for all approving f over all graphs in $\mathcal{G}$. Let us also define the minimum support, i.e., the minimum number of vertices with positive opinion $h_{min}^k\left(\mathcal{G}\right)=\frac{{\gamma }_{ks}^{}\left(\mathcal{G}\right)+n}{2}$. The k-subdomination problem is that of finding ${\gamma }_{ks}^{}\left(\mathcal{G}\right)$ (or, equivalently, $h_{\min }^k\left(\mathcal{G}\right)$) for a given family of graphs $\mathcal{G}$. An optimal graph $G\in \mathcal{G}$ and an optimal opinion function f are those where the minimum is attained.

Below we solve the k-subdomination problem for the class ${\mathcal{G}}_{n,\Delta }$ of graphs of order n with a given nonstrict upper bound $\Delta \ge 3$ for vertex degrees. We consider only graphs with each vertex having a loop, so that, for every vertex $v\in V$, $N\left[v\right]=N_v$, where $N_v$ is the standard neighborhood (the set of adjacent vertices) of v and $deg\left(v\right)=\left|N\right[v\left]\right|$, where $deg\left(v\right)$ is the number of vertices adjacent to v. The cases of $\Delta =1,2$ are trivial and thus not considered.

3. Related Work

The problems of finding the minimum support for proposals, i.e., the minimum number of happy vertices h, that enables approval under two-tier voting on graphs, have been studied in the literature in terms of graph domination. In the case where every vote is performed by simple majority and the opinion function $f:V\left(G\right)\to \{-1,1\}$ is varied, such a minimum h is denoted by $h_{min}\left(G\right).$

A weak majority dominating function [4] on $V=V\left(G\right)$ is an opinion function such that $f\left(N_u\right)>0$ for at least half of the vertices u in V. A strict majority function is an opinion function such that $f\left(N_u\right)>0$ for more than half of the vertices $u\in V$. As said above, for a positive integer k, a k-subdominating function is an opinion function such that $f\left(N_u\right)>0$ for at least k vertices u in $V.$ The latter concept reduces to the previous two when $k=\lceil \left|V\right|/2\rceil$ and $k=\lceil \left(\right|V|+1)/2\rceil ,$ respectively.

The weak majority domination number ${\gamma }_{\mathrm{maj}}\left(G\right)$ [4], the strict majority domination number ${\gamma }_{\mathrm{smaj}}\left(G\right)$ [5,6], and the k-subdomination number ${\gamma }_{ks}^{}\left(G\right)$ [7] of G are the minimum possible weights of a weak majority function, a strict majority function, and a k-subdominating function on $V\left(G\right),$ respectively. The minimum h corresponding to a weak majority dominating function on $V\left(G\right)$ will be denoted by $h_{min}^{\prime }\left(G\right)$ and the minimum h corresponding to a k-subdominating function by $h_{min}^k\left(G\right)$.

N. Alon proved (see [4,7]) that the weak majority domination number ${\gamma }_{\mathrm{maj}}\left(G\right)$ of a connected graph G is at most 2, which is equivalent to $h_{min}\left(G\right)\le \frac{n}{2}+1$. Moreover, ${\gamma }_{\mathrm{maj}}\left(G\right)$ does not exceed 1 (resp., $h_{min}\left(G\right)\le \frac{n+1}{2}$) when the order n of G is odd [5,7]. Obviously, in the latter case, ${\gamma }_{\mathrm{smaj}}\left(G\right)={\gamma }_{\mathrm{maj}}\left(G\right).$ For any graph G it holds (see [5]) that ${\gamma }_{\mathrm{smaj}}\left(G\right)\le 4$ and ${\gamma }_{\mathrm{smaj}}\left(G\right)\le 2$ for the class of all trees (respectively, $h_{min}\left(G\right)\le \frac{n}{2}+2$ and $h_{min}\left(G\right)\le \frac{n}{2}+1$ for such graphs on n vertices).

Furthermore, for any tree T of order n, $h_{min}^k\left(T\right) k\le +1$ [7]. This bound is sharp when $k\le \frac{n}{2}.$ Moreover, if $\frac{n}{2}<k\le n,$ then $h_{min}^k\left(T\right)\le k$ and this bound is sharp [8,9]. On the other hand, characterizing all trees such that $h_{min}^k\left(T\right)=$ with $\frac{n}{2}<k\le n$ is apparently still an open problem [10]. A general conjecture that $h_{min}^k\left(G\right)\le k$ for any connected graph G whenever $\frac{n}{2}<k\le n$ was disproved in [11] by the counterexample of the three-dimensional cube $G=Q_3$ and $k=5$, for which $h_{min}^5\left(G\right)=6$. However, for any connected graph G of order n and $\frac{n}{2}<k\le n$ it holds [9] that

$$h_{min}^k\left(G\right)\le (n-k+1)⌈\frac{k}{n-k+1}⌉.$$

Turning to the lower bounds, suppose that ${\mathcal{G}}_{n|d}$ is the class of all d-regular graphs with loops on n vertices,

$${\gamma }_{\mathrm{smaj}}(n,d)=\underset{G\in {\mathcal{G}}_{n|d}}{min}{\gamma }_{\mathrm{smaj}}\left(G\right);h_{min}(n,d)=\underset{G\in {\mathcal{G}}_{n|d}}{min}{h}_{min}\left(G\right).$$

Since $f\left(V\right)=h-(n-h)=2h-n,$ we have

$${\gamma }_{\mathrm{smaj}}(n,d)=2h_{min}(n,d)-n.$$

Henning [12] and independently Holm [13] proved that (in our notation), in the case of odd $d\ge 3,$

$$h_{min}(n,d)\ge \frac{n(d+1)}{4d}.$$

(1)

The same lower bound can be obtained from a more general result [6] on graphs with specified minimum and maximum vertex degrees. It was claimed [12,14,15,16,17] that the bound (1) is sharp or best possible. Technically, it is sharp in a weak sense; that is, it cannot be improved for some values of n and $d.$ As shown in [3], for any odd $d>1$ there are infinitely many n such that bound (1) can be improved for the class ${\mathcal{G}}_{n|d}$ of d-regular graphs with loops on n vertices. Moreover, the inaccuracy of (1) reaches $\frac{n+1}{2}$ in the case of graphs with $d\ge \frac{n+1}{2}$ (“high-degree” graphs).

The more accurate lower bound for odd $n,$

$$h_{min}(n,d)\ge \frac{(n+1)(d+1)}{4d}.$$

(2)

can be derived from a result of [14,15] (cf. [18], Theorem 4.15), which in turn follows from the results in [8,17] and Theorem 2 in [19] on k-subdomination numbers, by substituting $k=\frac{n+1}{2}$ (in the notation of [15], $q=\frac{n+1}{2n}$) in the case of odd $n.$ As shown in [3], this bound is sharp for graphs with $d<\frac{n+1}{2}$ (“low-degree” graphs). For high-degree graphs it is not sharp and its inaccuracy in bounding $h_{min}(n,d)$ can be estimated by $\left(1-\frac{n+1}{2d}\right)\frac{d+1}{2},$ which reduces to $\frac{n^2-1}{4n}$ when $d=n$.

The sharpness of the bound (2) generalized to the k-subdominating functions is claimed in ([14], Theorem 4.1). However, to prove this for a given $d,$ the author constructs a graph whose order n is determined by the parameter k of subdomination and is divisible by d (as in [12]), so this is sharpness in a weak sense. Similarly, the sharpness of the bounds given in ([19], Theorem 2) is established only for some values of the parameters, namely, when $k=n,$ or in other words, for n-subdomination (also called signed domination). It was proved in [3] that for all odd $n,d\in \mathbb{N}$ such that $d\le n,$

$$h_{min}(n,d)=⌈\frac{d+1}{2}·max\left\{\frac{n+1}{2d},1\right\}⌉+{\mathbf{1}}_{\left\{\right(5,3),(9,5\left)\right\}}\left((n,d)\right),$$

where the indicator function ${\mathbf{1}}_{\left\{\right(5,3),(9,5\left)\right\}}\left((n,d)\right)$ equals 1 when $(n,d)\in \left\{\right(5,3),(9,5\left)\right\}$ and 0 otherwise.

Let G be a graph of order n with the degree sequence $d_1\le d_2\le \dots \le d_n$. It was shown in [8] that, for such graphs and for $1\le k\le n$,

$$h_{min}^k\left(G\right)\ge \frac{1}{d_n}\sum _{i=1}^k⌈\frac{d_i+1}{2}⌉.$$

In particular, for the subclass of graphs with m edges (excluding loops), it holds that

$$h_{min}^k\left(G\right)\ge \frac{1}{2}\left(k-n+\frac{2m+n+k}{d_n}\right),$$

where $2m+n$ can be replaced with ${\sum }_{i=1}^n{d}_i.$

The following lower bound has been obtained in [17]:

$$h_{min}^k\left(G\right)\ge n-k\frac{(n-k)(d_n+1)+2m}{2d_1}$$

(with a slightly stronger version in the case of even vertex degrees) and a lower bound for $h_{min}^{\prime }\left(G\right)$ in [6]:

$$h_{min}^{\prime }\left(G\right)\ge n-\frac{n(d_n+1)+4m}{4d_1}.$$

A stronger result of [19] takes in our notation the following simple form:

$$h_{min}^k\left(G\right)\ge max\left\{\frac{s_k^{}}{d_n},n-\frac{n+2m-s_k}{d_1}\right\},$$

where $s_k={\sum }_{i=1}^k(d_i+1)/2.$ This bound is attainable.

The decision problem corresponding to computing ${\gamma }_{\mathrm{maj}}\left(G\right)$ is NP-complete [4].

A number of additional inequalities related to majority domination and k-subdomination can be found in [10]. For other results applicable to regular and nearly regular graphs with some variations of the majority domination and k-subdomination models we refer to [20,21,22,23,24,25,26,27,28].

While classical graph-theoretic reasoning is widely used in graph domination studies, we combine it with an integer programming language that has been successfully applied in the past to the similar Roman graph domination problem (see [29,30]).

We contribute to the literature on k-subdomination by proposing a novel lower bound for the k-subdomination number on the set of graphs with a given upper bound for the vertex degrees, and proving that this lower bound is attained when the voting quota is not too high and is divisible by a linear function of the upper bound of vertex degree (see Theorems 2 and 3). Our approach is based on the original reduction of the k-subdomination problem to the integer linear program and the proposed lower bound is obtained from the continuous relaxation of this program.

4. Results

 Definition 1.

We will say that the voting conditions for vertex $v\in V$ in graph $\tilde{G}=(V,\tilde{E})$ with opinion function $\tilde{f}$ are no worse than those in graph $G=(V,E)$ with opinion function f if, in the former case, vertex v has at least as many neighbors with positive opinion and no more neighbors with negative opinion than in the latter case.

 Lemma 1.

For the class of graphs ${\mathcal{G}}_{n,\Delta }$, the solution of the k-subdomination problem $h_{min}^k\left({\mathcal{G}}_{n,\Delta }\right)$ is at least $z^{*}$, where $z^{*}$ is the solution of the following two-dimensional linear program:

$$\begin{array}{c}\hfill \underset{x,y}{min}x+y\end{array}$$

(3a)

$$\begin{array}{c}\hfill \mathrm{\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}s}.\mathrm{t}.\hspace{1em}\hspace{1em}\hspace{1em}n-\ge x\ge 0,\end{array}$$

(3b)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em} y\ge 0,\end{array}$$

(3c)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\frac{\Delta -1}{2}x+\frac{\Delta +3}{4}y\ge k,\end{array}$$

(3d)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\frac{\Delta +1}{2}x-\frac{\Delta -3}{2}y\le n,\end{array}$$

(3e)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\frac{\Delta +5}{4}x+y\le n.\end{array}$$

(3f)

 Proof.

Let us consider an optimal graph G, that has the minimum number of edges among all optimal graphs, and let f be its optimal opinion function. The vertices of G can be divided into four classes. Vertices of class A are happy but vote “against” in the two-tier voting. Vertices of class B are unhappy, but vote “for”. Vertices of class C are happy and vote “for”, while vertices of class D are unhappy and vote “against”.

First let us note that any neighbor u of a vertex v of class A votes “for”. Indeed, if u votes “against”, then the edge $uv$ can be removed without decreasing the number of positive votes (since both u and v vote “against” in G); that is, an optimal graph exists with a smaller number of edges, which contradicts the assumption.

In a similar way, it is easy to see that any vertex v in class B has ${deg}_G\left(v\right)=3$ and both its neighbors are happy. Indeed, an unhappy vertex votes “for” only if it has at least two happy neighbors. Connections with other neighbors could be removed without worsening the voting conditions of these vertices (since an unhappy neighbor is not a neighbor any more) and without changing the vote of vertex v (it still votes “for”, since both of its neighbors are happy). In this way one would obtain an optimal graph with a smaller number of edges, which is impossible by assumption.

Finally, any vertex v in class D is isolated (so that ${deg}_G\left(v\right)=1$), otherwise connections with all its neighbors could be removed without worsening the voting conditions of these vertices (an unhappy neighbor is cut off) and without changing the vote of vertex v, thus resulting in an optimal graph with a smaller number of edges.

Therefore, vertices of class A can only be connected to vertices of classes B and C, vertices of class B can be connected to vertices of classes A and B, vertices of class C can be connected to vertices of classes A, B, and C, while all vertices of class D are isolated.

Let us denote by $n_A,\dots ,n_D$ the number of vertices in the corresponding class. Let $n_{AB}$ stand for the number of edges between vertices of classes A and B, $n_{AC}$ be the number of edges between the vertices of classes A and C, $n_{BC}$ be the number of edges between the vertices of classes B and C, while $n_{CC}$ be the doubled number of edges between vertices of class C.

These variables are connected by the following relationships:

• All variables are non-negative, so

  $$n_A\ge 0,\dots ,n_D\ge 0,n_{AB}\ge 0,n_{AC}\ge 0,n_{BC}\ge 0,n_{CC}\ge 0.$$

  (4)
• The degree of any vertex is bounded by $\Delta$, so the total number of edges that connect the vertices of class A or class C with vertices outside the class cannot exceed the number of vertices in the class multiplied by the degree upper bound $\Delta$ (diminished by 1 to account for loops):

  $$n_{AB}+n_{AC}\le (\Delta -1)n_A,$$

  (5)

  $$n_{AC}+n_{BC}+n_{CC}\le (\Delta -1)n_C.$$

  (6)
• Vertices of class B have degree 3, so

  $$n_{AB}+n_{BC}=2n_B.$$

  (7)
• Vertices of class A vote “against”, so

  $$n_{AB}\ge n_{AC}+2n_A.$$

  (8)
• Vertices of class C vote “for”, so

  $$n_{AC}+n_{CC}\ge n_{BC}.$$

  (9)
• Graph G has n vertices in total, so

  $$n_A+n_B+n_C\le n.$$

  (10)
• Voting is positive, so

  $$n_B+n_C\ge k.$$

  (11)

Conditions (4)–(11) are also satisfied for any optimal graph, while the total number $n_A+n_C$ of vertices with positive opinion in such a graph is minimal. Therefore, the problem of finding the minimum value $z^{*}$ of the sum $n_A+n_C$ under constraints (4)–(11) is a relaxation of the k-subdomination problem (because we neglect the integrality of variables and some other constraints of the problem). Moreover, if, for the optimal values of $n_A,\dots ,n_D,n_{AB}\dots n_{CC}$, a graph $G\in {\mathcal{G}}_{n,\Delta }$ can be constructed, then graph G with the accompanying opinion function is optimal.

Let us simplify this linear program. First, from Equation (7) it is easy to find that $n_{AB}=2n_B-n_{BC}$ and, excluding $n_{AB}$ from the formulation, we obtain the problem:

$$\min n_A+n_C$$

(12a)

$$\begin{array}{c}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{s}.\mathrm{t}.\hspace{1em}\hspace{1em}{n}_A\ge 0,\dots ,n_D\ge 0,n_{AC}\ge 0,n_{BC}\ge 0,\hfill \end{array}$$

(12b)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}0\le n_{CC,}\end{array}$$

(12c)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{n}_{AC}+n_{BC}\le n_{CC,}\end{array}$$

(12d)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}(\Delta -1)n_C-n_{AC}-n_{BC}\ge n_{CC,}\end{array}$$

(12e)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}2n_B-n_{AC}-2n_A\ge n_{BC,}\end{array}$$

(12f)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}2n_B+n_{AC}-(\Delta -1)n_A\le n_{BC,}\end{array}$$

(12g)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}2n_B\ge n_{BC,}\end{array}$$

(12h)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{n}_A+n_B+n_C\le n,\end{array}$$

(12i)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{n}_B+n_C\ge k.\end{array}$$

(12j)

All variables except those included in the objective function can be excluded using the procedure that is illustrated below on the example of variable $n_{CC}$. From (12) we see that $n_{CC}$ is met only in constraints (12c)–(12e), being constrained from below by (12c) and (12d), and constrained from above by (12e). Variable $n_{CC}$ affects only problem feasibility, but not the objective function.

Combining ((12c) and (12d) with (12e) we obtain:

$$0\le n_{CC}\le (\Delta -1)n_C-n_{AC}-n_{BC},$$

(13)

$$n_{AC}+n_{BC}\le n_{CC}\le (\Delta -1)n_C-n_{AC}-n_{BC}.$$

(14)

From (13) and (14) it is clear that a feasible value of $n_{CC}$ exists if and only if

$$0\le (\Delta -1)n_C-n_{AC}-n_{BC},$$

(15)

$$n_{AC}+n_{BC}\le (\Delta -1)n_C-n_{AC}-n_{BC}.$$

(16)

Thus, if one is not interested in the exact value of $n_{CC}$, this variable can be excluded, and constraints (12c)–(12e) can be replaced with (15) and (16). Moreover, from (12b) we know that $n_{AC},n_{BC}\ge 0$; inequality (15) obviously majorizes (16), so that constraint (15) can be omitted, and we obtain the following equivalent program:

$$\begin{array}{c}\hfill min\hspace{1em}\hspace{1em}{n}_A+n_C\end{array}$$

(17a)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\mathrm{s}.\mathrm{t}.\hspace{1em}{n}_A\ge 0,\dots ,n_D\ge 0,n_{AC}\ge 0,n_{BC}\ge 0,\end{array}$$

(17b)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em} n_{AC}+n_{BC}\le (\Delta -1)n_C-n_{AC}-n_{BC,}\end{array}$$

(17c)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}2n_B-n_{AC}-2n_A\ge n_{BC,}\end{array}$$

(17d)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}2n_B+n_{AC}-(\Delta -1)n_A\le n_{BC,}\end{array}$$

(17e)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}2n_B\ge n_{BC,}\end{array}$$

(17f)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{n}_A+n_B+n_C\le n,\end{array}$$

(17g)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{n}_B+n_C\ge k.\end{array}$$

(17h)

Sequentially excluding variables $n_B,n_D,n_{AC},n_{BC}$ in a similar fashion (the routine calculations are omitted) we end up with the following optimization problem:

$$\begin{array}{c}\hfill \underset{n_A,n_C}{min}\hspace{1em}{n}_A+n_C\end{array}$$

(18a)

$$\begin{array}{c}\hfill \mathrm{s}.\mathrm{t}.\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}n-k\ge n_A\ge 0,\end{array}$$

(18b)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{n}_C\ge 0,\end{array}$$

(18c)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\frac{\Delta -1}{2}{n}_A+\frac{\Delta +3}{4}{n}_C\ge k,\end{array}$$

(18d)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\frac{\Delta +1}{2}{n}_A-\frac{\Delta -3}{2}{n}_C\le n\end{array}$$

(18e)

$$\begin{array}{c}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\frac{\Delta +5}{4}{n}_A+n_C\le n.\end{array}$$

(18f)

Finally, renaming $n_A$ and $n_C$ with x and y, respectively, completes the proof. □

 Theorem 1.

If $\Delta \le 5$, then $h_{min}^k({\mathcal{G}}_{n,\Delta })\ge \frac{4k}{\Delta +3}$. If $\Delta \ge 5$ then $h_{min}^k({\mathcal{G}}_{n,\Delta })\ge \frac{2k}{\Delta -1}$.

 Proof.

Since (3d) is the only constraint that limits from below the linear combination of both unknowns with positive weights, it takes the form of equality in the optimal solution. Let us relax all other constraints in (3) except for the non-negativity constraints. Then it is obvious that for $\Delta \le 5$ the minimum of the objective function is reached at $x=0$, $y=\frac{4k}{\Delta +3}$, and $z^{*}=y$, while, for $\Delta \ge 5$, the minimum is reached at $x=\frac{2k}{\Delta -1},y=0$, and $z^{*}=x$. From Lemma 1 we know that problem (3) is a relaxation of the k-subdomination problem, which completes the proof. □

 Theorem 2.

For all positive integers $n,k,\Delta$ such that Δ is odd, is divisible by $\frac{\Delta -1}{2}$, and $k\le n\frac{\Delta -1}{\Delta +1}$, $h_{min}^k\left({\mathcal{G}}_{n,\Delta }\right)=a=\frac{2k}{\Delta -1}$ holds, the optimum is attained on a “sunflower” graph (see Figure 1) with the number of vertices having positive opinions equal to a.

 Proof.

Under the conditions of the theorem, the “sunflower” graph with the given parameters exists. It includes $a=\frac{2k}{\Delta -1}$ vertices with positive opinion, so $h_{min}^k\left({\mathcal{G}}_{n,\Delta }\right)\le a=\frac{2k}{\Delta -1}$. On the other hand, by Theorem 1, for $\Delta \ge 5$, $h_{min}^k\left({\mathcal{G}}_{n,\Delta }\right)\ge \frac{2k}{\Delta -1}$ holds, which completes the proof. □

 Theorem 3.

For all positive integers $n,k,\Delta$ such that Δ is even, k is divisible by $\Delta -1$, and $k\le n\frac{\Delta -1}{\Delta +1}$, $h_{min}^k\left({\mathcal{G}}_{n,\Delta }\right)=a=\frac{2k}{\Delta -1}$ holds, the optimum is attained on the “alternating sunflower” graph (see Figure 2) with the number of vertices having positive opinions equal to a.

 Proof.

The proof is similar to that of Theorem 2. □

The above theorems, however, do not shed light on the case of graphs with the upper bound for the vertex degrees less than 5, which is partially covered by the following result.

 Theorem 4.

For all positive integers n and $k\le n$, $h_{min}^k\left({\mathcal{G}}_{n,3}\right)=2b+k\%3$ holds, where $b=\lfloor k/3\rfloor$ and operator $x\%y$ is “the remainder of x divided by y”. $h_{min}^k\left({\mathcal{G}}_{n,3}\right)$ is attained on a graph G that contains b cycles of length 3 whose vertices have opinions $1,1,$ and $-1$ in each cycle, and $k\%3$ isolated vertices with positive opinions. All other vertices in G are isolated and have negative opinions (see Figure 3).

 Proof.

Let us consider an optimal opinion function f over an optimal graph G of order n that has the maximum number of connected components among optimal graphs with the minimum number of edges. Equivalently, G is a graph in which at least k vertices vote “for”, while the number of happy vertices is minimal, and any other optimal graph $\tilde{G}$ of order n with vertex degree not exceeding 3 has the number of edges no less than in G and, if having the same number of edges, $\tilde{G}$ has no more connected components than G.

Since $\Delta \le 3$, G can have vertices of degree 1, 2, and 3. Hence, any optimal graph in ${\mathcal{G}}_{n,3}$, including G, is a disjoint union of cycles, paths, and isolated vertices.

The properties of G are as follows.

• $\mathit{G}$ contains no unhappy vertices of degree 2. Otherwise, let us consider an unhappy vertex v of degree 2 in G. This vertex votes “against” regardless of the labeling of its neighbor u, and the edge $uv$ can be removed without worsening the voting conditions for all vertices and without changing the number of unhappy vertices.
• Let $\mathit{G}$ contain an unhappy vertex $\mathit{v}$ of degree 3. Then both of its neighbors (call them ${\mathit{u}}_{\mathbf{1}}$ and ${\mathit{u}}_{\mathbf{2}}$) are happy. Otherwise, v votes “against”, and one can remove the edges $u_{1}v$ and $u_{2}v$ without worsening the voting conditions for v, $u_1$, and $u_2$ and reducing the number of edges, which contradicts the fact that G is an optimal graph with the minimum number of edges.
• Let $\mathit{G}$ contain a happy vertex $\mathit{v}$ of degree 3. Then one of its neighbors (call it ${\mathit{u}}_{\mathbf{1}}$), is happy and the second neighbor (name it ${\mathit{u}}_{\mathbf{2}}$) is unhappy.

  (a)

  Otherwise, if $u_1$ and $u_2$ are happy, we can connect them directly with edge $u_1{u}_2$ and isolate vertex v. The votes of all vertices do not change and the number of edges decreases, which contradicts the fact that G is an optimal graph with the minimum number of edges.

  (b)

  If both $u_1$ and $u_2$ are unhappy, then, from Item 1 above, the degrees of $u_1$ and $u_2$ equal 3. Let us denote their second neighbors by $w_1$ and $w_2$ and consider all possible alternatives:

  i.

  If $w_1$ is happy, we can isolate vertices $u_1$ and v and directly connect vertices $u_2$ and $w_1$. In this case, the voting conditions for vertices $u_2$ and $w_1$ do not change. Vertex v in graph G votes “against” because it has two unhappy neighbors but it votes “for” after being isolated. Vertex $u_1$, on the contrary, votes “for” in G and votes “against” after being isolated. Hence, the total number of positive votes has not changed and opinion function f is still approving for the new graph, which is optimal since the number of happy vertices is the same. However, the number of components has increased by two, which contradicts the definition of G.

  ii.

  Now let both $w_1$ and $w_2$ be unhappy. Then vertices $u_1$, $u_2$, and v vote “against”, and the opinion of vertex v can be changed to $-1$ without changing the vote, which strictly reduces the number of happy vertices and contradicts the fact that G is optimal.

  iii.

  Finally, let $w_1$ be unhappy and $w_2$ be happy. Then, similarly to Case 3(b)i, we connect vertices $u_1$ and $w_2$ and isolate vertices $u_2$ and v increasing the number of components, which contradicts the definition of G.

• Graph $\mathit{G}$ has no vertices of degree 2. We have already proved that no unhappy vertices of degree 2 exist. Let G have a happy vertex v of degree 2. This means that v is the beginning of a chain and, therefore, this chain has an end u, and, as follows from the above proof, u is also happy. A neighbor $v^{\prime }$ of v cannot be happy, otherwise one can add an edge $u{v}^{\prime }$ and isolate v leaving the opinion function approving over this new optimal graph and increasing the number of connected components by 1. If vertices $u^{\prime }$ and $v^{\prime }$ are unhappy, then one can isolate v by connecting $v^{\prime }$ directly to u. At the same time, the voting conditions of vertex $v^{\prime }$ do not change; u votes “against” as before and the voting conditions of vertex v have not worsened. However, the number of components increases, which contradicts the definition of G.

It is clear that, since graph G has no vertices of degree 2, it appears to be a disjoint union of cycles of length at least 3 with the repeating sequence of opinions “happy—happy—unhappy” and, possibly, some number of isolated vertices. In fact, the opinions of the cycle vertices are uniquely determined up to a cyclic shift. Let us assign the index “0” to any happy vertex in a cycle. Then, from Item 3 above, one of its neighbors (let us label it by “$-1$”) should be happy and the second one (let us label it as “$+1$”) should be unhappy. Then, from Item 3, the second neighbor of “$-1$” (call it “$-2$”) must be unhappy and, from Item 2, the second neighbor of “$+1$” must be happy. Hence, to avoid contradiction, the length of the cycle must be divisible by 3. Now it is clear that to maximize the number of components in G, all cycles must have length 3.

Let graph G contain a cycles. All vertices of them vote “for”, with $2a$ happy vertices. Let there be x happy vertices among isolated vertices. Graph G is optimal, so a and x are found as the solution of the minimization problem $2a+x\to min$ over all non-negative $a,x$ satisfying the condition $3a+x\ge k$. If $3a+x>k$ in the optimal solution, then $x=0$, as otherwise x could be reduced by 1 improving the optimal solution. That is, a is the minimum number of cycles such that $3a>k$. By definition, it is only possible if k is not divisible by 3. If $3a=k+2$, then the solution $a^{\prime }=a-1,x=1$ is better, while, if $3a=k+1$, then this solution is not worse, which is impossible due to the optimality of G.

Therefore, we can assume that $3a+x=k$ and $x=k-3a$. We know that $2a+x=k-a$, i.e., a has the maximum value for which $3a\le k$. Then x is the remainder of k divided by 3. □

5. Conclusions

In this paper, we studied the properties of the k-subdomination number for graphs with vertex degrees limited by a given constant $\Delta$. The main results are summarized in Figure 4.

It has been shown that, in the optimal graph, the k-subdomination number is sufficiently low; there exist graphs of social interactions with positive voting while the ratio of unhappy agents to those happy has the order of the maximum vertex degree (see Theorems 2 and 3; details depend on the ratios of the graph size n, the upper bound $\Delta$ for the vertex degree, and the voting quota k). Thus, the minimum support (the number of happy vertices) decreases inversely as the degree $\Delta$ increases, and the social properties of the corresponding graph quickly converge to those of the optimal graph that has no upper bound for the maximum vertex degree (for example, in Figure 4, for $n=100$ and $k=80$, the support is only 16 under the relatively small upper bound of $\Delta =11$ for the degree). These social characteristics are completely different from those of regular graphs.

Although the social structure with the duopoly of two “opinion leaders”, which arises when no degree restrictions are imposed, cannot be exactly reproduced in graphs with vertex degrees limited from above by number $\Delta$, we have there a situation of oligarchy where any “ordinary vertex” is connected to exactly two members of a limited “corporation of public opinion leaders”. Each opinion leader, in turn, influences $\Delta -1$ ordinary vertices through its social links.

In terms of political science, if the number of social ties of the “ordinary vertices” may be kept low, for example, by the government, then through a “corporation of opinion leaders” this government can effectively manipulate the social choice. To avoid this situation, one has to increase the lower bound of the number of social ties. In other words, to have the k-subdomination number approaching the relatively high values (such as those found in regular graphs), each member of the society should maintain a larger number of social contacts (connections in the social graph). The detailed study of this effect is a promising subject of future research, which can use the optimization-based technique introduced in the present article.

An open question not covered by the results of the present paper is the shape of the optimal graph for the case where vertex degrees are bounded by 4 (see the gap in blue dots for $\Delta =4$ in Figure 4), which requires additional investigation.