Cycles and paths related vertex-equitable graphs (Q6580117)

A vertex \(\xi\) labeling of a graph \(\chi\) is referred to as a ``vertex equitable labeling'' (VEq) if the induced edge weights, obtained by summing the labels of the end vertices, satisfy the following condition: the absolute difference in the number of vertices \(v\) and \(u\) with labels \(\xi(v) = a\) and \(\xi(u) = b\) (where \(a, b \in Z\)) is approximately 1, considering a given set A that consists of the first \(\left\lceil \frac{q}{2}\right\rceil\) non-negative integers. A graph \(\chi\) that admits a vertex equitable labeling (VEq) is termed a `vertex equitable graph'.\N\NLet \(\chi\) be a \((p, q)\) graph with \(p\) vertices and \(q\) edges. In this context, a vertex labeling \(\xi\) assigns non-integers to the vertices of the graph. Several types of labelings have been extensively studied with detailed results in the literature, such as graceful, multiplicative, vertex equitable (VEq), harmonious, cordial, and prime labelings, among others. In some labelings, vertex labels induce edge labels, and a vertex labeling \(\xi\) is termed a `vertex-difference labeling' if it induces the label \(|\xi(x)-\xi(y)|\) for all edges \(xy \in E(\chi)\) which we call edge-weight \(wt_{xy}(\xi)\).\N\NA `\(k\)-equitable' labeling is a vertex-difference labeling where the appearance of edge-weights induced by \(\xi\) occurs exactly \(k\) times. \textit{G. S. Bloom} and \textit{S. Ruiz} [Discrete Appl. Math. 49, No. 1--3, 61--75 (1994; Zbl 0811.90107)] described the idea of extending vertex-difference labeling.\N\N\textit{M. Seenivasan} and \textit{A. Lourdusamy} [J. Discrete Math. Sci. Cryptography 11, No. 6, 727--735 (2008; Zbl 1178.05084)] introduced the concept of `vertex equitable labeling' (VEq) using the first \(\left\lceil \frac{q}{2}\right\rceil\) non-negative integers, i.e. \(Z= 0, 1, 2, \dots,\left\lceil \frac{q}{2}\right\rceil\) for vertices. In this labeling, the induced edge weights obtained by summing the end vertex labels satisfy the condition: the absolute difference in the number of vertices \(v\) and \(a\) with labels \(\xi(v) = a\) and \(\xi(u) = b\) for \(a, b \in Z\) is approximately 1. The proved results regarding vertex equitable graphs include paths \(P_{n}\), bi-star \(B(n,n)\), combs \(P_{n} \odot K_1\), bipartite complete \(K_{2,n}\), friendship graph \(C_{3}^{(t)}\) \(t \geq 2\) quadrilateral snake, \(K_{2} + mK_{1}\), \(K_{1, p} \cup K_{1,p+k}\), ladder graph \(L_{n}\), uniform subdivision of a path, and cycle \(C_{m}\) \(m \equiv 0 \text{ or } 3 \pmod{4}\). On the other hand, the proved results about graphs that are not vertex-equitable include \(K_{1,p}\), \(p\geq 4\), Eulerian graphs with \(p\) edges \(p \equiv 1 \text{ or } 2 \pmod{4}\), the wheel graph \(W_{p}\), the complete graph \(K_{p}\) \(p > 3\) and triangular cacti with \(q\) edges \(q \equiv 0\) or 6 or 9.\N\N\textit{A. Lourdusamy} and \textit{F. Patrick}, [Lect. Notes Comput. Sci. 10398, 134--143 (2017; Zbl 1496.05164)] observed that the graphs \(TL_{n}\), \(L_{n} \odot K_{1}\), \(Q_{n} \odot K_{1}\) and \(A(T_{n})\) admit VEq labeling. \textit{M. Acharya} et al. [Electron. Notes Discrete Math. 63, 461--468 (2017; Zbl 1383.05139)] introduced the concept of VEq labeling for signed graphs and observed the VEq behavior of signed paths, stars, and complete bipartite graphs \(K_{2,n}\). \N\textit{P. Jeyanthi} et al. [J. Sci. Res. 7, No. 3, 33--42 (2015; \url{doi:10.3329/jsr.v7i3.22810})] \Nprovided vertex equitable labeling of \(T \widehat{O} P_{n}\), \(T \widehat{O} 2P_{n}\), \(T \widehat{O} C_{n}\), \(T \widetilde{O} P_{n}\). \textit{P. Jeyanthi} et al. [Proyecciones 35, No. 2, 177--186 (2016; Zbl 1343.05131)] showed that \(KY(m, n)\), \(P(2,QS_{n})\), \(P(m,QS_{n})\), \(C(n, QS_{n})\), \(NQ(m)\), \(K_{1,n} \times P_{2}\) admit VEq labeling. Additionally, Jeyanthi et al. [2016, loc. cit.] demonstrated that \(D(T_{n})\) (where \(S(D(T_{n}))\) represents the subdivision of the double triangular snake), \(S(D(Q_{n}))\) where \(S(D(Q_{n}))\) is the subdivision of double quadrilateral snakes), \(S(DA(T_{n}))\) (where \(S(DA(T_{n}))\) denotes the subdivision of the double alternate triangular snake), \(DA (T_{m}) \odot nK_{1}\) and \(DA(Q_m) \odot nK_{1}\) are VEq. Furthermore, it is shown that Eulerian graphs with \(n\) edges, triangular cacti under certain conditions are VEq. They also proved that \(K_{2}+mK_{1}+K_{1,n} \cup K_{1,n+k}\) are vertex equitable if and only if \(k = 1, 2, 3\) They derived the following inequality as a criteria for determining not vertex equitable graphs:\N\[\Np < \left\lceil \frac{q} {2} \right\rceil + 2,\N\]\Nwhere \(p\) and \(q\) define the elements of the graph. \textit{P. Jeyanthi} et al. [J. Algebra Comb. Discrete Struct. Appl. 3, No. 2, 97--104 (2016; Zbl 1425.05141)] provided VEq labeling for \(J_{n}\) \((JF)_{n}\), \(BL(n,2,m)\) the corona product of ladder and the complement of the complete graph, and \(<L_{n} \widehat{O} K_{1,m}>\), while Jeyanthi et al. [2015, loc. cit.], proved that \(P_{m} \widetilde{O} n C_{4}\), \(C_{m} \widetilde{O} n C_{4}\) and \(L_{m} \widetilde{O} n C_{4}\) are VEq graphs. Jeyanthi et al. [Zbl 1425.05141, loc. cit.] gave VEq labeling for \(B_{n,n}^{2}\), \(C_{n1}^{2}, C_{n2}^{2},\dots,C_{nk}^{2}\), where each \(n_{i} \equiv 0 \pmod{4}\). They also proved that \(kC_{4}\) snakes, where \(k\) is greater than or equal to 1, are VEq, and \(kC_{n}\) vertex equitable under conditions.\N\NIn this paper, the authors demonstrate that graphs related to cycles and paths are examples of vertex-equitable graphs.\N\NThe paper is well written. There is an exhaustive bibliography.