Disproofs of two conjectures on no hole anti-\(n\)-labeling of graphs (Q2030247)

Let \(k\) be a positive integer. An anti-\(k\)-labeling of a graph \(G\) is a mapping from \(V(G)\) to \(\{1,2,\dots,k\}\). An anti-\(k\)-labeling of a graph \(G\) is called a no hole anti-\(k\)-labeling if the anti-\(k\)-labeling is surjective. For a no hole anti-\(k\)-labeling \(\xi\) of a graph \(G\), we define \(w_\xi(e)=|\xi(u)-\xi(v)|\) for any edge \(e=uv\) of \(G\), and \(w_\xi(G)= \min\{w_\xi(e): e\in E(G)\}\). The no hole anti-\(k\)-labeling number of a graph \(G\), denoted by \(\gamma_k^{nh}(G)\), is \(\max\{w_\xi(G):\xi\text{ is a no hole anti-\(k\)-labeling}\}\). In this note, the authors disprove two conjectures of their own. In particular, they show that the following two conjectures are false. Conjecture 1. For a tree \(T\) of order \(n\) with bipartition \((X_1, X_2)\), where \(|X_i|=q_i\), \(i=1,2\), we have \(\gamma_k^{nh}(T)= \min\{q_1, q_2\}\). Conjecture 2. Let \(G\) be the two-dimensional grid \(P_m\times P_n\), \(m\le n\). Then \(\gamma_{mn}^{nh}(G)=\lfloor\frac{mn-m}{2}\rfloor\). They also characterize graphs of order \(n\) for which the independence number and the no hole anti-\(n\)-labeling number are equal.