|Table of Contents|

The Exact Domination Number of GeneralizedPetersen Graphs P（n，k）with n=3k(PDF)

《南京师大学报（自然科学版）》[ISSN:1001-4616/CN:32-1239/N]

Issue:
2016年02期
Page:
10-
Research Field:
数学
Publishing date:

Info

Title:
The Exact Domination Number of GeneralizedPetersen Graphs P（n，k）with n=3k
Author(s):
Long Yan
Teacher Education Department，Xinjiang Applied Vocational Technical College，Kuitun 833200，China
Keywords:
dominating set; domination number; generalized Petersen graph
PACS:
O157.5
DOI:
10.3969/j.issn.1001-4616.2016.02.003
Abstract:
A subset [S?V] is a dominating set of [G=(V,E)] if each vertex in [V\S] is adjacent to at least one vertex in [S]. The domination number of [G] is the cardinality of a minimum dominating set of [G]. 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. In this paper，we determine that the exact domination number of generalized Petersen graphs [P(n,k)] with [n=3k]，[γ(P(n,k))=5n9].

References:

［1］ HAYNES T W，HEDETNIEMI S T，SLATER P J. Fundamentals of domination in graphs［M］//Monographs and textbooks in pure and applied mathematics，208. New York：Marcel Dekker Inc，1998.
［2］ HAYNES T W，HEDETNIEMI S T，SLATER P J. Domination in graphs，advanced topics［M］//Monographs and textbooks in pure and applied mathematics，209. New York：Marcel Dekker Inc，1998.
［3］ BEHZAD A，BEHZAD M，PRAEGER C E. On the domination number of the generalized Petersen graphs［J］. Discrete mathematics，2008，308：603-610.
［4］ EBRAHIMI B J，JAHANBAKHT N，MAHMOODIANC E S. Vertex domination of generalized Petersen graphs［J］. Discrete mathematics，2009，309：4 355-4 361.
［5］ FU X，YANG Y，JIANG B. On the domination number of generalized Petersen graphs P（n，3）［J］. Ars Combin，2007，84：373-383.
［6］ FU X，YANG Y，JIANG B. On the domination number of generalized Petersen graphs P（n，2）［J］. Discrete mathematics，2009，309：2 445-2 451.
［7］ YAN H，KANG L，XU G. The exact domination number of the generalized Petersen grapes［J］. Discrete mathematics，2009，309：2 596-2 607.
［8］ ZELINKA B. Domination in generalized Petersen graphs［J］. Czechoslovak math J，2002，52（127）：11-16.

Memo

Memo:
-
Last Update: 2016-06-30