图的控制问题研究
|
摘要
图的控制理论是图论中的一个重要研究领域.自从上个世纪八十年代以来,控制理论根据不同的实际应用背景,演化出各种不同性质的的控制数.这篇论文主要研究其中两种重要的控制:全{k}-控制和符号控制.
在第一部分中,我们首先介绍图论的发展历史背景及一些常用的术语概念.然后,再给出比较经典的控制数的概念其研究问题.
第二部分中,我们主要探讨全{k}-控制数以及笛卡尔乘积图的全{k}-控制数的一个下界:γt~({k})(G)γt~({k})(G)≤k(k+1)γt~({k})(G□H).这个结果包含并提高了全控制数及全{k}-控制数的Vizing猜想的多个已有结果.并且彻底解决了Henning和Rall 2005年在[On the total domination number of Cartesian product of graph,Graphs and combinatorics 21(2005),63-69 ]一文中提出的关于笛卡尔乘积图的全控制数的一个猜想γ{t}(G)γ{t}(G)≤2_(γ{t})(G□H).从而解决了全控制数的Vizing-like问题.然后我们研究了全{k}-控制划分数问题,特别是得到了完全图的全{k}-控制划分数的上界.从而解决了S.M. Sheikholeslami和L. Volkmann在[The total k?domatic number of a graph, Journal of Combinatorial Optimization]一文中提出的完全图的全k?控制划分数问题.
第三部分中,我们主要是研究了符号控制数的稳定性问题:符号控制数的约束数和符号控制数的加强数.我们首先给出了常见几类图的符号加强数和符号约束数.然后我们给出了树图的符号控制数的上界: R_s(T)≤2,并且证明了此上界的紧性,给出了上界取等号时的几类图.
The study of dominations has become to be one of the best important top-ics in combinatorics and graph theory. Since the eighty of the last century, theconcepts of various dominations with special properties according to the di?erenceof practical backgrounds have been proposed from the classic domination. Thisthesis mainly study two kinds of important dominations, the total {k}-dominationand the reinforcement number of the signed domination number.
In Part 1, besides introducing the developing background and some conceptsof graph theory, we mainly present the de?nition of domination numbers andresearch problems on domination theory.
In Part 2, we mainly discuss the total {k}-domination. At the beginning,we get the lower bound of the total {k}-domination number of Cartesian productgraphs, that is,γt~({k})(G)γt~({k})(G)≤k(k+1)γt~({k})(G□H). This lower bound containsand improves some known results on Vizing’s conjectures on the total dominationnumber and the total {k}-domination number, and so we give a proof for theconjecture proposed by Henning and Rall in [ On the total domination number ofCartesian product of graphs, Graphs and Combinatorics]. So we solve the Vizing-like problem on the total domination number. Then, we study the total k-domaticnumber of a graph. We obtain an upper bound of the total k-domatic numberof a complete graph, and then give an answer to the question proposed by S. M.Sheikholeslami and L. Volkmann in the forthcoming paper [The total k-domaticnumber of a graph, Journal of Combinatorial Optimization].
In Part 3, we introduce the concepts of the bondage number and the reinforce-ment number of the signed domination number, and determine the reinforcementnumber of the signed domination number of some normal graphs. Especially, weget the upper bound of the reinforcement number R_s of the signed dominationnumber of a tree T, that is, R_s(T)≤2. In fact, we prove that the bound is tight and give graphs achieving the upper bound.
In the end, we survey our main research results in this thesis, and provide someimmature results on the reinforcement number of the signed domination number.We also propose some questions that are worthy of further deep consideration.
在第一部分中,我们首先介绍图论的发展历史背景及一些常用的术语概念.然后,再给出比较经典的控制数的概念其研究问题.
第二部分中,我们主要探讨全{k}-控制数以及笛卡尔乘积图的全{k}-控制数的一个下界:γt~({k})(G)γt~({k})(G)≤k(k+1)γt~({k})(G□H).这个结果包含并提高了全控制数及全{k}-控制数的Vizing猜想的多个已有结果.并且彻底解决了Henning和Rall 2005年在[On the total domination number of Cartesian product of graph,Graphs and combinatorics 21(2005),63-69 ]一文中提出的关于笛卡尔乘积图的全控制数的一个猜想γ{t}(G)γ{t}(G)≤2_(γ{t})(G□H).从而解决了全控制数的Vizing-like问题.然后我们研究了全{k}-控制划分数问题,特别是得到了完全图的全{k}-控制划分数的上界.从而解决了S.M. Sheikholeslami和L. Volkmann在[The total k?domatic number of a graph, Journal of Combinatorial Optimization]一文中提出的完全图的全k?控制划分数问题.
第三部分中,我们主要是研究了符号控制数的稳定性问题:符号控制数的约束数和符号控制数的加强数.我们首先给出了常见几类图的符号加强数和符号约束数.然后我们给出了树图的符号控制数的上界: R_s(T)≤2,并且证明了此上界的紧性,给出了上界取等号时的几类图.
The study of dominations has become to be one of the best important top-ics in combinatorics and graph theory. Since the eighty of the last century, theconcepts of various dominations with special properties according to the di?erenceof practical backgrounds have been proposed from the classic domination. Thisthesis mainly study two kinds of important dominations, the total {k}-dominationand the reinforcement number of the signed domination number.
In Part 1, besides introducing the developing background and some conceptsof graph theory, we mainly present the de?nition of domination numbers andresearch problems on domination theory.
In Part 2, we mainly discuss the total {k}-domination. At the beginning,we get the lower bound of the total {k}-domination number of Cartesian productgraphs, that is,γt~({k})(G)γt~({k})(G)≤k(k+1)γt~({k})(G□H). This lower bound containsand improves some known results on Vizing’s conjectures on the total dominationnumber and the total {k}-domination number, and so we give a proof for theconjecture proposed by Henning and Rall in [ On the total domination number ofCartesian product of graphs, Graphs and Combinatorics]. So we solve the Vizing-like problem on the total domination number. Then, we study the total k-domaticnumber of a graph. We obtain an upper bound of the total k-domatic numberof a complete graph, and then give an answer to the question proposed by S. M.Sheikholeslami and L. Volkmann in the forthcoming paper [The total k-domaticnumber of a graph, Journal of Combinatorial Optimization].
In Part 3, we introduce the concepts of the bondage number and the reinforce-ment number of the signed domination number, and determine the reinforcementnumber of the signed domination number of some normal graphs. Especially, weget the upper bound of the reinforcement number R_s of the signed dominationnumber of a tree T, that is, R_s(T)≤2. In fact, we prove that the bound is tight and give graphs achieving the upper bound.
In the end, we survey our main research results in this thesis, and provide someimmature results on the reinforcement number of the signed domination number.We also propose some questions that are worthy of further deep consideration.
引文
[1] B. Bres(?)ar, M.A. Henning and D.F. Rall, Paired-domination of Cartesian productsof graphs and rainbow domination, Electronic Notes in Discrete Math., 22 (2005),233–237.
[2] B. Bres(?)ar, M.A. Henning and S. Klarzar, On integer domination in graphs andVizing-liking problem, Taiwanese. J. Math., 10(5) (2006), 1317–1328.
[3] B. Bres(?)ar, Vizing-liking conjecture for the upper domination of Cartesian productsof graphs (?) the proof, Electron. J. Combin., 12(2005), Note 12, 6pp.
[4] B. L. Hartnell and D.F.Rall, A characterization of trees in which no edge is essen-tial to the domination number. Ars Combinatoria. 33(1992), 65–76.
[5] B. L. Hartnell and D.F.Rall, Bounds on the bondage number of graph.DiscretMath. 128(1994), 173–177.
[6] B. Zelinka, Signed domination number of directed graphs, Czechoslovak Math. J.55(130)(2005),479–482.
[7] B. Zelinka, Total domatic number and degrees of vertices of a graph. Math. Slovaca,39(1989), 7–11.
[8] B. Zelinka, Total domatic number of graph. Proc. Math. Liberec (1994).
[9] Douglas B. West, Introduction to Graph Theory, Prentice-Hall, Inc, 2000.
[10] D. Bauer, F. Harary, J.Nieminen and C.L.Sujel, Domination alteration sets ingraphs. Discrete Mathematics 47(1983), 153–161.
[11] E. J. Cockayne, R. M. Dawes, and S. T. Hedetniemi, Total domination in graphs.Networks 10(1980), 211–219.
[12] E. J. Cockayne, S. T. Hedetniemi, Towards a theory of domination in graphs.Networks 7(1977), 247–261.
[13] G. Chartrant and L. Lesniak, Graphs & Digraphs, 3rd ed., Chapman and Hall,London, (1996).
[14] Gayla, Domke, Renu C. Laskar, The bondage and reinforcement number ofγf forsome graphs, Discrete Math. 167/168 (1997), 249–259.
[15] Haas, Ruth; Wexler, Thomas B, Bounds on the signed domination number of agraph. The Ninth Quadrennial International Conference on Graph Theory, Combi-natorics, Algorithms and Applications, 9 pp. (electronic), Electron. Notes DiscreteMath., 11, Elsevier, Amsterdam, 2002.
[16] Haas, Ruth; Wexler, Thomas B., Signed domination numbers of a graph and itscomplement. Discrete Math. 283(1-3) (2004), 87–92.
[17] H. B. Walikar, B. D. Acharya, Domination critical graphs, National AcademyScience Letters - India 2(1979),70–72.
[18] H. Tang, Y. Chen, Upper signed domination number. Discrete Mathematics.308(15)(2008), 3416–3419.
[19] J.A. Bondy and U.S.R. Murty, Graph Theory, Springer Monographs in Mathe-matics, Springer, London, (2008).
[20] J. E. Dunbar, S. T. Hedetniemi, M. A. Henning and P. J. Slater, Signed dominationin graphs, Graph Theory, Combinatorics, and Applications, John Wiley&Sons,Inc. 1 (1995), 311–322.
[21] J. E. Dunbar, T. W. Haynes, U. Teschner, L. Volkmann, Bondage, insensitivity,and reinforcement. Domination in Graphs: Advanced Topics (T. W. Haynes, S.T. Hedetniemi, P. J. Slater, Eds.), Marcel Dekker, New York, 1998, pp. 471–489.
[22] J.F. Fink and M.S. Jacobson, n-Domination in graphs, [in:] Y. Alavi, A.J. Schwenk(Eds), Graph Theory with Applications to Algorithms and Computer Science,Wiley, New York, (1885), 283–300.
[23] J. F. Fink, M. S. Jacobson, L. F. Kinch and J. Roberts, The bondage number ofa graph. Discrete Math. 86 (1990), 47-157.
[24] J. Ghoshal, R. Laskar, D. Pillon and C. Wallils, Strong bondage and strong rein-forcement numbers of graphs, Congr. Numer. 108(1995), 33-42.
[25] J. Huang, J.-W. Wang and J.-M. Xu, Reinforcement numbers of digraphs. DiscreteApplied Mathematics, doi:10.1016/j.dam.2009.01.002.
[26] J. Huang and J.-M. Xu, The bondage numbers of extended de Bruijn and Kautzdigraphs. Comput. Math. Appl. 51 (6-7)(2006), 1137-11147.
[27] J. Huang and J.-M. Xu, The bondage numbers of graphs with small crossingnumbers. Discrete Math. 307 (15)(2007), 1881–1897.
[28] J. Huang and J.-M. Xu, The bondage numbers and e(?)cient dominations of vertex-transitive graphs. Discrete Math. 308 (4)(2008), 571–582.
[29] J. Huang, J. Wang and J.-M. Xu, Reinforcement numbers of digraphs. DiscreteAppl. Math. doi:10.1016/j.dam. 2009.01.002.
[30] J. Kok, C. M. Mynhardt, Reinforcement in graphs, Congr. Numer. 79(1990), 225–231.
[31] J. Kok and C. M. Mynhardt, Reinforcement in graphs, Congr. Numer. 79(1990),225–231.
[32] J. Topp and P. D. Vestergaard,αk andγk(?) stable graphs, Discrete Mathemat-ics,212(2000), 149–160
[33] Jun-Ming Xu, Theory and Application of Graphs, Kluwer Academic Publishers,Dordrecht/Boston/London (2003).
[34] Jun-Ming Xu, Topological Structure and Analysis of Interconnection Networks,Kluwer Academic Publishers, Dordrecht/Boston/London (2001).
[35] K. Carlson and M. Develin, On the bondage number of planar and directed graphs.Discrete Math. 306 (8-9) (2006), 820–826.
[36] L. Euler, Solutio problematis ad geometriam situs pertinentis, CommetariiAcademiae Scietiarum Imperialis Petropolitanae, 8(1736), 128–140.
[37] L. Kang and J. Yuan, Bondage number of planar graphs, Discrete Math. 222(2000), 191–198.
[38] Lu, Xin-zhong, Total signed domination numbers of graphs. Int. J. Pure Appl.Math. 29(3) (2006), 281–288.
[39] Lu, Xin-zhong, Edge signed domination numbers of a graph and its complement.Int. J. Pure Appl. Math. 26(2) (2006), 211–216.
[40] Lu, Xin-zhong, A lower bound on the total signed domination numbers of graphs.Sci. China Ser. A 50(8) (2007), 1157–1162.
[41] L. Volkmann, Some remarks on lower bounds on the p-domination number in trees,J. Combin. Math. Combin. Comput., 61 (2007), 159–167.
[42] L. Volkmann, Some remarks on the signed domatic number of graphs with smallminimum degree. Applied Mathematics Letters, doi:10.1016/j.aml.2008.09.006.
[43] M.A. Henning and D.F. Rall, On the total domination number of Cartesian prod-ucts of graphs, Graphs and Combinatorics, 21 (2005), 63–69.
[44] M.A.Henning and D.F.Rall, On the upper total domination of Cartesian productsof graphs, J. Comb. Optin, 16(2008), Note 1, 13pp.
[45] M. Blidia, M. Chellali and L. Volkmann, Some bounds on the p-domination num-ber in trees. Discrete Math., 306 (2006), 2031–2037.
[46] M. Chellali, Bounds on the 2-domination number in cactus graphs, Opuscula Math.26 (2006), 5–11.
[47] M. Fischermann, D. Rautenbach and L. Volkmann, Remarks on the bondage num-ber of planar graphs. Discrete Math. 260 (2003), 57–67.
[48] M. Y. Sohn, J. Lee, Y. S. Kwon, Lower bounds of signed domination number of agraph. Bill. Korean Math. Soc,41(1)(2004),181–188.
[49] P.Tung Ho, A note on the total domination number,Utilitas Math 77 (2008), 97–100.
[50] R.D.Dutton and R.C.Brigham, An external problem for edge domination insensi-tive graphs . Discrete Applied Mathematics 20(1998), 113–125.
[51] R. Diestel, Graph Theory (3rd edition), Springer Monographs in Mathematics,Sringer, London, (2005).
[52] R. Hass, T. B. Wexler, Signed domination numbers of a graph and its complement.Discrete Math., 283(1-3)(2004), 87–92.
[53] R. J. Nowakowski and D. Rall, Associative graph products and their independence,domination and coloring number, Discuss. Math. Graph Theory 16(1996), 53–79.
[54] Sheikholeslami, S. M, Forcing signed domination numbers in graphs. Mat. Vesnik59(4) (2007), 171–179.
[55] S. M. Sheikholeslami and L. Volkmann, The total k-domatic number of a graph,Journal of Combinatorial Optimization, DOI: 10.1007/s10878-010-9352-4.
[56] S. M. Sheikholeslami, Forcing signed domination number of graphs, MatematickiVesnic, 59(2007), 171–179.
[57] Sohn, Moo Young; Lee, Jaeun; Kwon, Young Soo, Lower bounds of signed domi-nation number of a graph. Bull. Korean Math. Soc. 41(1) (2004), 181–188.
[58] Tang, Huajun; Chen, Yaojun, Upper signed domination number. Discrete Math.308(15) (2008), 3416–3419.
[59] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in graphs (Advancedtopics), Marcel Dekker, New York, (1998).
[60] U.Teschner, New results about the bondage number of a graph, Discrete Mathe-matics ,171(1997) 249–259.
[61] V.G. Vizing, Some unsoloved problems in graph theory, Uspkhi. Mat. Nauk,23(6(144)) (1968), 117–134.
[62] W.E. Clark and S. Suen, An inequality related to Vizing’s conjecture, Electron. J.Combin. 7(1) (2000), Note 4, 3pp.(electronic).
[63] Weidong. Chen and Enmin. Song, Lower bounds on several versions of signeddomination number. Discrete Math. 308(10) (2008), 1837–1846.
[64] Xing, Hua-ming; Sun, Liang, On the lower bounds of partial signed dominationnumber of graphs. Ars Combin. 74 (2005), 269–273.
[65] Xinmin Hou, Total domination of Cartesian products of graphs, Discuss. Math.Graph Theory 27 (2007), 175–178.
[66] X. Lu, Total signed domination numbers of graphs. Int. J. Pure Appl. Math.29(3)(2006), 281–288
[67] X. LU, A lower bound on the total signed domination numbers of graphs. Sci.ChinaSer.A. 50(8)(2007), 1157–1162.
[68] Zelinka, Bohdan, Signed domination numbers of directed graphs. CzechoslovakMath. J. 55(130) (2005), 479–482.
[69] Zhang, Zhongfu; Xu, Baogen; Li, Yinzhen; Liu, Linzhong, A note on the lowerbounds of signed domination number of a graph. Discrete Math. 195(1–3) (1999),295-298.
[70] Z. Zhang, B. Xu, Y. Li and L. Liu, A note on the lower bounds of signed dominationnumber of a graph, Discrete Math. 195(1999), 295–298.
[2] B. Bres(?)ar, M.A. Henning and S. Klarzar, On integer domination in graphs andVizing-liking problem, Taiwanese. J. Math., 10(5) (2006), 1317–1328.
[3] B. Bres(?)ar, Vizing-liking conjecture for the upper domination of Cartesian productsof graphs (?) the proof, Electron. J. Combin., 12(2005), Note 12, 6pp.
[4] B. L. Hartnell and D.F.Rall, A characterization of trees in which no edge is essen-tial to the domination number. Ars Combinatoria. 33(1992), 65–76.
[5] B. L. Hartnell and D.F.Rall, Bounds on the bondage number of graph.DiscretMath. 128(1994), 173–177.
[6] B. Zelinka, Signed domination number of directed graphs, Czechoslovak Math. J.55(130)(2005),479–482.
[7] B. Zelinka, Total domatic number and degrees of vertices of a graph. Math. Slovaca,39(1989), 7–11.
[8] B. Zelinka, Total domatic number of graph. Proc. Math. Liberec (1994).
[9] Douglas B. West, Introduction to Graph Theory, Prentice-Hall, Inc, 2000.
[10] D. Bauer, F. Harary, J.Nieminen and C.L.Sujel, Domination alteration sets ingraphs. Discrete Mathematics 47(1983), 153–161.
[11] E. J. Cockayne, R. M. Dawes, and S. T. Hedetniemi, Total domination in graphs.Networks 10(1980), 211–219.
[12] E. J. Cockayne, S. T. Hedetniemi, Towards a theory of domination in graphs.Networks 7(1977), 247–261.
[13] G. Chartrant and L. Lesniak, Graphs & Digraphs, 3rd ed., Chapman and Hall,London, (1996).
[14] Gayla, Domke, Renu C. Laskar, The bondage and reinforcement number ofγf forsome graphs, Discrete Math. 167/168 (1997), 249–259.
[15] Haas, Ruth; Wexler, Thomas B, Bounds on the signed domination number of agraph. The Ninth Quadrennial International Conference on Graph Theory, Combi-natorics, Algorithms and Applications, 9 pp. (electronic), Electron. Notes DiscreteMath., 11, Elsevier, Amsterdam, 2002.
[16] Haas, Ruth; Wexler, Thomas B., Signed domination numbers of a graph and itscomplement. Discrete Math. 283(1-3) (2004), 87–92.
[17] H. B. Walikar, B. D. Acharya, Domination critical graphs, National AcademyScience Letters - India 2(1979),70–72.
[18] H. Tang, Y. Chen, Upper signed domination number. Discrete Mathematics.308(15)(2008), 3416–3419.
[19] J.A. Bondy and U.S.R. Murty, Graph Theory, Springer Monographs in Mathe-matics, Springer, London, (2008).
[20] J. E. Dunbar, S. T. Hedetniemi, M. A. Henning and P. J. Slater, Signed dominationin graphs, Graph Theory, Combinatorics, and Applications, John Wiley&Sons,Inc. 1 (1995), 311–322.
[21] J. E. Dunbar, T. W. Haynes, U. Teschner, L. Volkmann, Bondage, insensitivity,and reinforcement. Domination in Graphs: Advanced Topics (T. W. Haynes, S.T. Hedetniemi, P. J. Slater, Eds.), Marcel Dekker, New York, 1998, pp. 471–489.
[22] J.F. Fink and M.S. Jacobson, n-Domination in graphs, [in:] Y. Alavi, A.J. Schwenk(Eds), Graph Theory with Applications to Algorithms and Computer Science,Wiley, New York, (1885), 283–300.
[23] J. F. Fink, M. S. Jacobson, L. F. Kinch and J. Roberts, The bondage number ofa graph. Discrete Math. 86 (1990), 47-157.
[24] J. Ghoshal, R. Laskar, D. Pillon and C. Wallils, Strong bondage and strong rein-forcement numbers of graphs, Congr. Numer. 108(1995), 33-42.
[25] J. Huang, J.-W. Wang and J.-M. Xu, Reinforcement numbers of digraphs. DiscreteApplied Mathematics, doi:10.1016/j.dam.2009.01.002.
[26] J. Huang and J.-M. Xu, The bondage numbers of extended de Bruijn and Kautzdigraphs. Comput. Math. Appl. 51 (6-7)(2006), 1137-11147.
[27] J. Huang and J.-M. Xu, The bondage numbers of graphs with small crossingnumbers. Discrete Math. 307 (15)(2007), 1881–1897.
[28] J. Huang and J.-M. Xu, The bondage numbers and e(?)cient dominations of vertex-transitive graphs. Discrete Math. 308 (4)(2008), 571–582.
[29] J. Huang, J. Wang and J.-M. Xu, Reinforcement numbers of digraphs. DiscreteAppl. Math. doi:10.1016/j.dam. 2009.01.002.
[30] J. Kok, C. M. Mynhardt, Reinforcement in graphs, Congr. Numer. 79(1990), 225–231.
[31] J. Kok and C. M. Mynhardt, Reinforcement in graphs, Congr. Numer. 79(1990),225–231.
[32] J. Topp and P. D. Vestergaard,αk andγk(?) stable graphs, Discrete Mathemat-ics,212(2000), 149–160
[33] Jun-Ming Xu, Theory and Application of Graphs, Kluwer Academic Publishers,Dordrecht/Boston/London (2003).
[34] Jun-Ming Xu, Topological Structure and Analysis of Interconnection Networks,Kluwer Academic Publishers, Dordrecht/Boston/London (2001).
[35] K. Carlson and M. Develin, On the bondage number of planar and directed graphs.Discrete Math. 306 (8-9) (2006), 820–826.
[36] L. Euler, Solutio problematis ad geometriam situs pertinentis, CommetariiAcademiae Scietiarum Imperialis Petropolitanae, 8(1736), 128–140.
[37] L. Kang and J. Yuan, Bondage number of planar graphs, Discrete Math. 222(2000), 191–198.
[38] Lu, Xin-zhong, Total signed domination numbers of graphs. Int. J. Pure Appl.Math. 29(3) (2006), 281–288.
[39] Lu, Xin-zhong, Edge signed domination numbers of a graph and its complement.Int. J. Pure Appl. Math. 26(2) (2006), 211–216.
[40] Lu, Xin-zhong, A lower bound on the total signed domination numbers of graphs.Sci. China Ser. A 50(8) (2007), 1157–1162.
[41] L. Volkmann, Some remarks on lower bounds on the p-domination number in trees,J. Combin. Math. Combin. Comput., 61 (2007), 159–167.
[42] L. Volkmann, Some remarks on the signed domatic number of graphs with smallminimum degree. Applied Mathematics Letters, doi:10.1016/j.aml.2008.09.006.
[43] M.A. Henning and D.F. Rall, On the total domination number of Cartesian prod-ucts of graphs, Graphs and Combinatorics, 21 (2005), 63–69.
[44] M.A.Henning and D.F.Rall, On the upper total domination of Cartesian productsof graphs, J. Comb. Optin, 16(2008), Note 1, 13pp.
[45] M. Blidia, M. Chellali and L. Volkmann, Some bounds on the p-domination num-ber in trees. Discrete Math., 306 (2006), 2031–2037.
[46] M. Chellali, Bounds on the 2-domination number in cactus graphs, Opuscula Math.26 (2006), 5–11.
[47] M. Fischermann, D. Rautenbach and L. Volkmann, Remarks on the bondage num-ber of planar graphs. Discrete Math. 260 (2003), 57–67.
[48] M. Y. Sohn, J. Lee, Y. S. Kwon, Lower bounds of signed domination number of agraph. Bill. Korean Math. Soc,41(1)(2004),181–188.
[49] P.Tung Ho, A note on the total domination number,Utilitas Math 77 (2008), 97–100.
[50] R.D.Dutton and R.C.Brigham, An external problem for edge domination insensi-tive graphs . Discrete Applied Mathematics 20(1998), 113–125.
[51] R. Diestel, Graph Theory (3rd edition), Springer Monographs in Mathematics,Sringer, London, (2005).
[52] R. Hass, T. B. Wexler, Signed domination numbers of a graph and its complement.Discrete Math., 283(1-3)(2004), 87–92.
[53] R. J. Nowakowski and D. Rall, Associative graph products and their independence,domination and coloring number, Discuss. Math. Graph Theory 16(1996), 53–79.
[54] Sheikholeslami, S. M, Forcing signed domination numbers in graphs. Mat. Vesnik59(4) (2007), 171–179.
[55] S. M. Sheikholeslami and L. Volkmann, The total k-domatic number of a graph,Journal of Combinatorial Optimization, DOI: 10.1007/s10878-010-9352-4.
[56] S. M. Sheikholeslami, Forcing signed domination number of graphs, MatematickiVesnic, 59(2007), 171–179.
[57] Sohn, Moo Young; Lee, Jaeun; Kwon, Young Soo, Lower bounds of signed domi-nation number of a graph. Bull. Korean Math. Soc. 41(1) (2004), 181–188.
[58] Tang, Huajun; Chen, Yaojun, Upper signed domination number. Discrete Math.308(15) (2008), 3416–3419.
[59] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in graphs (Advancedtopics), Marcel Dekker, New York, (1998).
[60] U.Teschner, New results about the bondage number of a graph, Discrete Mathe-matics ,171(1997) 249–259.
[61] V.G. Vizing, Some unsoloved problems in graph theory, Uspkhi. Mat. Nauk,23(6(144)) (1968), 117–134.
[62] W.E. Clark and S. Suen, An inequality related to Vizing’s conjecture, Electron. J.Combin. 7(1) (2000), Note 4, 3pp.(electronic).
[63] Weidong. Chen and Enmin. Song, Lower bounds on several versions of signeddomination number. Discrete Math. 308(10) (2008), 1837–1846.
[64] Xing, Hua-ming; Sun, Liang, On the lower bounds of partial signed dominationnumber of graphs. Ars Combin. 74 (2005), 269–273.
[65] Xinmin Hou, Total domination of Cartesian products of graphs, Discuss. Math.Graph Theory 27 (2007), 175–178.
[66] X. Lu, Total signed domination numbers of graphs. Int. J. Pure Appl. Math.29(3)(2006), 281–288
[67] X. LU, A lower bound on the total signed domination numbers of graphs. Sci.ChinaSer.A. 50(8)(2007), 1157–1162.
[68] Zelinka, Bohdan, Signed domination numbers of directed graphs. CzechoslovakMath. J. 55(130) (2005), 479–482.
[69] Zhang, Zhongfu; Xu, Baogen; Li, Yinzhen; Liu, Linzhong, A note on the lowerbounds of signed domination number of a graph. Discrete Math. 195(1–3) (1999),295-298.
[70] Z. Zhang, B. Xu, Y. Li and L. Liu, A note on the lower bounds of signed dominationnumber of a graph, Discrete Math. 195(1999), 295–298.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |