On Mixed Domination in Generalized Petersen Graphs

2018/12/03 by M. Rajaati, Rajaati, M., M. R. Hooshmandasl +5
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.1812.00977

openalex publication_date 2018/12/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a graph G = (V, E), a set S ⊆ V ∪ E of vertices and edges is called a mixed dominating set if every vertex and edge that is not included in S happens to be adjacent or incident to a member of S. The mixed domination number γ_md(G) of the graph is the size of the smallest mixed dominating set of G. We present an explicit method for constructing optimal mixed dominating sets in Petersen graphs P(n, k) for k ∈ \1, 2\. Our method also provides a new upper bound for other Petersen graphs.

Related

• Total mixed domination in graphs
• On the Domination Number of Generalized Petersen Graphs P(ck,k)
• [1,2]-Domination in Generalized Petersen Graphs
• An Efficient Algorithm for Mixed Domination on Generalized Series-Parallel Graphs
• Upper and Lower Bounds on Approximating Weighted Mixed Domination