The bondage numbers and efficient dominations of vertex-transitive graphs. (English) Zbl 1130.05043
Summary: The bondage number of a graph \(G\) is the minimum number of edges whose removal results in a graph with larger domination number. A dominating set \(D\) is called an efficient dominating set of \(G\) if \(|N^{-}[v]\cap D|\)=1 for every vertex \(v \in V(G)\). In this paper we establish a tight lower bound for the bondage number of a vertex-transitive graph. We also obtain upper bounds for regular graphs by investigating the relation between the bondage number and the efficient domination. As applications, we determine the bondage number for some circulant graphs and tori by characterizing the existence of efficient dominating sets in these graphs.
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C35 | Extremal problems in graph theory |
References:
| [1] | Bange, D. W.; Barkauskas, A. E.; Host, L. H.; Clark, L. H., Efficient domination of the orientations of a graph, Discrete Math., 178, 1-14 (1998) · Zbl 0906.05033 |
| [2] | Bange, D. W.; Barkauskas, A. E.; Slater, P. J., Efficient dominating sets in graphs, (Ringeisen, R. D.; Roberts, F. S., Applications of Discrete Mathematics (1988), SIAM: SIAM Philadelphia), 189-199 · Zbl 0664.05027 |
| [3] | Barkauskas, A. E.; Host, L. H., Finding efficient dominating sets in oriented graphs, Congr. Numer., 98, 27-32 (1993) · Zbl 0801.05031 |
| [4] | Bondy, J.; Murty, U., Graph Theory with Applications (1976), MacMillan: MacMillan New York · Zbl 1226.05083 |
| [5] | Carlson, K.; Develin, M., On the bondage number of planar and directed graphs, Discrete Math., 306, 820-826 (2006) · Zbl 1122.05045 |
| [6] | Clark, L. H., Perfect domination in random graphs, J. Combin. Math. Combin. Comput., 14, 173-182 (1993) · Zbl 0793.05106 |
| [7] | Dejter, I. J.; Serra, O., Efficient dominating sets in Cayley graphs, Discrete Appl. Math., 129, 319-328 (2003) · Zbl 1035.05060 |
| [8] | Dunbar, J. E.; Haynes, T. W.; Teschner, U.; Volkmann, L., Bondage, insensitivity, and reinforcement, (Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Domination in Graphs: Advanced Topics (1998), Marcel Dekker: Marcel Dekker New York), 471-489 · Zbl 0894.05025 |
| [9] | Fink, J. F.; Jacobson, M. S.; Kinch, L. F.; Roberts, J., The bondage number of a graph, Discrete Math., 86, 47-57 (1990) · Zbl 0745.05056 |
| [10] | W. Gu, X. Jia, J. Shen, Independent perfect domination sets in meshes, tori and trees, preprint 2002, available at http://basilo.kaist.ac.kr/papers/SouthwestTexas/Jia/PIDS.pdf.; W. Gu, X. Jia, J. Shen, Independent perfect domination sets in meshes, tori and trees, preprint 2002, available at http://basilo.kaist.ac.kr/papers/SouthwestTexas/Jia/PIDS.pdf. |
| [11] | Hartnell, B. L.; Rall, D. F., Bounds on the bondage number of a graph, Discrete Math., 128, 173-177 (1994) · Zbl 0796.05051 |
| [12] | Huang, J.; Xu, J.-M., The bondage numbers of extended de Bruijn and Kautz digraphs, Comput. Math. Appl., 51, 1137-1147 (2006) · Zbl 1133.05041 |
| [13] | Kang, L.-Y.; Sohn, M. Y.; Kim, H. K., Bondage number of the discrete torus \(C_n \times C_4\), Discrete Math., 303, 80-86 (2005) · Zbl 1077.05077 |
| [14] | Lee, J., Independent perfect domination sets in Cayley graphs, J. Graph Theory, 37, 4, 213-219 (2001) · Zbl 0996.05096 |
| [15] | Van Wieren, D.; Livingston, M.; Stout, Q. F., Perfect dominating sets on cube-connected cycles, Congr. Numer., 97, 51-70 (1993) · Zbl 0802.05073 |
| [16] | Xu, J.-M., Topological Structure and Analysis of Interconnection Networks (2001), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, Boston, London · Zbl 1046.68026 |
| [17] | Xu, J.-M., Theory and Application of Graphs (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, Boston, London · Zbl 1035.05003 |
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.
