Gallai theorems involving minority and majority parameters

1. Introduction

In 1959, Gallai established [1] the now classic equalities involving the vertex independence number $\alpha (G)$, the vertex covering number $\beta (G)$, the edge independence, or matching, number ${\alpha }^{\mathrm{\prime }}(G)$, and the edge covering number ${\beta }^{\mathrm{\prime }}(G)$.

Since then there have been many similar results, which have come to be known as Gallai theorems. We refer the reader to [1,2,3,4,5,6,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25].

In this note we prove Gallai theorems for minority and majority parameters of a graph $G$. Minority and majority sets in graphs have been introduced in [8,7] as follows. Given an isolate-free graph $G=(V,E),$ let $S\subset V$ be a subset of vertices, where $\overline{S}=V-S$ denotes the vertices in $V$ that are not in $S$.

The set $S$ is called an internal minority set if every vertex $u\in S$ has (strictly) more neighbors in $\overline{S}$ than it has in $S$, while it is called an external minority set if every vertex $v\in \overline{S}$ has fewer neighbors in $S$ than it has in $\overline{S}$. Moreover, the set $S$ is called a total minority set if every vertex $w\in V$ has fewer neighbors in $S$ than it has in $\overline{S}$.

Similarly, a set $S$ is called an internal majority set if every vertex $u\in S$ has more neighbors in $S$ than it has in $\overline{S}$, while it is called an external majority set if every vertex $v\in \overline{S}$ has more neighbors in $S$ than it has in $\overline{S}$. And a set $S$ is called a total majority set if every vertex $w\in V$ has more neighbors in $S$ than it has in $\overline{S}$.

2. Examples of minority and majority sets

In this section we illustrate the concepts of minority and majority sets with a few examples. Let $G=(V,E)$ be a graph of order $n=|V|$, each vertex of which has at least three neighbors, that is, the minimum degree $\delta (G)$ satisfies $\delta (G)\ge 3$. Recall that a set $S\subset V$ is independent if no two vertices $u,v\in S$ are adjacent. Let $S$ be any independent set in $G$, and consider $S$ and $\overline{S}$. In this case $S$ is an internal minority set, since every vertex $u\in S$ has no neighbors in $S$. Thus, if $\delta (G)\ge 3$, then every independent set is an internal minority set.

Consider, by contrast, a complete graph $G=K_{2n}$ of even order, for $n\ge 1$. Arbitrarily divide the vertices in $V$ into two sets $V_1$ and $V_2$ of equal size. Thus, $|V_1|=|V_2|=n$. In this case $V_1$ is an internal minority set, since every vertex $u\in V_1$ has $n-1$ neighbors in $V_1$ but has $n$ neighbors in $V_2$. At the same time, $V_1$ is also an external majority set since every vertex $v\in V_2$ has $n$ neighbors in $V_1$ but only $n-1$ neighbors in $V_2$.

For another example, recall the definition of the corona $G\circ K_1$, which is the graph obtained from a graph $G$ by attaching a leaf $u^{\mathrm{\prime }}$ adjacent to each vertex $u\in V$. In this case, provided that $\delta (G)\ge 2$, the set of vertices $S=V(G)$ in $G\circ K_1$ is both an internal majority set and an external majority set, and hence $V(G)$ is a total majority set. At the same time, the set $S$ of leaves of $G\circ K_1$, being an independent set, is an internal minority set and an external minority set, and hence is a total minority set. Thus, in this case, we have a graph having a set $S$ which is a total majority set, whose complement $\overline{S}$ is a total minority set.

It is important to point out that in [8] it was noted that the empty set is the only total minority set for some isolate-free graphs, such as paths, cycles and stars. In such cases, it is assumed that ${\mu }_t(G)={\mu }_t^{+}(G)=0.$ The same applies for external minority sets, where it has also been assumed that $\overline{\mu }(G)={\overline{\mu }}^{+}(G)=0.$

3. Main results

We begin this section by giving the results needed to prove several Gallai theorems involving different minority and majority parameters. In the following proof, it is necessary to recall that the property of being an internal or total minority set is hereditary, that is, every subset of an internal or total minority set is also an internal or total minority set.

Similarly, the property of being an external or total majority set is superhereditary, in that every superset of an internal or total majority set is also an internal or total majority set.

Thus, (i) an internal or total minority set $S$ is maximal if and only if for every vertex $w\in \overline{S}$, the set $S\cup \{w\}$ is no longer an internal or total minority set, and (ii) an external or total majority set $S$ is minimal if and only if for every vertex $w\in S$, the set $S-\{w\}$ is no longer an external or total majority set.

Proof Assume that $S$ is a maximal internal minority set of $G.$ It follows from the definition of $S$ that $\overline{S}$ is an external majority set. All that remains is to show that $\overline{S}$ is a minimal external majority set. Suppose that $\overline{S}$ is not a minimal external majority set of $G.$ Thus, there is a vertex $u\in \overline{S}$ such that $\overline{S}-\{u\}$ is an external majority set of $G,$ that is, every vertex in $S\cup \{u\}$ has more neighbors in $\overline{S}-\{u\}$ than it has in $S\cup \{u\}.$ But then $S\cup \{u\}$ is an internal minority set of $G,$ contradicting the fact that $S$ is a maximal internal minority set.

Conversely, assume that $\overline{S}$ is a minimal external majority set of $G.$ Observe that no vertex $v$ in $\overline{S}$ can have a majority of its neighbors in $\overline{S}$ for otherwise $\overline{S}-\{v\}$ would be an external majority set which contradicts the minimality of $\overline{S}$. Since every vertex of $S$ has more neighbors in $\overline{S}$ than it has in $S$, it follows that $S$ is an internal minority set of $G.$ All that remains to show is that $S$ is a maximal internal minority set. Assume that $S$ is not a maximal internal minority set. Thus, there is a vertex $v$ in $\overline{S}$ such that $S\cup \{v\}$ is an internal minority set of $G,$ which in turn means that every vertex in $S\cup \{v\}$ has more neighbors in $\overline{S}-\{v\}$ than it has in $S\cup \{v\}.$ But then $\overline{S}-\{v\}$ is an external majority set of $G,$ contradicting the fact that $\overline{S}$ is a minimal external majority set. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

Thus, according to Propositions 3.1, 3.2 and 3.3, the following Gallai theorems are derived for the following parameters:

• $\mu (G),{\mu }^{+}(G)$, the minimum and maximum cardinalities of a maximal internal minority set,

• $\overline{\mu }(G),{\overline{\mu }}^{+}(G)$, the minimum and maximum cardinalities of a maximal external minority set,

• ${\mu }_t(G),{\mu }_t^{+}(G)$, the minimum and maximum cardinalities of a maximal total minority set,

• $M(G),M^{+}(G)$, the minimum and maximum cardinalities of a minimal internal majority set,

• ${\overline{M}}_t(G),{\overline{M}}_t^{+}(G)$, the minimum and maximum cardinalities of a minimal external majority set,

• $M_t(G),M_t^{+}(G)$, the minimum and maximum cardinalities of a minimal total majority set.

It has been shown in [8] and [7] that the problems of computing $\mu (G)$ and $\overline{M}(G)$ are NP-complete for bipartite graphs $G,$ while the problems of computing ${\mu }_t(G)$ and $M_t(G)$ are NP-complete for arbitrary graphs $G$. Consequently, according to Theorems 3.4 and 3.5, respectively, the complexity problems corresponding to ${\overline{M}}^{+}(G)$ and ${\mu }^{+}(G)$ will be NP-complete for bipartite graphs while those corresponding to ${\mu }_t^{+}(G)$ and $M_t^{+}(G)$ are NP-complete for arbitrary graphs $G.$