×

Domination in partitioned graphs with minimum degree two. (English) Zbl 1113.05077

Let \(V_1\) and \(V_2\) be a partition of the vertex set in a graph \(G\). For \(i=1,2\), let \(\gamma_i\) denote the least number of vertices needed in \(G\) to dominate \(V_i\). It is known that if \(G\) has order \(n\) and minimum degree two, then \(\gamma_1+\gamma_2\leq 2n/3\). The contribution of this paper is the complete characterization of those graphs of order \(n\) which are edge minimal with respect to satisfying the conditions of connected, minimum degree at least two, and \(\gamma_1+\gamma_2=2n/3\).

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Chartrand, G.; Lesniak, L., Graphs and Digraphs (1996), Chapman & Hall: Chapman & Hall London · Zbl 0890.05001
[2] Hartnell, B. L.; Vestergaard, P. D., Partitions and dominations in a graph, J. Combin. Math. Combin. Comput., 46, 113-128 (2003) · Zbl 1036.05039
[3] Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of Domination in Graphs (1998), Marcel Dekker: Marcel Dekker New York · Zbl 0890.05002
[4] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.; T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998. · Zbl 0883.00011
[5] Henning, M. A., Graphs with large total domination number, J. Graph Theory, 35, 1, 21-45 (2000) · Zbl 0959.05089
[6] McCuaig, W.; Shepherd, B., Domination in graphs with minimum degree two, J. Graph Theory, 13, 749-762 (1989) · Zbl 0708.05058
[7] Sanchis, L. A., Domination related to domination in graphs with minimum degree two, J. Graph Theory, 25, 139-152 (1997) · Zbl 0876.05047
[8] Seager, S. M., Partition dominations of graphs of minimum degree 2, Congress. Numer., 132, 85-91 (1998) · Zbl 0951.05079
[9] Tuza, Z.; Vestergaard, P. D., Domination in partitioned graph, Discuss. Math. Graph Theory, 22, 1, 199-210 (2002) · Zbl 1016.05057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.