Exploring graphs where clique number meets coprime index

Articles in Press

Document Type : Original paper

Author

Sir Parashurambhau College (S. P. College), Savitribai Phule Pune University, Pune, India

Abstract

In this paper, an algorithmic approach is explored towards vertex coloring, coprime labeling, and coprime index of certain variant of the dot product graphs. The notion of coprime index $\mu(G)$ of a graph $G$ was introduced by Katre et al. This notion has interesting connections with the clique number $\omega(G)$, the intersection number $i(G)$ of $G$, and the edge-clique covering number $\theta_e(G^\complement)$ of the complement of the graph. Katre et al. posed a problem to characterize the graphs for which clique number and coprime index are equal, i.e., $\omega(G)=\mu(G)$.
In this paper, we provide a broader class of combinatorial graphs $G(R_n)$ satisfying this equality. With a slight modification, these graphs are the dot product graphs introduced by Badawi. The graph $G(R_n)$ is associated to a subset $R_n$ of the first octant of $\mathbb R^n$, instead of associating to a ring. This graph generalizes the Kneser graphs, the Boolean graphs, and more generally, the zero-divisor graph of the ring $\mathbb F_{q_1} \times \mathbb F_{q_2} \times \dots \times \mathbb F_{q_n}$. We first explore the structure of the graph $G(R_n)$ recursively using $G(R_{n-1})$. Then, we utilize it to obtain simple algorithms for the graph labelings such as vertex coloring and coprime labeling of these graphs, and show that these labelings are minimal. The chromatic number $\chi(G(R_n))$ and the coprime index $\mu(G(R_n))$ of $G(R_n)$ are determined. Consequently, we have the class of graphs $G(R_n)$ satisfying the equality: $ \omega(G(R_n))= \mu(G(R_n))=\chi (G(R_n))=\theta_e(G(R_n)^\complement)=i(G(R_n)^\complement)$.

Keywords

Main Subjects

References

[1] D.F. Anderson and P.S. Livingston, The zero-divisor graph of a commutative ring, J. Algebra 217 (1999), no. 2, 434–447.
https://doi.org/10.1006/jabr.1998.7840
[2] A. Badawi, On the dot product graph of a commutative ring, Comm. Algebra 43 (2015), no. 1, 43–50.
https://doi.org/10.1080/00927872.2014.897188
[3] I. Beck, Coloring of commutative rings, J. Algebra 116 (1988), no. 1, 208–226. https://doi.org/10.1016/0021-8693(88)90202-5
[4] P. Erdös, A.W. Goodman, and L. P´osa, The representation of a graph by set intersections, Canad. J. Math. 18 (1966), 106–112. https://doi.org/10.4153/CJM-1966-014-3
[5] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 6 (2022), no. 25, # DS6. https://doi.org/10.37236/27
[6] I. Holyer, The np-completeness of some edge-partition problems, SIAM J. Comput. 10 (1981), no. 4, 713–717. https://doi.org/10.1137/0210054
[7] G.S. Kadu, G. Sonawane, and Y.M. Borse, Reciprocal eigenvalue properties using the zeta and möbius functions, Linear Algebra Appl. 694 (2024), 186–205. https://doi.org/10.1016/j.laa.2024.04.010
[8] S.A. Katre, L. Yahyaei, and S. Arumugam, Coprime index of a graph, Electron. Notes Discrete Math. 60 (2017), 77–82.
https://doi.org/10.1016/j.endm.2017.06.011
[9] J.D. LaGrange, Boolean rings and reciprocal eigenvalue properties, Linear Algebra Appl. 436 (2012), no. 7, 1863–1871.
https://doi.org/10.1016/j.laa.2011.05.042
[10] C. Patil, N. Khandekar, and V. Joshi, On graphs with equal coprime index and clique number, AKCE Int. J. Graphs Comb. 20 (2023), no. 3, 235–243. https://doi.org/10.1080/09728600.2023.2218442
[11] F.S. Roberts, Applications of edge coverings by cliques, Discrete Appl. Math. 10 (1985), no. 1, 93–109. https://doi.org/10.1016/0166-218X(85)90061-7
[12] P.N. Shinde, S. Faruqi, and S.A. Katre, On set graphs, Bulletin of the ICA 88 (2020), 65–77.
[13] G. Sonawane, Pascal-type matrices and eigenvalues of zero-divisor graphs of reduced rings, Linear Multilinear Algebra 73 (2025), no. 14, 3331–3345. https://doi.org/10.1080/03081087.2025.2539336
[14] G. Sonawane, G.S. Kadu, and Y.M. Borse, Determinantal properties of boolean graphs using recursive approach, AKCE Int. J. Graphs Comb. 21 (2024), no. 1, 16–22. https://doi.org/10.1080/09728600.2023.2240865
[15] G. Sonawane, G.S. Kadu, and Y.M. Borse, Combinatorial approach to structural indices of zero-divisor graphs, Dis-
crete Math. Algorithms Appl. (2025), 2550035. https://doi.org/10.1142/S1793830925500351
[16] G. Sonawane, G.S. Kadu, and Y.M. Borse, Spectra of zero-divisor graphs of finite reduced rings, J. Algebra Appl.
24 (2025), no. 03, 2550082. https://doi.org/10.1142/S0219498825500823
[17] A. Tout, A.N. Dabboug, and K. Howalla, Prime labeling of graphs, Nat. Acad. Sci. Letters 11 (1982), 365-368.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 14 November 2025

Files

Share

How to cite

Statistics