×

zbMATH — the first resource for mathematics

Bibliography on domination in graphs and some basic definitions of domination parameters. (English) Zbl 0733.05076
Let G(V,E) be a graph. A subset S of the vertex set V is dominating in G if every vertex from V is contained in S or adjacent to any vertex of S. Finding a minimal dominating set of a graph G is one of the basic problems in graph theory. In the paper are listed over 30 definitions close to the domination. The main part of the paper is a bibliography concerning to problems related to dominating. The list of papers contains more than 400 titles.
Reviewer: L.Niepel

MSC:
05C99 Graph theory
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
00A15 Bibliographies for mathematics in general
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abbott, H.L.; Liu, A.C., Bounds for the covering number of a graph, Discrete math., 25, 3, 281-284, (1979) · Zbl 0393.05032
[2] Acharya, B.D., The strong domination number of a graph and related concepts, J. math. phys. sci., 14, 5, 471-475, (1980) · Zbl 0476.05065
[3] B.D. Acharya and H.B. Walikar, Bounds on the size of a graph having unique minimum dominating set, manuscript, undated.
[4] B.D. Acharya and H.B. Walikar, Indominable graphs cannot be characterized by a finite family of forbidden subgraphs, manuscript, undated. · Zbl 0476.05068
[5] Acharya, B.D.; Walikar, H.B., On graphs having unique minimum dominating sets, Graph theory newsletter, 8, 5, 1, (1979) · Zbl 0401.05056
[6] Ahrens, W., Mathematishe unterhaltungen und spiele, (1901), Leipzig · JFM 31.0220.02
[7] Aigner, M., Some theorems on coverings, Studia sci. math. hungar., 5, 303-315, (1970) · Zbl 0244.05110
[8] Allan, R.B.; Laskar, R., On domination and independent domination numbers of a graph, Discrete math., 23, 73-76, (1978) · Zbl 0416.05064
[9] Allan, R.B.; Laskar, R., On domination and some related topics in graph theory, (), 43-58
[10] Allan, R.B.; Laskar, R.; Hedetniemi, S.T., A note on total domination, Discrete math., 49, 7-13, (1984) · Zbl 0576.05028
[11] Anciaux-Mundeleer, M.; Hansen, P., On kernels in strongly connected graphs, Networks, 7, 3, 263-266, (1977) · Zbl 0364.05028
[12] Andreas, B., Graphs with unique maximal clumpings, J. graph theory, 2, 1, 19-24, (1978) · Zbl 0377.05036
[13] Arnautov, V.I., Estimation of the exterior stability number of a graph by means of the minimal degree of the vertices, Prikl. mat. i programmirovanie vyp., Prikl. mat. i programmirovanie vyp., 11, 126-8, (1974), (in Russian)
[14] Arnautov, V.I., The exterior stability number of a graph, Diskret. analiz, 20, 3-8, (1972)
[15] Arnborg, S., Efficient algorithms for combinatorial problems on graphs with bounded decomposability — a survey, Bit, 25, 2-23, (1985) · Zbl 0573.68018
[16] Arnborg, S.; Proskurowski, A., Linear time algorithms for NP-hard problems restricted to partial K-trees, Discrete appl. math., 23, 11-24, (1989) · Zbl 0666.68067
[17] P. Ash, Two sufficient conditions for the existence of hamilton cycles in bipartite graphs, undated manuscript. · Zbl 0534.05041
[18] Ash, P.; Jackson, B., Dominating cycles in bipartite graphs, (), 81-87
[19] Atallah, J.; Kosaraju, S.R., An efficient algorithm for maxdominance, with applications, () · Zbl 0664.68070
[20] Baker, B.S., Approximation algorithms for NP-complete problems on planar graphs, 24th annual symposium on the foundations of computer science, 265-273, (1983)
[21] Balas, E.; Padberg, M.W., On the set covering problem, Oper. res., 20, 1152-1161, (1972) · Zbl 0254.90035
[22] Ball, W.R., Mathematical recreations and problems, (1892), London · JFM 24.0199.01
[23] Bange, D.W.; Barkauskas, A.E.; Host, L.H.; Slater, P.J., Efficient near-domination of grid graphs, Congr. numer., 58, 83-92, (1987)
[24] Bange, D.W.; Barkauskas, A.E.; Slater, P.J., A constructive characterization of trees with two disjoint minimum dominating sets, (), 101-112
[25] Bange, D.W.; Barkauskas, A.E.; Slater, P.J., Disjoint dominating sets in trees, () · Zbl 0664.05027
[26] Bange, D.W.; Barkauskas, A.E.; Slater, P.J., Efficient dominating sets in graphs, (), 189-199 · Zbl 0664.05027
[27] Bar-Yehuda, R.; Vishkin, U., Complexity of finding k-path-free dominating sets in graphs, Inform. process. lett., 14, 228-232, (1982) · Zbl 0491.68043
[28] Barefoot, C.; Harary, F.; Jones, K.F., What is the difference between α and α′ of a cubic graph?, (1988), manuscript
[29] Bauer, D.; Harary, F.; Neiminen, J.; Suffel, C.L., Domination alteration sets in graphs, Discrete math., 47, 2-3, 153-161, (1983) · Zbl 0524.05040
[30] Benedetti, M.A.; Mason, F.M., On the characterization of “domistable” graphs (Italian; English summary), Ann. univ. ferrara sez. VII (NS), 27, 1-11, (1981), MR84b:0566
[31] Benzaken, C.; Hammer, P.L., Linear separation of dominating sets in graphs, (), 1-10, Ann. Discrete Math. · Zbl 0375.05043
[32] C. Benzaken and P.L. Hammer, On some open problems regarding dominating sets in graphs, manuscript. · Zbl 0375.05043
[33] Berge, C., Graphs and hypergraphs, (), 303-324
[34] Berge, C., Nouvelles extensions du noyau d’un graphe et ses applications en theorie des jeux, Publ. econometriques, 6, 6-11, (1973) · Zbl 0257.05113
[35] Berge, C., Theory of graphs and its applications, (), 40-51
[36] Bern, M.W.; Lawler, E.L.; Wong, A.L., Linear-time computation of optimal subgraphs of decomposable graphs, J. algorithms, 8, 216-235, (1987) · Zbl 0618.68058
[37] Bern, M.W.; Lawler, E.L.; Wong, A.L., Why certain subgraph computations require only linear time, 26th annual IEEE symposium on the foundations of computer science, 117-125, (1985), Portland, OR
[38] Bertolazzi, P.; Sassano, A., A class of polynomially solvable set covering problems, SIAM, J. discrete math., 1, 3, 306-316, (1988) · Zbl 0678.05048
[39] Bertossi, A.A., Dominating sets for split and bipartite graphs, Inform. process. lett., 19, 37-40, (1984) · Zbl 0539.68058
[40] Bertossi, A.A., Total domination in interval graphs, Inform. process. lett., 23, 3, 131-134, (1986) · Zbl 0604.05032
[41] Bertossi, A.A.; Gori, A., Total domination and irredundance in weighted interval graphs, SIAM J. discrete math., 1, 3, 317-327, (1988) · Zbl 0648.05041
[42] Beyer, T.; Proskurowski, A.; Hedetniemi, S.; Mitchell, S., Independent domination in trees, (), 321-328 · Zbl 0417.05020
[43] Billionnet, A., Bornes inférieures et supérieures du poids et du cardinal de tout ensemble stable maximal d’un graphe (upper and lower bounds for the weight and c ardinality of every maximal stable set of a graph), Rev. roumaine math. pures appl., 29, 8, 641-656, (1984) · Zbl 0554.05040
[44] Blank, M.M., An estimate of the external stability number of a graph without suspenced vertices (in Russian), Prikl. mat. i programmirovanie vyp., 10, 149, 3-11, (1973)
[45] Bollobás, B.; Cockayne, E.J., Graph theoretic parameters concerning domination, independence and irredundance, J. graph theory, 3, 3, 241-249, (1979) · Zbl 0418.05049
[46] Bollobás, B.; Cockayne, E.J., On the domination number and minimum degree of a graph, () · Zbl 0539.05056
[47] Bollobás, B.; Cockayne, E.J., On the irredundance number and maximum degree of a graph, Discrete math., 49, 2, 197-199, (1984) · Zbl 0539.05056
[48] Bollobás, B.; Cockayne, E.J.; Mynhardt, C.M., On generalised minimal domination parameters for paths, Discrete math., 86, 89-97, (1990), (this Vol.) · Zbl 0744.05056
[49] Bollobás, B.; Thomason, A.G., Uniquely partitionable graphs, J. London math. soc., 2, 3, 403-410, (1977) · Zbl 0377.05038
[50] Bondy, J.A.; Fan, Geng-hua, A sufficient condition for dominating cycles, Discrete math., 76, 205-208, (1987) · Zbl 0634.05045
[51] Bonuccelli, M.A., Dominating sets and domatic number of circular arc graphs, Discrete appl. math., 12, 203-213, (1985) · Zbl 0579.05051
[52] Booth, K.S.; Johnson, J.H., Dominating sets in chordal graphs, SIAM J. comput., 11, 4, 191-199, (1982) · Zbl 0485.05055
[53] Borowiecki, M., On graphs with minimaximal kernels, ^∗, 17 ser. stud. i materialy, 13, 3-7, (1977) · Zbl 0398.05064
[54] Borowiecki, M., On the stable and absorbent sets of hypergraphs, (), 33-39, (German) · Zbl 0435.05034
[55] Brandstädt, A., Classes of bipartite graphs related to chordal graphs and domination of one colour class by the other, ()
[56] Brandstädt, A.; Kratsch, D., On domination problems for permutation and other graphs, Theoret. comput. sci., 54, 181-198, (1987) · Zbl 0641.68100
[57] Brandstädt, A.; Kratsch, D., On the restriction of some NP-complete graph problems to permutation graphs, (), 53-62
[58] Brigham, R.C.; Chinn, P.Z.; Dutton, R.D., Vertex domination-critical graphs, Networks, 18, 3, 173-179, (1988) · Zbl 0658.05042
[59] Brigham, R.C.; Dutton, R.D., Factor domination in graphs, Discrete math., 86, 127-136, (1990), (this Vol.) · Zbl 0722.05049
[60] Brigham, R.C.; Dutton, R.D., Neighborhood numbers, new invariants of undirected graphs, Congr. numer., 53, 121-132, (1986) · Zbl 0624.05059
[61] Caro, Y.; Roditty, Y., On the vertex-independence number and star decomposition of graphs, Ars combin., 20, 167-180, (1985) · Zbl 0623.05031
[62] Cazanescu, V.E.; Rudeanu, S., Independent sets and kernels in graphs and hypergraphs, (), 37-66 · Zbl 0412.05055
[63] Chang, G.J., k-domination and graph covering problems, ()
[64] Chang, G.J., Labelling algorithms for domination problems in sunfree chordal graphs, Discrete appl. math., 22, 1, 21-34, (1988)
[65] Chang, G.J., Total domination in block graphs, Oper. res. lett., 8, 1, 53-57, (1989) · Zbl 0678.90086
[66] Chang, G.J.; Nemhauser, G.L., Covering, packing and generalized perfection, SIAM J. algebraic discrete methods, 6, 1, 109-132, (1985) · Zbl 0556.05055
[67] Chang, G.J.; Nemhauser, G.L., R-domination of block graphs, Oper. res. lett., 1, 6, 214-218, (1982) · Zbl 0498.90023
[68] Chang, G.J.; Nemhauser, G.L., The k-domination and k-stability on Sun-free chordal graphs, SIAM J. algebraic discrete methods, 5, 3, 332-345, (1984) · Zbl 0576.05054
[69] Chang, G.J.; Nemhauser, G.L., The k-domination and k-stability problems on graphs, () · Zbl 0576.05054
[70] Chao, Chong-Yun, On the kernels of graphs, IBM research rept. RC-685, (1962)
[71] Cheston, G.A.; Fricke, G.; Hedetniemi, S.T.; Pokrass, D., On the computational complexity of upper fractional domination, Discrete appl. math., 27, 195-207, (1990) · Zbl 0717.05068
[72] Cheston, G.A.; Hare, E.O.; Hedetniemi, S.T.; Laskar, R., Simplicial graphs, Congr. numer., 67, 105-113, (1988) · Zbl 0668.05041
[73] Chung, F.R.K.; Graham, R.L.; Cockayne, E.J.; Miller, D.J., On the minimum dominating pair number of a class of graphs, Caribbean J. math., 1, 2, 73-76, (1982) · Zbl 0524.05038
[74] Chvátal, V.; Cook, W., The discipline number of a graph, Discrete math., 86, 191-198, (1990), (this Vol.) · Zbl 0747.05087
[75] Chvátal, V.; Lovasz, L., Every directed graph has a semikernel, () · Zbl 0297.05116
[76] Clark, B.N.; Colbourn, C.J.; Erdős, P., A conjecture on dominating cycles, Congr. numer., 47, 189-197, (1985)
[77] Clark, B.N.; Colbourn, C.J.; Johnson, D.S., Unit disk graphs, Discrete math., 86, 165-177, (1990), (this Vol.) · Zbl 0739.05079
[78] Cockayne, E.J., Chessboard domination problems, Discrete math., 86, 13-20, (1990), (this Vol.) · Zbl 0818.05057
[79] Cockayne, E.J., Domination in undirected graphs — a survey, (), 141-147 · Zbl 0384.05052
[80] Cockayne, E.J.; Dawes, R.M.; Hedetniemi, S.T., Total domination in graphs, Networks, 10, 211-219, (1980) · Zbl 0447.05039
[81] Cockayne, E.J.; Favaron, O.; Payan, C.; Thomason, A., Contributions to the theory of domination, independence and irredundance in graphs, Discrete math., 33, 249-258, (1981) · Zbl 0471.05051
[82] Cockayne, E.J.; Gamble, B.; Shepherd, B., An upper bound for the k-domination number of a graph, J. graph theory, 9, 533-534, (1985) · Zbl 0664.05053
[83] Cockayne, E.J.; Gamble, B.; Shepherd, B., Domination parameters for the bishops graph, Discrete math., 58, 221-227, (1986) · Zbl 0602.05040
[84] Cockayne, E.J.; Goodman, S.E.; Hedetniemi, S.T., A linear algorithm for the domination number of a tree, Inform. process. lett., 4, 41-44, (1975) · Zbl 0311.68024
[85] Cockayne, E.J.; Hare, E.O.; Hedetniemi, S.T.; Wimer, T.V., Bounds for the domination number of grid graphs, Congr. numer., 47, 217-228, (1985)
[86] Cockayne, E.J.; Hedetniemi, S.T., Disjoint independent dominating sets in graphs, Discrete math., 15, 213-222, (1976) · Zbl 0364.05035
[87] Cockayne, E.J.; Hedetniemi, S.T., Independence graphs, (), 471-491 · Zbl 0305.05114
[88] Cockayne, E.J.; Hedetniemi, S.T., On the diagonal queens domination problem, J. combin. theory ser. A, 42, 137-139, (1986) · Zbl 0589.05014
[89] Cockayne, E.J.; Hedetniemi, S.T., Optimal domination in graphs, IEEE trans. circuits and systems, 22, 11, 855-857, (1975)
[90] Cockayne, E.J.; Hedetniemi, S.T., Towards a theory of domination in graphs, Networks, 7, 247-261, (1977) · Zbl 0384.05051
[91] Cockayne, E.J.; Hedetniemi, S.T.; Miller, D.J., Properties of hereditary hypergraphs and middle graphs, Canad. math. bull, 21, 4, 461-468, (1978) · Zbl 0393.05044
[92] Cockayne, E.J.; Hedetniemi, S.T.; Slater, P.J., Matchings and transversals in hypergraphs, domination and independence in trees, J. combin. theory, 26, 1, 78-80, (1979) · Zbl 0414.05036
[93] Cockayne, E.J.; Ko, C.W.; Shepherd, F.B., Inequalities concerning dominating sets in graphs, ()
[94] Cockayne, E.J.; Mynhardt, C.M., On the product of k-minimal domination numbers of a graph and its complement, (), 16 · Zbl 0745.05055
[95] E.J. Cockayne and C.M. Mynhardt, On the product of upper irredundance numbers of a graph and its complement, Discrete Math., to appear. · Zbl 0672.05049
[96] Cockayne, E.J.; Mynhardt, C.M., The sequence of upper and lower domination, independence and irredundance numbers of a graph, (1988), manuscript · Zbl 0788.05055
[97] Cockayne, E.J.; Roberts, F.D.K., Computation of dominating partitions, Infor., 15, 94-106, (1977) · Zbl 0352.90038
[98] Cockayne, E.J.; Spencer, P.H., On the independent queens covering problem, Graphs combin., 4, 2, 101-110, (1988) · Zbl 0709.05013
[99] Cockayne, E.J.; Thomason, A.G., Contributions to the theory of domination, independence and irredundance in graphs, () · Zbl 0471.05051
[100] Colbourn, C.J.; Keil, J.M.; Stewart, L.K., Finding minimum dominating cycles in permutation graphs, Oper. res. lett., 4, 1, 13-17, (1985) · Zbl 0569.90091
[101] Colbourn, C.J.; Slater, P.J.; Stewart, L.K., Locating-dominating sets in series-parallel networks, Proceedings 16th Annual Conference on Numerical Math. and Computing, Winnipeg, 1986, Congr. numer., 56, 135-162, (1987) · Zbl 0646.05065
[102] Colbourn, C.J.; Stewart, L.K., Dominating cycles in series-parallel graphs, Ars combin., 19, 107-112, (1985), A · Zbl 0568.05035
[103] Colbourn, C.J.; Stewart, L.K., Permutation graphs: connected domination and Steiner trees, Discrete math., 86, 179-189, (1990), (this Vol.) · Zbl 0744.05059
[104] Corneil, D.G.; Keil, J.M., A dynamic programming approach to the dominating set problem on k-trees, SIAM J. algebraic discrete methods, 8, 535-543, (1987) · Zbl 0635.05040
[105] Corneil, D.G.; Perl, Y., Clustering and domination in perfect graphs, Discrete appl. math., 9, 27-39, (1984) · Zbl 0581.05053
[106] Corneil, D.G.; Perl, Y.; Stewart, L., Cographs: recognition, application and algorithms, Congr. numer., 43, 249-258, (1984)
[107] Corneil, D.G.; Perl, Y.; Burlingham, L.Stewart, A linear recognition algorithm for cographs, SIAM J. comput., 14, 4, 926-934, (1985) · Zbl 0575.68065
[108] Corneil, D.G.; Stewart, L.K., Dominating sets in perfect graphs, Discrete math., 86, 145-164, (1990), (this Vol.) · Zbl 0746.05066
[109] Cozzens, M.B.; Kelleher, L.L., Dominating cliques in graphs, Discrete math., 86, 101-106, (1990), (this Vol.) · Zbl 0729.05043
[110] Croitoru, C., On stables in graphs, (), 55-60, (cluj-Napoca, 1978)
[111] Croitoru, C.; Suditu, E., Perfect stables in graphs, Inform. process. lett., 17, 1, 53-56, (1983) · Zbl 0509.68038
[112] D’Atri, A.; Moscarini, M., Cross graphs, Steiner trees and connected domination, () · Zbl 0649.68067
[113] Damaschke, P., Irredundance number versus domination number, Forschungsergebnisse der FSU jena, (1988), N/88/5 · Zbl 0753.05068
[114] Daykin, D.E.; Ng, C.P., Algorithms for generalized stability numbers of tree graphs, J. austral. math. soc., 6, 89-100, (1966) · Zbl 0135.42106
[115] De Jaenisch, C.F., ()
[116] Dewdney, A.K., Fast Turing reductions between problems in NP; chapter 4: reductions between NP-complete problems, ()
[117] Domke, G.S., Variations of colorings, coverings and packings of graphs, ()
[118] Domke, G.S.; Hedetniemi, S.T.; Laskar, R., Fractional packings, coverings and irredundance in graphs, Congr. numer., 66, 227-238, (1988) · Zbl 0722.05052
[119] Domke, G.S.; Hedetniemi, S.T.; Laskar, R.; Allan, R.B., Generalized packings and coverings of graphs, Congr. numer., 62, 259-270, (1988)
[120] Domke, G.S.; Hedetniemi, S.T.; Laskar, R.; Fricke, G., Proceedings Sixth International Conference on the Theory and Applications of Graphs, Kalamazoo, MI, Relationships between integer and fractional parameters of graphs, (1988), to appear
[121] Duchet, P.; Meyniel, H., On Hadwiger’s number and the stability number, Ann. discrete math., 13, 71-74, (1982) · Zbl 0522.05060
[122] Edmonds, J.; Fulkerson, D.R., Bottleneck extrema, J. combin. theory, 8, 299-306, (1970) · Zbl 0218.05006
[123] Egiazaryan, E.V., The domination number of graphs (russian, Armenian summary), (), 67-74
[124] Ene, D., Algorithms for the detection of the minimal externally stable sets in a graph, and applications, Stud. cerc. mat., 23, 1009-1016, (1971) · Zbl 0237.05119
[125] Farber, M., Applications of linear programming duality to problems involving independence and domination, ()
[126] Farber, M., Characterizations of strongly chordal graphs, Discrete math., 43, 173-189, (1983) · Zbl 0514.05048
[127] Farber, M., Domination and duality in weighted trees, Congr. numer., 33, 3-13, (1981)
[128] Farber, M., Domination, independent domination, and duality in strongly chordal graphs, Discrete appl. math., 7, 115-130, (1984) · Zbl 0531.05045
[129] Farber, M., Independent domination in chordal graphs, Oper. res. lett., 1, 4, 134-138, (1982) · Zbl 0495.05053
[130] Farber, M.; Keil, J.M., Domination in permutation graphs, J. algorithms, 6, 3, 309-321, (1985) · Zbl 0598.05056
[131] Farley, A.; Hedetniemi, S.; Proskurowski, A., Partitioning trees: matching, domination and maximum diameter, Internat. J. comput. info. sciences, 10, 55-61, (1981) · Zbl 0464.68068
[132] Farley, A.M.; Proskurowski, A., Computing the maximum order of an open irredundant set in a tree, Congr. numer., 41, 219-228, (1984)
[133] Farley, A.M.; Schacham, N., Senders in broadcast networks: open irredundancy in graphs, Congr. numer., 38, 47-57, (1983)
[134] Favaron, O., On a conjecture of fink and Jacobson concerning k-domination and k-dependence, J. combin. theory ser. B, 39, 1, 101-102, (1985) · Zbl 0583.05049
[135] Favaron, O., A note on the open irredundance in a graph, Congr. numer., 66, 316-318, (1988)
[136] Favaron, O., Stability, domination and irredundance in a graph, J. graph theory, 10, 4, 429-438, (1986) · Zbl 0612.05056
[137] Fellows, M.R., Applications of some domination-related categories of graphs, (1986), manuscript
[138] Fellows, M.R., Encoding graphs in graphs, ()
[139] Fink, J.F.; Jacobson, M.S., n-domination in graphs, (), 283-300, Kalamazoo, MI, 1984
[140] Fink, J.F.; Jacobson, M.S., On n-domination, n-dependence and forbidden subgraphs, (), 301-311, Kalamazoo, MI, 1984
[141] Fink, J.F.; Jacobson, M.S.; Kinch, L.F.; Roberts, J., On graphs having domination number half their order, Period. math. hungar., 16, 4, 287-293, (1985) · Zbl 0602.05043
[142] Fink, J.F.; Jacobson, M.S.; Kinch, L.F.; Roberts, J., The bondage number of a graph, Discrete math., 86, 47-57, (1990), (this Vol.) · Zbl 0745.05056
[143] Fraisse, P., Dominating cycles and paths, Notices amer. math. soc., 5, 3, 231, (1984)
[144] Frank, A., Kernel systems of directed graphs, Acta sci. math. (Szeged), 41, 1-2, 63-76, (1979) · Zbl 0425.05028
[145] Fu, Y., Dominating set and converse dominating set of a directed graph, Amer. math. monthly, 75, 861-863, (1968) · Zbl 0174.55203
[146] Galeana-Sanchez, H., A theorem about a conjecture of H. meyneil on kernel-perfect graphs, Discrete math., 59, 35-41, (1986) · Zbl 0602.05032
[147] Galeana-Sanchez, H.; Neumann-Lara, V., On kernels and semikernels of digraphs, Discrete math., 48, 67-76, (1984) · Zbl 0529.05024
[148] Gamble, B.; Shepherd, B.; Cockayne, E.J., Domination of chessboards by queens on a column, Ars combin., 19, 105-118, (1985) · Zbl 0583.05005
[149] Garey, M.R.; Johnson, D.S., Computers and intractability, () · Zbl 0369.90053
[150] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[151] Grinstead, C.M.; Hahne, B.; Van Stone, D., On the queen domination problem, Discrete math., 86, 21-26, (1990), (this Vol.) · Zbl 0742.05021
[152] Grinstead, D.L.; Slater, P.J., A recurrence template for several domination-related parameters for series-parallel graphs, (1988), manuscript
[153] Grinstead, D.L.; Slater, P.J., Fractional domination and fractional packing in graphs, Congr. numer., 71, 153-172, (1990) · Zbl 0691.05043
[154] Grinstead, D.L.; Slater, P.J., On minimum dominating sets with minimum intersection, Discrete math., 86, 239-254, (1990), (this Vol.) · Zbl 0745.05057
[155] Grinstead, D.L.; Slater, P.J., On the minimum intersection of minimum dominating sets in series-parallel graphs, Proceedings sixth international conference on the theory and applications of graphs, kalamzoo, MI, (1988), to appear · Zbl 0841.05049
[156] Gupta, R.P., Independence and covering numbers of line graphs and total graphs, (), 61-62 · Zbl 0193.24203
[157] Gurevich, Y.; Stockmeyer, L.; Vishkin, U., Solving NP-hard problems on graphs that are almost trees and an application to facility location problems, IBM research rept. RC9348, (1982), Yorktown Heights, NY
[158] Hammer, P.L.; Hujter, M., Graphs whose minimal dominating sets are independent, (1984), manuscript
[159] Hansen, P., Bornes et algorithmes pour LES stables d’un graphs, (), 39-53, (Proc. Colloq., Cerisy, 1980) (French)
[160] Harary, F.; Livingston, M., Characterization of trees with equal domination and independent domination numbers, Congr. numer., 55, 121-150, (1986) · Zbl 0647.05020
[161] Hare, E.O.; Hare, W.R.; Hedetniemi, S.T., Algorithms for computing the domination number of K × N complete grid graphs, Congr. numer., 55, 81-92, (1986) · Zbl 0637.68077
[162] Hare, E.O.; Hedetniemi, S.T., A linear algorithm for computing the Knight’s domination number of a K × N chessboard, Congr. numer., 59, 115-130, (1987) · Zbl 0652.05015
[163] Hartnell, B.L., Some problems on minimum dominating sets, (), 317-320 · Zbl 0408.05042
[164] Hedetniemi, S.M., Optimum domination in unicyclic graphs, ()
[165] Hedetniemi, S.M.; Hedetniemi, S.T., Dominating partitions of graphs, (1981), manuscipt
[166] Hedetniemi, S.M.; Hedetniemi, S.T.; Laskar, R., Domination in trees: models and algorithms, (), 423-442, Kalamazoo, MI, 1984
[167] Hedetniemi, S.M.; Hedetniemi, S.T.; Wimer, T.V., Linear time resource allocation algorithms for trees, Southeastern conference on combinatorics, graph theory and computing, (1987), Boca Raton, FL
[168] Hedetniemi, S.T., A MAX-MIN relationship between matchings and domination in graphs, Congr. numer., 40, 23-34, (1983) · Zbl 0547.05051
[169] Hedetniemi, S.T.; Laskar, R., A bipartite theory of graphs: I, Congr. numer., 55, 5-14, (1986)
[170] Hedetniemi, S.T.; Laskar, R., A bipartile theory of graphs: II, Prof. 250th anniversary cont. on graph theory, Congr. numer., 64, 137-146, (1988), (Ft. Wayne Ind., 1986)
[171] Hedetniemi, S.T.; Laskar, R., Connected domination in graphs, (), 209-218 · Zbl 0548.05055
[172] Hedetniemi, S.T.; Laskar, R., Recent results and open problems in domination theory, (), 205-218 · Zbl 0664.05026
[173] Hedetniemi, S.T.; Laskar, R.; Pfaff, J., A linear algorithm for finding a minimum dominating set in a cactus, Discrete appl. math., 13, 287-292, (1986) · Zbl 0596.05051
[174] Hedetniemi, S.T.; Laskar, R.; Pfaff, J., Irredundance in graphs: a survey, Congr. numer., 48, 183-193, (1985) · Zbl 0647.05060
[175] Hochbaum, D.S., Easy solutions for the k-center problem or the dominating set problem on random graphs, (1982), manuscipt
[176] Hochbaum, D.S., On the fractional solution to the set covering problem, SIAM J. algebraic discrete methods, 4, 2, 221-222, (1983) · Zbl 0518.90055
[177] Hochbaum, D.S.; Shmoys, D.B., A best possible heuristic for the k-center problem, Math. oper. res., 10, 2, 180-184, (1985) · Zbl 0565.90015
[178] Holyer, I.J.; Cockayne, E.J., On the sum of cardinalities of extrenum maximal independent sets, Discrete math., 26, 3, 243-246, (1979) · Zbl 0404.05033
[179] Hsu, Wen-Lian, On the domination numbers of trees, () · Zbl 0487.90049
[180] Hsu, Wen-Lian, On the maximum coverage problem on trees, () · Zbl 0559.05049
[181] Hsu, Wen-Lian, The distance-domination number of trees, Oper. res. lett., 1, 3, 96-100, (1982) · Zbl 0487.90049
[182] Hujter, M., The irredundance and domination numbers are equal in domistable graphs, (1984), manuscript
[183] Jacobson, M.S.; Kinch, L.F., On the domination of the products of graphs II: trees, J. graph theory, 10, 1, 97-106, (1986) · Zbl 0584.05053
[184] Jacobson, M.S.; Kinch, L.F., On the domination number of products of graphs: I, Ars. combin., 18, 33-44, (1984) · Zbl 0566.05050
[185] Jacobson, M.S.; Peters, K., Chordal graphs and upper irredundance, upper domination and independence, Discrete math., 86, 59-69, (1990), (this Vol.) · Zbl 0744.05063
[186] Jaeger, F.; Payan, C., Relations du type Nordhaus-Gaddum pour le nombre d’absorption d’un graphe simple, C. R. acad. sci. Paris, 274, 728-730, (1972) · Zbl 0226.05121
[187] Johnson, D.S., The NP-completeness column: an ongoing guide, J. algorithms part I, J. algorithms part II, 6, 291-305, (1985) · Zbl 0588.68020
[188] Johnson, T.W.; Slater, P.J., Maximum independent, minimally c-redundant sets in graphs, Congr. numer., 74, 193-211, (1990) · Zbl 0702.05075
[189] Kalbfleisch, J.G.; Stanton, R.G.; Horton, J.D., On covering sets and error-correcting codes, J. combin. theory ser. A, 11, 233-250, (1971) · Zbl 0181.22401
[190] Kariv, O.; Hakimi, S.L., An algorithmic approach to network location problems I: the p-centers, SIAM J. appl. math., 37, 513-538, (1979) · Zbl 0432.90074
[191] Kariv, O.; Hakimi, S.L., An algorithmic approach to network location problems II: the p-medians, SIAM J. appl. math., 37, 539-560, (1979) · Zbl 0432.90075
[192] Karp, R.M., Reducibility among combinatorial problems, (), 85-103 · Zbl 0366.68041
[193] Keil, J.M., Total domination in interval graphs, Inform. process. lett., 22, 171-174, (1986) · Zbl 0595.05063
[194] J.M. Keil and D. Schaefer, An optimal algorithm for finding dominating cycles in circular-arc graphs, Discrete Appl. Math., to appear. · Zbl 0753.05063
[195] Kelleher, L.L., Domination in graphs and its application to social network theory, ()
[196] Kikuno, T.; Yoshida, N.; Kakuda, Y., A linear algorithm for the domination number of a series-parallel graph, Discrete appl. math., 5, 299-311, (1983) · Zbl 0507.05060
[197] Kikuno, T.; Yoshida, N.; Kakuda, Y., Dominating set in planar graphs, Inst. electronics and comm. eng. Japan, 21-30, (1979)
[198] Kikuno, T.; Yoshida, N.; Kakuda, Y., The NP-completeness of the dominating set problem in cubic planar graphs, Trans. IECE Japan E63, 6, 443-444, (1980)
[199] Kleitman, D.J.; West, D.B., Spanning trees with many leaves, manuscript, Fourth SIAM conference on discrete mathematics, San Francisco, CA, June 13-16, 1988, (1988), presented at the
[200] Koch, E.; Perles, M.A., Covering efficiency of trees and k-trees, Congr. numer., 18, 391-420, (1976) · Zbl 0344.05101
[201] König, D., Theorie der endlichen und unendlichen graphen, (1950), Chelsea New York · Zbl 0040.10303
[202] Kratochvil, J.; Krivanek, M., On the computational complexity of codes in graphs, (1987), manuscipt
[203] Kratsch, D., A linear time algorithm for the minimum dominating clique problem on strongly chordal graphs, Forschungsergebnisse der FSU jena, (1987), N/87/29 · Zbl 0641.68099
[204] Kratsch, D., Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs, Discrete math., 86, 225-238, (1990), (this Vol.) · Zbl 0729.05046
[205] Krishnamoorthy, M.S.; Murthy, K., On the total dominating set problem, Congr. numer., 54, 265-278, (1986) · Zbl 0645.05062
[206] Laskar, R.; Peters, K., Connected domination of complementary graphs, ()
[207] Laskar, R.; Peters, K., Vertex and edge domination parameters in graphs, Congr. numer., 48, 291-305, (1985)
[208] Laskar, R.; Pfaff, J., Domination and irredundance in graphs, () · Zbl 0647.05060
[209] Laskar, R.; Pfaff, J., Domination and irredundance in split graphs, () · Zbl 0647.05060
[210] Laskar, R.; Pfaff, J.; Hedetniemi, S.M.; Hedetniemi, S.T., On the algorithmic complexity of total domination, SIAM J. algebraic discrete methods, 5, 420-425, (1984) · Zbl 0576.68056
[211] Laskar, R.; Walikar, H.B., On domination related concepts in graph theory (Calcutta, 1980), (), 308-320
[212] Lawler, E.L.; Slater, P.J., A linear time algorithm for finding an optimal dominating subforest of a tree, (), 501-506, Kalamazoo, MI, 1984
[213] Lesniak-Foster, L.; Williamson, J.E., On spanning and dominating circuits in graphs, Canad. bull. math., 20, 2, 215-220, (1977) · Zbl 0357.05060
[214] Liu, C.L., Introduction to combinatorial mathematics, (1968), McGraw-Hill New York · Zbl 0188.03801
[215] Loukakis, E., Two algorithms for determining a minimum independent dominating set, Internat. J. comput. math., 15, 3-4, 213-229, (1984) · Zbl 0535.68031
[216] Loukakis, E., Two algorithms for determining a minimum independent dominating set, Internat. J. comput. math., 15, 3-4, 213-229, (1984) · Zbl 0535.68031
[217] Maffray, T., On kernels in i-triangulated graphs, Discrete math., 61, 247-251, (1986) · Zbl 0617.05029
[218] Maghout, K., Sur la determination des nombres de stabilite et du nombre chromatique d’un graphe, C. R. acad. sci. Paris, 248, 3522-3523, (1959) · Zbl 0088.15601
[219] Marchioro, M.; Morgana, A., Structure and recognition of domishold graphs, Discrete math., 50, 2-3, 239-251, (1984) · Zbl 0611.05051
[220] Marcu, D., A new upper bound for the domination number of a graph, Quart. J. math. Oxford ser., 36, 2, 221-223, (1985) · Zbl 0564.05051
[221] Marcu, D., Generalized kernels with considerations to the tournament digraphs, Mathematica (cluj), 24, 1-2, 57-63, (1982), (47) · Zbl 0508.05039
[222] Marcu, D., On the existence of a kernel in a strong connected diagraph (Romanian summary), Bul. inst. politehn. lasi sect. I, 25, 29, 35-37, (1979), 1-2
[223] Marcu, D., Some remarks concerning the kernels of a strong connected diagraph, An. stiint. univ. “al. l. cuza” lasi sect. I a math. (N.S.), 26, 2, 417-418, (1980)
[224] McAvaney, K.L., The number and stability indices of cn-trees, (), 142-148 · Zbl 0344.05129
[225] McFall, J.D.; Nowakowski, R., Strong independence in graphs, Congr. numer., 29, 639-656, (1980)
[226] McHugh, J.; Perl, Y., Best location of service centers in a tree-like network under budget constraints, Discrete math., 86, 199-214, (1990), (this Vol.) · Zbl 0718.90053
[227] Megiddo, N.; Zemel, E.; Louis Hakimi, S., The maximum coverage location problem, SIAM J. algebraic discrete methods, 4, 2, 253-261, (1983) · Zbl 0514.90019
[228] Meir, A.; Moon, J.W., Packing and covering constants for certain families of trees, J. graph theory, 1, 2, 157-174, (1977) · Zbl 0391.05018
[229] Meir, A.; Moon, J.W., Packing and covering constants for certain families of trees: II, Trans. amer. soc., 233, 167-178, (1977) · Zbl 0391.05019
[230] Meir, A.; Moon, J.W., Packing and covering constants for recursive trees, (), 403-411 · Zbl 0371.05004
[231] Meir, A.; Moon, J.W., Relations between packing and covering numbers of a tree, Pacific J. math., 61, 225-233, (1975) · Zbl 0315.05102
[232] Mitchell, S.L., Linear algorithms on trees and maximal outerplanar graphs: design, complexity analysis and data structures study, ()
[233] Mitchell, S.L.; Cockayne, E.J.; Hedetniemi, S.T., Linear algorithms on recursive representations of trees, J. comput. system sci., 18, 76-85, (1979) · Zbl 0398.68008
[234] Mitchell, S.L.; Hedetniemi, S.T., Edge domination in trees, (), 489-509
[235] Mitchell, S.; Hedetniemi, S.; Goodman, S., Some linear algorithms on trees, (), 467-483 · Zbl 0353.05032
[236] Müller, H., The NP-completeness of Hamiltonian circuit for chordal bipartite graphs, Forschungsergebnisse der FSU jena, (1987), N/87/36 · Zbl 0641.68098
[237] Müller, H.; Brandstädt, A., The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs, Theoret. comput. sci., 53, 257-265, (1987) · Zbl 0638.68062
[238] Mynhardt, C.M., On a Ramsey type problem for independent domination parameter of graphs, () · Zbl 0760.05068
[239] Mynhardt, C.M., On the difference between the domination and independent domination numbers of cubic graphs, preprint, (1988)
[240] Mynhardt, C.M.; Cockayne, E.J., k-minimal domination numbers of cycles, Ars combin., 23-A, 195-206, (1987) · Zbl 0667.05053
[241] Nash-Williams, C.St.J.A., Edge-disjoint Hamiltonian circuits in graphs with vertices of large degree, (), 157-183, papers presented to Richard Rado · Zbl 0096.38003
[242] Natarajan, K.S.; White, L.J., Optimum domination in weighted trees, Inform. process. lett., 7, 261-265, (1978) · Zbl 0391.05046
[243] Neeralagi, P.S., Complete domination and neighbourhood numbers of a graph, manuscript, (1987)
[244] Neeralagi, P.S., Strong, weak edge domination in a graph, manuscript, (1988)
[245] Newman, R.E.; Dutton, R.D.; Brigham, R.C., Connecting sets in graphs—a domination related concept, manuscript, (1988) · Zbl 0675.05037
[246] Nieminen, J., A method to determine a minimal dominating set of a graph go, IEEE trans. circuits and systems, CAS-21, 1, 12-14, (1974)
[247] Nieminen, J., Two bounds for the domination number of a graph, J. inst. math. applics., 14, 183-187, (1974) · Zbl 0288.05124
[248] Ore, O., Theory of graphs, (), 206-212
[249] Payan, C., A class of threshold and domishold graphs: equistable and equidominating graphs, Discrete math., 29, 47-52, (1980) · Zbl 0542.05050
[250] C. Payan, Remarks on cliques and dominating sets in graphs, manuscript, undated. · Zbl 0443.05063
[251] Payan, C., Sur le nombre d’absorption d’un graphe simple, Cahiers centre études rech. opér., 171, 2.3.4, (1975) · Zbl 0341.05126
[252] Payan, C.; Xuong, N.H., Domination-balanced graphs, J. graph theory, 6, 1, 23-32, (1982) · Zbl 0489.05049
[253] Pfaff, J., Algorithmic complexities of domination-related graph parameters, ()
[254] Pfaff, J.; Laskar, R.; Hedetniemi, S.T., Linear algorithms for independent domination and total domination in series-parallel graphs, Congr. numer., 45, 71-82, (1985)
[255] Pfaff, J.; Laskar, R.; Hedetniemi, S.T., NP-completeness of total and connected domination, and irredundance for bipartite graphs, () · Zbl 0647.05060
[256] Phillippe, V., Quasi-kernels of minimum weakness in a graph, Discrete math., 20, 2, 187-192, (1977)
[257] Proskurowski, A., Minimum dominating cycles of two-trees, Internat. J. comput. inform. sci., 8, 5, 405-417, (1979) · Zbl 0433.05039
[258] Proskurowski, A.; Syslo, M.M., Minimum dominating cycles in outerplanar graphs, Internat. J. comput. inform. sci., 10, 127-139, (1981) · Zbl 0476.05064
[259] Rall, D.F., Domatically critical and domatically full graphs, Discrete math., 86, 81-87, (1990), (this Vol.) · Zbl 0745.05061
[260] Rall, D.F.; Slater, P.J., On location-domination numbers for certain classes of graphs, Congr. numer., 45, 97-106, (1984)
[261] Sampathkumar, E., (1-k)-domination in a graph, J. math. phys. sci., 22, 5, 613-619, (1988) · Zbl 0658.05039
[262] Sampathkumar, E., K-size vertex covering and domination numbers of a graph, (1988), manuscipt · Zbl 0658.05039
[263] Sampathkumar, E., Strong, weak domination and domination balance in a graph, D. math. phys. sci., 22, 5, 613-619, (1990) · Zbl 0658.05039
[264] Sampathkumar, E., The least point covering and domination numbers of a graph, Discrete math., 86, 137-142, (1990), (this Vol.) · Zbl 0744.05039
[265] Sampathkumar, E.; Kamath, S.S., Mixed domination in graphs, (1988), manuscript · Zbl 0882.05076
[266] Sampathkumar, E.; Neeralagi, P.S., Independent, perfect and connected neighborhood numbers of a graph, (1988), manuscript
[267] Sampathkumar, E.; Neeralagi, P.S., The neighborhood number of a graph, Indian J. pure appl. math., 16, 2, 126-132, (1985) · Zbl 0564.05052
[268] Sampathkumar, E.; Venkatachalam, C.V., Domination, independent and cover partitions of a graph, (1988), manuscript · Zbl 0688.05028
[269] E. Sampathkumar and H.B. Walikar, On a conjecture of Cockayne and Hedetniemi, J. Comput. Inform. System Sci., to appear. · Zbl 0532.05042
[270] Sampathkumar, E.; Walikar, H., The connected domination number of a graph, J. math. phys. sci., 13, 6, 607-613, (1979) · Zbl 0449.05057
[271] Sanchis, L.A., Maximum number of edges in connected graphs with a given domination number, (1988), manuscript
[272] Scheffler, P., Linear-time algorithms for NP-complete problems restricted to partial k-trees, () · Zbl 0629.68043
[273] Scheid, F., Some packing problems, Amer. math. monthly, 67, 231-235, (1960) · Zbl 0092.01304
[274] Schmidt, G.; Strohlein, T., Kernel in bipartite graphs (German summary), (), 251-256
[275] G. Schimidt and T. Strohlein, On kernels of graphs and solutions of games: a sypnosis based on relations and fixpoints, SIAM J. Algebraic Discrete Methods 6 (1) 54-65. · Zbl 0554.05032
[276] Schone, W., Algorithmen zur bestimmung intern und extern stabiler mengen und der chromatischen zahl eines endlichen graphen, Wiss. Z. techn. hochsch. karl marx-stadt, 17, 2, 269-280, (1975) · Zbl 0368.05035
[277] D. Seese, Tree-partite graphs and the complexity of algorithms, in: FCT 85, Lecture Notes in Computer Science 199 (Springer, Berlin) 412-421. · Zbl 0574.68036
[278] Selig, W.J.; Slater, P.J., Minimum dominating, optimally independent vertex sets in graphs, Proceedings sixth international conference on the theory and applications of graphs, (1988), to appear · Zbl 0841.05050
[279] Shee, S.C., On stabilities and chromatic number of a loop graph, Nanta math. IV, 8-14, (1970) · Zbl 0218.05059
[280] Shepherd, B.; Gamble, B.; Cockayne, E.J., Domination parameters for the bishops graph, () · Zbl 0602.05040
[281] Shneyder, B.N., Algebra of sets applied to solution of graph theory problems, Izv. akad. nauk SSSR tehn. kibernet., Cybernetics, 8, 3, 521-526, (1971), (1970)
[282] Sirokov, F.V.; Signaevskii, V.A., Minimal coverings of a finite set I (Russian), Diskret analiz., 21, 72-94, (1972)
[283] Sirokov, F.V.; Signaevskii, V.A., Minimal coverings of a finite set II (Russian): connected coverings, Diskret analiz., Diskret analiz., Cf. dokl. akad. nauk SSSR, 207, 1066-1069, (1972), MR 47 #3216
[284] Skowrońska, M.; Syslo, M.M., Dominating cycles in halin graphs, Discrete math., 86, 215-224, (1990), (this Vol.) · Zbl 0745.05062
[285] Slater, P.J., A characterization of SOFT hypergraphs, Canad. math. bull., 21, 335-337, (1978) · Zbl 0391.05042
[286] Slater, P.J., Dominating and reference sets in a graph, J. math. phys. sci., 22, 3, 323-330, (1989)
[287] Slater, P.J., Domination and location in acyclic graphs, Networks, 17, 55-64, (1987) · Zbl 0643.90089
[288] Slater, P.J., Enclaveless sets and MK-systems, J. res. nat bur. standards, 82, 197-202, (1977) · Zbl 0421.05053
[289] Slater, P.J., Irreducible point independence numbers and independence graphs, (), 647-660
[290] Slater, P.J., Leaves of trees, (), 549-559
[291] Slater, P.J., R-domination in graphs, J. assoc. comput. Mach., 23, 446-450, (1976) · Zbl 0349.05120
[292] Spencer, P.H.; Cockayne, E.J., An upper bound for the domination number of the queens graph, () · Zbl 0709.05013
[293] Stewart, L., Permutation in graph structure and algorithms, ()
[294] Sumner, D.P., Critical concepts in domination, Discrete math., 86, 33-46, (1990), (this Vol.) · Zbl 0725.05049
[295] Sumner, D.P.; Blitch, P., Domination critical graphs, J. combin. theory ser. B, 34, 1, 65-76, (1983) · Zbl 0512.05055
[296] Sun, Liang, Contributions to connected domination in graphs, manuscript, (1988)
[297] Syslo, M.M., NP-complete problems on some tree-structured graphs: a review, (), 342-353, (Workshop on Graph Theoretic Concepts in Computer Science, Universitat Osnabruck, June 1983) · Zbl 0551.68058
[298] Syslo, M.M., The calculation of a-sets of representatives, Zastos. mat., 13, 347-350, (1972/73) · Zbl 0265.05008
[299] Tjagunov, L.I., Some properties of the structure of the set of kernels of a symmetric graph (Russian), Trudy inst. mat. i meh, ural. naucn. centr akad. nauk SSSR 27, Trudy inst. mat. i meh, ural. naucn. centr akad. nauk SSSR 27, 126-127, (1979), Metody Mat. Programmiv. i Prilozon
[300] Tuza, Z., Covering all cliques of a graph, Discrete math., 86, 117-126, (1990), (this Vol.) · Zbl 0744.05040
[301] Van Nuffelen, C., Rank and domination number, (), 209-211
[302] Veldman, H.J., Existence of dominating cycles and paths, Discrete math., 43, 281-296, (1983) · Zbl 0503.05037
[303] Vinnicenko, M.G., A lower bound for the number of edges of a graph with prescribed internal and external stability numbers, Dopovidi akad. nauk ukrain RSR ser. A, Dopovidi akad. nauk ukrain RSR ser. A, 571-489, (1973)
[304] Vizing, V.G., A bound on the external stability number of a graph, Dokl. akad. nauk SSSR, 164, 729-731, (1965) · Zbl 0136.44703
[305] Walikar, H.B., On star-partition number of a graph, manuscript, (1979) · Zbl 0449.05057
[306] Walikar, H.B., Some topics in graph theory (contributions to the theory of domination in graphs and its applications), () · Zbl 1196.05073
[307] Walikar, H.B.; Acharya, B.D., Domination critical graphs, Nat. acad. sci. lett., 2, 2, 70-72, (1979) · Zbl 0401.05056
[308] H.B. Walikar and B.D. Acharya, On an extremal problem concerning a Nordhaus-Gaddum type result in the theory of domination in graphs, manuscript, undated.
[309] Walikar, H.B.; Acharya, B.D.; Sampathkumar, E., Recent developments in the theory of domination in graphs, () · Zbl 0401.05056
[310] Walikar, H.B.; Sampathkumar, E.; Acharya, B.D., Two new bounds for the domination number of a graph, manuscript, (1979) · Zbl 0449.05057
[311] Wang, Chengde, On the sum of two parameters concerning independence and irredundance in a graph, manuscript, (1984) · Zbl 0633.05059
[312] Weber, K., Domination number for almost every graph, Rostock. math. kolloq., 16, 31-43, (1981) · Zbl 0476.05067
[313] White, K.; Farber, M.; Pulleyblank, W., Steiner trees, connected domination and strongly chordal graphs, Networks, 15, 109-124, (1985) · Zbl 0579.05050
[314] Wimer, T.V., An O(n) algorithm for domination in k-chordal graphs, (1986), manuscript
[315] Wimer, T.V., Linear algorithms for the dominating cycle problems in series-parallel graphs, 2-trees and halin graphs, (), Congr. Numer., to appear · Zbl 0669.05050
[316] Wimer, T.V., Linear algorithms on k-terminal graphs, () · Zbl 0669.05050
[317] Wimer, T.V.; Hedetniemi, S.T.; Laskar, R., A methodology for constructing linear graph algorithms, Congr. numer., 50, 43-60, (1985) · Zbl 0603.68040
[318] Yannakakis, M.; Gavril, F., Edge dominating sets in graphs, SIAM J. appl. math., 38, 264-272, (1980) · Zbl 0455.05047
[319] Zelinka, B., Adomatic and idomatic numbers of graphs, Math. slovaca, 33, 1, 99-103, (1983) · Zbl 0507.05059
[320] Zelinka, B., Bichromaticity and domatic number of a bipartite graph, Casopis pest. mat., Casopis pest. mat., 110, 2, 207-115, (1985) · Zbl 0575.05046
[321] Zelinka, B., Complementarily domatic number of a graph, Math. slovaca, 38, 1, 27-32, (1988) · Zbl 0641.05045
[322] Zelinka, B., Domatic number and bichromaticity of a graph, (), 278-285
[323] Zelinka, B., Domatic number and degrees of vertices of a graph, Math. slovaca, 33, 2, 145-147, (1983) · Zbl 0516.05032
[324] Zelinka, B., Domatic numbers of cube graphs (Russian summary), Math. slovaca, 32, 2, 117-119, (1982) · Zbl 0487.05057
[325] B. Zelinka, Domatic numbers of directed graphs, Czech, Math. J., to appear. · Zbl 0847.05063
[326] Zelinka, B., Domatic numbers of uniform hypergraphs, Arch. math., 21, 3, 129-134, (1985) · Zbl 0605.05032
[327] Zelinka, B., Domatically cocritical graphs, Casopis pest. mat., 108, 1, 82-88, (1983) · Zbl 0517.05055
[328] Zelinka, B., Domatically critical graphs, Czechoslovak math. J., 30, 105, 486-489, (1980), (3) · Zbl 0426.05046
[329] Zelinka, B., Domatische zahlen der graphen (domatic numbers of graphs), (), Rockstock. math. kolloq., 21, 69-72, (1982) · Zbl 0517.05054
[330] Zelinka, B., Edge-domatic number of a graph, Czech. math. J., 33, 108, 107-110, (1983), (1) · Zbl 0537.05049
[331] Zelinka, B., On domatic numbers of graphs (Russian summary), Math. slovaca, 31, 1, 91-95, (1981) · Zbl 0472.05057
[332] Zelinka, B., On k-domatic numbers of graphs, Czech. math. J., 33, 108, 309-313, (1983), (2) · Zbl 0537.05050
[333] Zelinka, B., On k-ply domatic numbers of graphs, Math. slovaca, 34, 3, 313-318, (1984) · Zbl 0602.05039
[334] Zelinka, B., Regular totally domatically full graphs, Discrete math., 86, 71-79, (1990), (this Vol.) · Zbl 0745.05065
[335] Zelinka, B., Semidomatic numbers of directed graphs, Math. slovaca, 34, 371-374, (1984) · Zbl 0602.05038
[336] Zelinka, B., Some remarks on domatic numbers of graphs, Casopis pest. mat., 106, 373-375, (1981) · Zbl 0476.05063
[337] Zelinka, B., The bigraph decomposition number of a graph, Casopis pest. mat., 113, 1, 56-59, (1986) · Zbl 0698.05043
[338] B. Zelinka, Uniquely domatic regular domatically full graphs, Czech. Math. J., to appear. · Zbl 0745.05065
[339] Arnborg, S.; Lagergren, J.; Seese, D., Problems easy for tree-decomposable graphs, extended abstract, (), 38-51
[340] M.J. Atallah, G.K. Manacher and J. Urrutia, Finding a minimum independent dominating set in a permutation graph, Tech. Rept., Dept. Computer Science, Purdue Univ. · Zbl 0667.05055
[341] Berge, C.; Duchet, P., Recent problems and results about kernels in directed graphs, (), 200-204 · Zbl 0669.05036
[342] Bodlaender, H.L., Dynamic programming on graphs with bounded treewidth, (), 105-118
[343] Brewster, R.C.; Cockayne, E.J.; Mynhardt, C.M., Irredundant Ramsey numbers for graphs, J. graph theory, 13, 3, 283-290, (1989) · Zbl 0692.05044
[344] E.J. Cockayne, G. Fricke, S.T. Hedetniemi and C.M. Mynhardt, Properties of minimal dominating functions of graphs, Discrete Math., submitted. · Zbl 0840.05090
[345] Cockayne, E.J.; Hedetniemi, S.T.; Laskar, R., Gallai theorems for graphs, hypergraphs and set systems, Discrete math., 72, 35-47, (1988) · Zbl 0728.05050
[346] Cockayne, E.J.; Mynhardt, C.M., Domination sequences of graphs, manuscript, (1987) · Zbl 0667.05053
[347] D’Atri, A.; Moscarini, M., Distance-hereditary graphs, Steiner trees, and connected domination, SIAM J. comput., 17, 521-538, (1988) · Zbl 0647.05048
[348] Dawes, R.W., Neighborhood covers for trees, ()
[349] Dutton, R.D.; Brigham, R.C., An extremal problem for the edge domination insensitive graphs, Discrete appl. math., 20, 2, 113-125, (1988) · Zbl 0638.05031
[350] Elmallah, E.S.; Stewart, L.K., Domination in polygon graphs, manuscript, (1990) · Zbl 0891.68068
[351] Elmallah, E.S.; Stewart, L.K., Independence and domination in polygon graphs, manuscript, (1990) · Zbl 0891.68068
[352] Faudree, R.J.; Schelp, R.H.; Shreve, W.E., The domination number for the product of graphs, (1990), manuscript · Zbl 0862.05060
[353] Favaron, O., k-domination and k-independence in graphs, Ars combin. 25-C, 159-167, (1988) · Zbl 0820.05041
[354] Fellows, M.; Fricke, G.; Hedetniemi, S.; Jacobs, D., The irredundance cube, (1990), manuscript
[355] Finbow, A.; Hartnell, B., On locating dominating sets and well-covered graphs, Congr. numer., 65, 191-200, (1988) · Zbl 0674.05060
[356] Finbow, A.; Hartnell, B.; Nowakowski, R., Well-dominated graphs: a collection of well-covered ones, Ars combin., 25-A, 5-10, (1988) · Zbl 0652.05056
[357] P. Flach and L. Volkmann, Estimations for the domination number of a graph, Discrete Math., to appear. · Zbl 0699.05055
[358] Fraisse, P., A note on distance dominating cycles, Discrete math., 71, 1, 89-92, (1988) · Zbl 0642.05031
[359] Fricke, G., On the equivalence of the upper irredundance and fractional upper irredundance numbers of a graph, (1988), manuscript · Zbl 1104.05055
[360] Fricke, G.H., Upper domination on double cone graphs, Congr. numer., 72, 199-207, (1990)
[361] Fricke, G., When is an irredundant function on a graph maximal?, (1988), manuscript
[362] G. Fricke, E.O. Hare, D.P. Jacobs and A. Majumdar, On integral and fractional total domination, Congr. Numer., to appear. · Zbl 0862.05061
[363] Genert, D., Inequalities between the domination number and the chromatic number of a graph, Discrete math., 76, 151-153, (1989)
[364] Grinstead, D.L., Algorithmic templates and multiset problems in graphs, () · Zbl 0691.05043
[365] Harary, F.; Livingston, M., The caterpillars with equal domination and independent domination numbers, (1988), manuscript
[366] Hare, E.O., Algorithms for grids and grid-like graphs, () · Zbl 0791.05059
[367] E.O. Hare, K-weight domination and fractional domination of Pm x Pn, Congr. Numer., to appear.
[368] Hare, E.; Hedetniemi, S.; Laskar, R.; Peters, K.; Wimer, T., Linear-time computability of combinatorial problems on generalized-series-parallel graphs, (), 437-457, Kyoto, Japan · Zbl 0643.68093
[369] S.M. Hedetniemi, S.T. Hedetniemi and D.P. Jacobs, Private domination: theory and algorithms, congr. Numer., to appear. · Zbl 0862.05055
[370] Hedetniemi, S.T.; Laskar, R.; Capobianco, M.F.; Guan, M.; Hsu, D.F.; Tian, F., On irredundance, dimension and rank in posets, Graph theory and its applications: east and west, Ann. New York acad. sci., 576, 235-240, (1989), Proceedings First China-U.S.A. International Graph Theory Conference · Zbl 0798.06004
[371] Henning, M.A.; Swart, H.C., Bounds on a generalized domination parameter, manuscript, (1989)
[372] M.A. Henning and H.C. Swart, Bounds on a generalized total domination parameter, J. Combin. Math. Combin. Comput., to appear. · Zbl 0692.05057
[373] Henning, M.A.; Swart, H.C., Bounds relating generalized domination parameters, (1989), manuscript
[374] Horton, J.D.; Koilakos, K., Minimum edge dominating sets, (1989), manuscript
[375] Huseby, A.B., Domination theory and the crapo β-invariant, Networks, 1, 135-149, (1989) · Zbl 0668.05023
[376] Hujter, M., Bibliography on the minimum dominating set problem, (1984), RUTCOR, Rutgers Univ New Brunswick, NJ
[377] Irving, R.W., On approximating the minimum independent dominating set, manuscript, (1990)
[378] A.H. C, Solutions to the N×N knights cover problem, J. Recreational Math., to appear.
[379] Jacobson, M.S.; Peters, K., Complexity question for n-domination and related parameters, Congr. numer., 68, 7-22, (1989)
[380] Jayaram, S.R., Line domination in graphs, Graphs combin., 3, 4, 357-363, (1987) · Zbl 0628.05056
[381] Kok, J.; Mynhardt, C.M., Reinforcement in graphs,manuscript, (1990)
[382] Kratsch, D.; Stewart, L., Domination on cocomparability graphs, manuscript, (1989)
[383] Kys, P., Remarks on domatic number, Acta math. univ. Comenian, 46/47, 237-241, (1986) · Zbl 0608.05043
[384] Laskar, R.; Majumdar, A.; Domke, G.; Fricke, G., A fractional view of graph theory, manuscript, (1990) · Zbl 0882.05074
[385] Manacher, G.K.; Smith, C.J., Efficient algorithms for new problems on interval graphs and interval models, manuscript, (1984)
[386] Marcu, D., An upper bound on the domination number of a graph, Math. scand., 59, 1, 41-44, (1986) · Zbl 0662.05056
[387] McCuaig, W.; Shepherd, B., Domination in graphs with minimum degree two, J. graph theory, 13, 6, 749-762, (1989) · Zbl 0708.05058
[388] Peters, K.W., Theoretical and algorithmic results on domination and connectivity, ()
[389] Rall, D., Dominating a graph and its complement, (1990), manuscript
[390] Rall, D.F., A fractional version of domatic number, Congr. numer., 74, 100-106, (1990)
[391] G. Ramalingam and C. Pandu Rangan, A unified approach to domination problems in interval graphs, Inform. Process. Lett., to appear. · Zbl 0658.05040
[392] Ramalingam, G.; Pandu Rangan, C., Total domination in interval graphs, Inform. process. lett., 27, 17-21, (1988), revisited · Zbl 0662.68069
[393] Sampathkumar, E., The global domination number of a graph, J. math. phys. sci., 23, 377-385, (1989) · Zbl 0729.05045
[394] Singh, H.G.; Pargas, R.P., A parallel implementation for the domination number of a grid graph, Congr. numer., 59, 5-12, (1987) · Zbl 0645.68072
[395] Spinrad, J.; Brandstädt, A.; Stewart, L., Bipartite permutation graphs, Discrete appl. math., 18, 279-292, (1987) · Zbl 0628.05055
[396] J. Topp and L. Volkmann, Characterization of unicyclic graphs with equal domination and independence numbers, submitted. · Zbl 0763.05088
[397] J. Topp and L. Volkmann, On domination and independence numbers of graphs, results in mathematics, to appear. · Zbl 0748.05066
[398] Topp, J.; Volkmann, L., On graphs with equal domination and independent domination numbers, (1990), manuscript
[399] Topp, J.; Volkmann, L., On packing and covering numbers of graphs, (1990), manuscript
[400] Topp, J.; Volkmann, L., Some upper bounds for the product of the domination number and the chromatic,number of a graph, (1990), manuscript
[401] Topp, J.; Volkmann, L., Well covered and well dominated block graphs and unicyclic graphs, (1990), manuscript · Zbl 0728.05031
[402] Zelinka, B., Connected domatic number of a graph, Math. slovaca, 36, 4, 389-392, (1986) · Zbl 0625.05042
[403] Zelinka, B., Total domatic number of cacti, Math. slovaca, 38, 3, 207-214, (1988) · Zbl 0654.05059
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.