On the domination number of the generalized Petersen graphs. (English) Zbl 1131.05065
Summary: Graph domination numbers and algorithms for finding them have been investigated for numerous classes of graphs, usually for graphs that have some kind of tree-like structure. By contrast, we study an infinite family of regular graphs, the generalized Petersen graphs \(G(n)\). We give two procedures that between them produce both upper and lower bounds for the (ordinary) domination number of \(G(n)\), and we conjecture that our upper bound \(\lceil 3n/5\rceil \) is the exact domination number. To our knowledge this is one of the first classes of regular graphs for which such a procedure has been used to estimate the domination number.
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
References:
| [1] | A. Behzad, M. Behzad, P. Hatami, E.S. Mahmoodian, M. Seyed Salehi, Kashkul, unpublished results on graph dominations, 2004-2005; A. Behzad, M. Behzad, P. Hatami, E.S. Mahmoodian, M. Seyed Salehi, Kashkul, unpublished results on graph dominations, 2004-2005 |
| [2] | Behzad, M.; Chartrand, G.; Lesniak-Foster, L. M., Graphs and Digraphs (1979), Prindle: Prindle Weber, and Schmidt, Boston · Zbl 0403.05027 |
| [3] | Frucht, R.; Graver, J. E.; Watkins, M. E., The groups of the generalized Petersen graphs, Proc. Cambridge Philos. Soc., 70, 211-218 (1971) · Zbl 0221.05069 |
| [4] | Garey, M. R.; Johnson, D. S., Computers, and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039 |
| [5] | Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of Domination in Graphs (1998), Marcel Dekker: Marcel Dekker New York · Zbl 0890.05002 |
| [6] | J. Pfaff, R. Laskar, S.T. Hedetniemi, NP-completeness of total and connected domination, and irredundance for bipartite graphs. Technical Report 428, Department of Mathematical Sciences, Clemson University, 1983.; J. Pfaff, R. Laskar, S.T. Hedetniemi, NP-completeness of total and connected domination, and irredundance for bipartite graphs. Technical Report 428, Department of Mathematical Sciences, Clemson University, 1983. |
| [7] | Watkins, M. E., A theorem on Tait coloring with an application to the generalized Petersen graphs, J. Combin. Theory, 6, 152-164 (1969) · Zbl 0175.50303 |
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.
