在一個簡單圖G有著點集合V和邊集合E裡，一個頂點v可以支配(dominate)到與v點相鄰的邊和其端點，一條邊uv可以支配到兩端點和與u點、v點共點的相鄰邊，對圖G來說，若點集合和邊集合的子集合S ( )能夠支配到圖G所有點和邊，我們稱S為G的混合支配集(mixed dominating set，簡稱MDS)，而G的最小混合支配集的元素個數稱為G的混合支配數 。
此混合支配問題是圖論中支配問題的推廣，可以應用於電力公司需要不斷監測電力系統狀態而配置位相量測單元(phase measurement units簡稱PMUs)，為了節省成本，電力公司必須盡可能配置少量的位相量測單元來監測整個系統狀態。
本篇論文中，主要研究在區塊－仙人掌圖上探討混合支配問題，並設計其線性時間的演算法求得其混合支配集。

Let G = (V, E) be a simple graph with vertex set V and edge set E.
A subset S (S ⊆ V∪E) is a mixed dominating set if every element x ∈ (V∪E)\S is either adjacent or incident to an element of S. The mixed domination number γm of G is the minimum cardinality of a mixed dominating set of G. The mixed domination problem is to find a minimum mixed dominating set of G.
This problem can be theoretically represented as a variation of the well-known domination problem in graph theory. A practical application of the mixed domination problem is stated as follows. Electric power companies monitor the state of their electric power system by placing phase measurement units (PMUs) in the system. For economical considerations, companies have to place as few PMUs as possible and still maintain the ability of monitoring the entire system.
In this thesis, we propose a linear-time algorithm for solving mixed domination problem in block-cactus graphs.

[1] Y. Alavi, M. Behzad, L.M. Lesniak-Foster, and E.A. Nordhaus, Total matchings and total coverings of graphs, J. Graph Theory, 1(1977) 135–140.
[2] Y. Alavi, J. Liu, J. Wang, and Z. Zhang, On total covers of graphs, Discrete Math, 100 (1992) 229–233.
[3] R. B. Allan, R. C. Laskar, and S. T. Hedetniemi, A note on total domination, Discrete Math, 49 (1984) 7-13.
[4] A. A. Bertossi, Dominating sets for split and bipartite graphs, Information Processing Letters, 19 (1984) 37–40.
[5] A. A. Bertossi, Total domination in interval graphs, Information Processing Letters, 23 (1986) 131-134.
[6] K. S. Booth, J. H. Johnson, Dominating sets in chordal graphs, SIAM Journal on Computing, 11 (1982) 191–199.
[7] G. J. Chang, G. L. Nemhauser, The k-domination and k-stability problems in sun-free chordal graphs, SIAM Journal on Algebr. Discrete Methods, 5 (1984) 332–345.
[8] E. J. Cockayne, S. Goodman, and S. T. Hedetniemi, A linear algorithm for the domination number of a tree, Information Processing Letters, 4 (1975) 41–44.
[9] E. J. Cockayne, S. T. Hedetniemi, and D. J. Miller, Properties of hereditary hypergraphs and middle graphs, Canad. Math. Bull., 21 (1978) 461–468.
[10] E. J. Cockayne, R. M. Dawes, and S. T. Hedetniemi, Total domination in graphs, Networks, 10 (1980) 211-219.
[11] A. K. Dewdney, Fast turing reductions between problem in NP; chapter 4; reductions between NP-complete problems, Technical Report 71, Dept. computer Science, Univ. Western Ontario, 1981.
[12] P. Erdos and A. Meir., On total matching numbers and total covering numbers of complementary graphs, Discrete Math, 19 (1977) 229–233.
[13] M. Farber, Domination, independent domination, and duality in strongly chordal graphs, Discrete Appl. Math., 7 (1984) 115-130.
[14] M. R. Garey, D. S. Johnson, and L. Stockmeyer, Some simplifed NP-complete graph problems, Theoretical Computer Science, 1 (1976) 237–267.
[15] M. R. Garey and D. S. Johnson, Computers and intractability : A guide to the theory of NP-completeness, WH Freeman & Co, San Francisco 1979.
[16] F. Harary, A characterization of block graphs, Canadian Mathematic Bull, 6 (1982) 1–6.
[17] J. Haviland, Independent domination in regular graphs, Discrete Math., 143 (1995) 275-280.
[18] T. W. Haynes and P. J. Slater, Paired-domination and the paired-domatic number, Congr. Numer., 109 (1995) 67-72.
[19] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[20] B. L. Hartnell and S. Fitzpatrick, Paired-domination, Discuss. Math. Graph Theory, 18 (1998) 63-72.
[21] S.M. Hedetniemi, S.T. Hedetniemi, R. Laskar, A. McRae, A. Majumdar, Domination, independence and irredundance in total graphs: a brief survey, in: Y. Alavi, A. Schwenk (Eds.), in: Graph Theory, Combinatorics and Applications: Proceedings of the 7th Quadrennial International Conference on the Theory and Applications of Graphs, vol. 2, Wiley, New York, 1995, pp. 671-683.
[22] J. M. Keil, Total domination in interval graphs, Information Processing Letters, 22 (1986) 171-174.
[23] D.F. Manlove, On the algorithmic complexity of twelve covering and independence parameters of graphs, Discrete Appl. Math, 91 (1-3) (1999) 155–175.
[24] A. Majumdar, Neighborhood hypergraphs: a framework for covering and packing parameters in a graph, Ph.D. Thesis, Clemson University, Department of Mathematical Sciences, South Carolina, 1992.
[25] A. A. McRae, Generalizing NP-Completeness Proofs for Bipartite and Chordal Graphs, PH.D. Thesis, Clemson University, 1994.
[26] L. Mili, T. Baldwin, and A. Phadke, Phasor measurement placement for voltage and stability monitoring and control, in : Proc. of the EPRI-NSF Workshop on Application of Advanced Mathematics to Power System, San Francisco, CA, 1991.
[27] K. S. Natarajan and L. J. White, Optimum domination in weighted trees, Information Processing Letters, 7 (1978) 261–265.
[28] D. Rautenbach and L. Volkmann, The domatic number of block-cactus graphs, Discrete Mathematics, 187 (1998) 185–193.
[29] Yancai Zhzo, Liying Kang, Moo Young Sohn, The algorithmic complexity of mixed domination in graphs, Theoretical Computer Science 412 (2011) 2387–2392.