Article ID Journal Published Year Pages File Type
4648441 Discrete Mathematics 2010 6 Pages PDF
Abstract
The generalized prism πG of G is the graph consisting of two copies of G, with edges between the copies determined by a permutation π acting on the vertices of G. We define a generalized Cartesian product GH that corresponds to the Cartesian product G□H when π is the identity, and the generalized prism when H is the graph K2. Burger, Mynhardt and Weakley [A.P. Burger, C.M. Mynhardt, W.D. Weakley, On the domination number of prisms of graphs, Discuss. Math. Graph Theory 24 (2) (2004) 303-318.] characterized universal doublers, i.e. graphs for which γ(πG)=2γ(G) for any π. In general γ(GKn)≤nγ(G) for any n≥2 and permutation π, and a graph attaining equality in this upper bound for all π is called a universal multiplier. We characterize such graphs.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,