Discussiones Mathematicae Graph Theory 27(3) (2007) 541-547
doi: 10.7151/dmgt.1378

[BIBTex] [PDF] [PS]

FRACTIONAL DOMINATION IN PRISMS

Matthew Walsh

Department of Mathematical Sciences
Indiana-Purdue University
Fort Wayne, Indiana 46805, USA
e-mail: walshm@ipfw.edu

Abstract

Mynhardt has conjectured that if G is a graph such that γ(G) = γ(πG) for all generalized prisms πG then G is edgeless. The fractional analogue of this conjecture is established and proved by showing that, if G is a graph with edges, then γf(G×K2) > γf(G).

Keywords: fractional domination, graph products, prisms of graphs.

2000 Mathematics Subject Classification: 05C69.

References

[1] A.P. Burger, C.M. Mynhardt and W.D. Weakley, On the domination number of prisms of graphs, Discuss. Math. Graph Theory 24 (2004) 303-318, doi: 10.7151/dmgt.1233.
[2] G. Fricke, Upper domination on double cone graphs, in: Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1989), Congr. Numer. 72 (1990) 199-207.
[3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).
[4] C.M. Mynhardt, A conjecture on domination in prisms of graphs, presented at the Ottawa-Carleton Discrete Math Day 2006, Ottawa, Ontario, Canada.
[5] R.R. Rubalcaba and M. Walsh, Minimum fractional dominating functions and maximum fractional packing functions, in preparation.

Received 28 September 2006
Revised 24 April 2007
Accepted 25 April 2007