On the domination number of prisms of graphs
Author(s) -
Alewyn P. Burger,
Christina M. Mynhardt,
William D. Weakley
Publication year - 2004
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.1233
Subject(s) - mathematics , combinatorics , domination analysis , graph , vertex (graph theory)
For a permutation π of the vertex set of a graph G, the graph πG is obtained from two disjoint copies G1 and G2 of G by joining each v in G1 to π(v) in G2. Hence if π = 1, then πG = K2 × G, the prism of G. Clearly, γ(G) ≤ γ(πG) ≤ 2γ(G). We study graphs for which γ(K2 × G) = 2γ(G), those for which γ(πG) = 2γ(G) for at least one permutation π of V (G) and those for which γ(πG) = 2γ(G) for each permutation π of V (G).
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom