Contents

Ars Combinatoria

  • Research article

Gallai theorems involving minority and majority parameters

Mustapha Chellali1, Stephen T. Hedetniemi2, Nacéra Meddah1
1LAMDA-RO Laboratory, Department of Mathematics, University of Blida B.P. 270, Blida, Algeria
2School of Computing Clemson University Clemson, SC 29634 USA
  • Received: 06/11/2024
  • Accepted: 18/12/2024
  • Published: 31/12/2024

Abstract

In this note, we establish six Gallai theorems involving twelve minority and majority parameters. Accordingly, the complexity problems corresponding to some of these parameters are obtained.

Keywords: Minority sets, Majority sets, Total sets, Gallai-type results

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^{\prime }(G)\), and the edge covering number \(\beta^{\prime}(G)\).

Theorem 1.1 (Gallai).

For any graph \(G = (V, E)\) of order \(n = |V|\), (i) \(\alpha(G) +\beta(G) = n\), (ii) \(\alpha^{\prime}(G) + \beta^{\prime}(G) = n\).

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) \ge3\). 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) \ge3\), then every independent set is an internal minority set.

Consider, by contrast, a complete graph \(G = K_{2n}\) of even order, for \(n \ge1\). 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^{\prime}\) adjacent to each vertex \(u\in V\). In this case, provided that \(\delta(G)\geq 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.

Proposition 3.1. Let \(G\) be an isolate free graph. Then a subset \(S\) of vertices of \(G\) is a maximal internal minority set if and only if \(\overline{S}\) is a minimal external 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. \(\Box\)

Proposition 3.2. Let \(G\) be an isolate free graph. Then a nonempty subset \(S\) of vertices of \(G\) is a maximal total minority set if and only if \(\overline{S}\) is a minimal total majority set.

Proof. Assume that \(S\) is a nonempty maximal total minority set of \(G.\) It follows from the definition of \(S\) that \(\overline{S}\) is a total majority set. All that remains is to show that \(\overline{S}\) is a minimal total majority set. Suppose that \(\overline{S}\) is not a minimal total majority set of \(G.\) Thus, there is a vertex \(u\in\overline{S}\) such that \(\overline{S}-\{u\}\) is a total majority set of \(G,\) which results in the following: (i) every vertex in \(S\cup\{u\}\) has more neighbors in \(\overline{S}-\{u\}\) than it has in \(S\cup\{u\},\) and (ii) every vertex in \(\overline{S}-\{u\}\) has more neighbors in \(\overline{S}-\{u\}\) than it has in \(S\cup\{u\}.\) All this leads us to conclude that \(S\cup\{u\}\) is a total minority set of \(G\) contradicting the maximality of \(S.\)

Conversely, assume that \(\overline{S}\) is a minimal total majority set of \(G.\) It follows from the definition of \(\overline{S}\) that \(S\) is a total minority set. All that remains to show is that \(S\) is a maximal total minority set. Assume that \(S\) is not a maximal total minority set. Thus, there is a vertex \(v\) in \(\overline{S}\) such that \(S\cup\{v\}\) is a total minority set of \(G,\) which in turn means that: (i) every vertex in \(S\cup\{v\}\) has fewer neighbors in \(S\cup\{v\}\) than it has in \(\overline{S}-\{v\},\) and (ii) every vertex in \(\overline{S}-\{v\}\) has fewer neighbors in \(S\cup\{v\}\) than it has in \(\overline{S}-\{v\}.\) But then \(\overline {S}-\{v\}\) becomes a total majority set of \(G,\) contradicting the fact that \(\overline{S}\) is a minimal total majority set. ◻

Proposition 3.3. Let \(G\) be an isolate free graph. Then a nonempty subset \(S\) of vertices of \(G\) is a maximal external minority set if and only if \(\overline{S}\) is a minimal internal majority set.

Proof. Assume that \(S\) is a nonempty maximal external minority set of \(G.\) It follows from the definition of \(S\) that \(\overline{S}\) is an internal majority set. All that remains is to show that \(\overline{S}\) is a minimal internal majority set. Assume this is not the case, and let \(A\) be a subset of \(\overline{S}\) such that \(\overline{S}-A\) is an internal majority set of \(G.\) This means that every vertex in \(\overline{S}-A\) has fewer neighbors in \(S\cup A\) than it has in \(\overline{S}-A.\) But then \(S\cup A\) is an external minority set of \(G,\) contradicting the fact \(S\) is a maximal external minority set of \(G.\)

Conversely, assume that \(\overline{S}\) is a minimal internal majority set of \(G.\) It follows from the definition of \(\overline{S}\) that \(S\) is an external minority set. All that remains to show is that \(S\) is a maximal external minority set. Assume that this is not the case, and let \(B\) be a subset of \(\overline{S}\) such that \(S\cup B\) is an external minority set of \(G.\) It means that every vertex in \(\overline{S}-B\) has more neighbors in \(\overline{S}-B\) than it has in \(S\cup B,\) implying that \(\overline{S}-B\) is an internal majority set of \(G,\) contradicting the assumption that \(\overline{S}\) is a minimal internal majority set. ◻

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.

Theorem 3.4. For every isolate free graph \(G\) of order \(n,\)

(a)

\(\overline{M}^{+}(G)+\mu(G)=n.\)

(b)

\(\overline{M}(G)+\mu^{+}(G)=n.\)

Theorem 3.5. For every isolate free graph \(G\) of order \(n\) such that \(\mu_{t}(G)\neq0,\)

(c)

\(M_{t}^{+}(G)+\mu_{t}(G)=n.\)

(d)

\(M_{t}(G)+\mu_{t}^{+}(G)=n.\)

Theorem 3.6. For every isolate free graph \(G\) of order \(n\) such that \(\overline{\mu}(G)\neq0,\)

(e)

\(\overline{\mu}(G)+M^{+}(G)=n.\)

(f)

\(\overline{\mu}^{+}(G)+M(G)=n.\)

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.\)

References:

  1. J. Albertson, A. Harris, L. Langley, and S. Merz. Domination parameters and gallai-type theorems for directed trees. Ars Combinatoria, 81:201–207, 2006.
  2. R. B. Allan, R. C. Laskar, and S. T. Hedetniemi. A note on total domination. Discrete Mathematics, 49:7–13, 1984. http://doi.org/10.1016/0012-365X(84)90145-6.
  3. S. Balasubramanian, J. Farr, K. Bernasconi, R. Laskar, J. Villalpando, K. Hutson, G. Stevens, M. Gairing, and S. T. Hedetniemi. Gallai theorems involving domination parameters. Congressus Numerantium, 157:149–157, 2002.
  4. B. Bollobás, E. J. Cockayne, and C. M. Mynhardt. On generalised minimal domination parameters for paths. Discrete Mathematics, 86(1-3):89–97, 1990. https://doi.org/10.1016/0012-365X(90)90188-T.
  5. M. Borowiecki and D. Michalak. Generalised independence and domination in graphs. In Graph Theory (Erlangen, 1996), volume 191, pages 51–56. 1998. https://doi.org/10.1016/0012-365X(98)00092-2.
  6. M. Borowiecki and P. Mihók. Hereditary properties of graphs. In Advances in Graph Theory, pages 41–68. Vishwa International Publications, Gulbarga, 1991. https://doi.org/10.1016/S0095-8956(73)80009-7.
  7. M. Chellali, S. T. Hedetniemi, and N. Meddah. Majority sets in graphs. Manuscript (September 2022), submitted.
  8. M. Chellali, S. T. Hedetniemi, and N. Meddah. Minority sets in graphs. Manuscript (September 2022), submitted.
  9. E. J. Cockayne, S. T. Hedetniemi, and R. Laskar. Gallai theorems for graphs, hypergraphs and set systems. Discrete Mathematics, 72:35–47, 1988. https://doi.org/10.1016/S0012-365X(88)70769-6.
  10. G. S. Domke, J. E. Dunbar, and L. R. Markus. Gallai-type theorems and domination parameters. Discrete Mathematics, 167/168:237–248, 1997. https://doi.org/10.1016/S0012-365X(97)00021-8.
  11. P. Erdős and T. Gallai. On the minimal number of vertices representing the edges of a graph. Magyar Tud. Akad. Mat. Kut., 6:181–203, 1960.
  12. T. Gallai. Maximum-minimum theorems for networks, i. ii. Magyar Tud. Akad. Mat. Fiz. Oszt. Közl., 8:1–40, 1957.
  13. T. Gallai. Über extreme punkt-und kantenmengen. Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae Sectio Mathematica, 2:133–138, 1959.
  14. D. Geller and S. Hedetniemi. A proof technique in graph theory. In Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), pages 49–59. Academic Press, New York-London, 1969.
  15. F. Harary and M. D. Plummer. On the point-core of a graph. Mathematische Zeitschrift, 94:382–386, 1966.
  16. S. T. Hedetniemi. Hereditary properties of graphs. Journal of Combinatorial Theory, 14:94–99, 1973.
  17. S. T. Hedetniemi. A max-min relationship between matchings and domination in graphs. Congressus Numerantium, 40:23–34, 1983.
  18. A. Kemnitz and M. Marangio. A gallai’s theorem type result for the edge stability of graphs. Discrete Mathematics Letters, 12:118–121, 2023. https://doi.org/10.47443/dml.2023.088.
  19. J. D. McFall and R. Nowakowski. Strong independence in graphs. Congressus Numerantium, 29:639–656, 1980.
  20. S. Merz and D. Stewart. Gallai-type theorems and domination parameters in digraphs. Congressus Numerantium, 154:31–41, 2002.
  21. J. Nieminen. Two bounds for the domination number of a graph. Journal of the Institute of Mathematics and its Applications, 14:183–187, 1974.
  22. P. J. Slater. Enclaveless sets and mk-systems. Journal of Research of the National Bureau of Standards, 82:197–202, 1977.
  23. P. J. Slater. Generalized graph parameters: gallai theorems. Bulletin of the Institute of Combinatorics and its Applications, 17:27–37, 1996.
  24. V. Swaminathan and P. Thangaraju. Gallai-type theorems in domination and strong domination parameters. In Electronic Notes in Discrete Mathematics, volume 15, page 215, Amsterdam. Elsevier Science B.V., 2003. https://doi.org/10.1016/S1571-0653(04)00584-0.
  25. S. Zhou. A gallai-type equality for the total domination number of a graph. Discussiones Mathematicae Graph Theory, 24(3):539–543, 2004.
Information
Guidelines
CP Initiatives
Follow CP
Facebook X-twitter Linkedin

1970-2025 CP (Manitoba, Canada) unless otherwise stated.

Citation
Mustapha Chellali, Stephen T. Hedetniemi, Nacéra Meddah. Gallai theorems involving minority and majority parameters[J], Ars Combinatoria, Volume 161. -. https://doi.org/10.61091/ars161-11.