×

Bipartite graphs are not universal fixers. (English) Zbl 1181.05068

Summary: For any permutation \(\pi \) of the vertex set of a graph \(G\), the graph \(\pi G\) is obtained from two copies \(G{^{\prime}}\) and \(G{^{\prime\prime}}\) of \(G\) by joining \(u\in V(G{^{\prime}})\) and \(v\in V(G{^{\prime\prime}})\) if and only if \(v=\pi (u)\). Denote the domination number of \(G\) by \(\gamma (G)\). For all permutations \(\pi\) of \(V(G), \gamma (G)\leq \gamma (\pi G)\leq 2\gamma (G)\). If \(\gamma (\pi G)=\gamma (G)\) for all \(\pi \), then \(G\) is called a universal fixer. We prove that graphs without 5-cycles are not universal fixers, from which it follows that bipartite graphs are not universal fixers.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Burger, A. P.; Mynhardt, C. M.; Weakley, W. D., On the domination number of prisms of graphs, Discuss. Math. Graph Theory, 24, 303-318 (2004) · Zbl 1064.05111
[2] R.G. Gibson, C.M. Mynhardt, Universal fixers and regular graphs (submitted for publication); R.G. Gibson, C.M. Mynhardt, Universal fixers and regular graphs (submitted for publication)
[3] Goddard, W.; Raines, M. E.; Slater, P. J., Distance and connectivity measures in permutation graphs, Discrete Math., 271, 61-70 (2003) · Zbl 1022.05024
[4] Gu, W., On diameter of permutation graphs, Networks, 33, 161-166 (1999) · Zbl 0923.05023
[5] W. Gu, Personal communication to S.T. Hedetniemi, in: 30th South-Eastern Conference on Graph Theory and Combinatorics, Florida Atlantic University, USA, March 1999; W. Gu, Personal communication to S.T. Hedetniemi, in: 30th South-Eastern Conference on Graph Theory and Combinatorics, Florida Atlantic University, USA, March 1999
[6] Hartnell, B. L.; Rall, D. F., On dominating the Cartesian product of a graph and \(K_2\), Discuss. Math. Graph Theory, 24, 389-402 (2004) · Zbl 1063.05107
[7] Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of Domination in Graphs (1998), Marcel Dekker: Marcel Dekker New York · Zbl 0890.05002
[8] C.M. Mynhardt, Zhixia Xu, Domination in prisms of graphs: Universal fixers, Util. Math. (in press); C.M. Mynhardt, Zhixia Xu, Domination in prisms of graphs: Universal fixers, Util. Math. (in press) · Zbl 1284.05199
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.