Article in press
Authors:
Title:
Disjoint maximal independent sets in graphs and hypergraphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-01-27 , Revised: 2023-05-05 , Accepted: 2023-05-05 , Available online: 2023-06-07 , https://doi.org/10.7151/dmgt.2500
Abstract:
In this paper, we consider the question of the existence of disjoint maximal
independent sets (\MIS) in graphs and hypergraphs. The question was raised in
the 1970's independently by Berge and Payan. They considered the question
of characterizing the graphs that admit disjoint \MIS, and in particular whether
regular graphs do. In this paper, we are interested in the existence of disjoint
\MIS\ in a graph or in its complement, motivated by the fact that most
constructions of graphs that do not admit disjoint \MIS\ are such that their
complement does. We prove that there are disjoint \MIS\ in a graph or its
complement whenever the graph has diameter at least three or has chromatic
number at most four. We also define a graph of chromatic number 5 and diameter
2 which does not admit disjoint \MIS\ nor its complement.
As our work was first motivated by a more recent work on disjoint \MIS\ in
hypergraphs by Acharya (2010), we also consider the question of the existence
of disjoint \MIS\ in hypergraphs. We answer a question by Jose and Tuza
(2009), proving that there exists balanced $k$-connected hypergraphs admitting
no disjoint \MIS.
Keywords:
maximal independent set, clique, disjoint sets
References:
- B.D. Acharya, Domination in hypergraphs II: New directions, in: Recent Trends in Discrete Mathematics, Mysore, 2008, B.D. Acharya, G.O.H. Katona and J. Nešetřil (Ed(s)), (Ramanujan Math. Soc. Lect. Notes Ser. Math. 2010) 1–18.
- J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Elsevier Science Publishing Co., Inc., New York, 1976).
- E.J. Cockayne and S.T. Hedetniemi, Disjoint independent dominating sets in graphs, Discrete Math. 15 (1976) 213–222.
https://doi.org/10.1016/0012-365X(76)90026-1 - P. Erdős, A.M. Hobbs and C. Payan, Disjoint cliques and disjoint maximal independent sets of vertices in graphs, Discrete Math. 42 (1982) 57–61.
https://doi.org/10.1016/0012-365X(82)90053-X - W. Goddard and M.A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math. 313 (2013) 839–854.
https://doi.org/10.1016/j.disc.2012.11.031 - M.A. Henning, C. Löwenstein and D. Rautenbach, Remarks about disjoint dominating sets, Discrete Math. 309 (2009) 6451–6458.
https://doi.org/10.1016/j.disc.2009.06.017 - B.K. Jose and Zs. Tuza, Hypergraph domination and strong independence, Appl. Anal. Discrete Math. 3 (2009) 347–358.
https://doi.org/10.2298/AADM0902347J - C. Payan, Coverings by minimal transversals, Discrete Math. 23 (1978) 273–277.
https://doi.org/10.1016/0012-365X(78)90008-0 - C. Payan, Sur une classe de problèmes de couverture, C.R. Acad. Sci. Paris Sér. A 278 (1974) 233–235.
- C. Payan, A counter-example to the conjecture "every nonempty regular simple graph contains two disjoint maximal independent sets", Graph Theory Newsletter 6 (1977) 7–8.
- O. Schaudt, On disjoint maximal independent sets in graphs, Inform. Process. Lett. 115 (2015) 23–27.
https://doi.org/10.1016/j.ipl.2014.08.010
Close