آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 121 |
| تعداد مقالات | 1,448 |
| تعداد مشاهده مقاله | 1,555,674 |
| تعداد دریافت فایل اصل مقاله | 1,459,762 |
Exploring graphs where clique number meets coprime index | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 23 آبان 1404 اصل مقاله (459.69 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2025.30573.2539 | ||
| نویسنده | ||
| Gahininath Sonawane* | ||
| Sir Parashurambhau College (S. P. College), Savitribai Phule Pune University, Pune, India | ||
| چکیده | ||
| 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)$. | ||
| کلیدواژهها | ||
| Graph labelings؛ dot product graph؛ chromatic number؛ coprime index؛ clique number | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 214 تعداد دریافت فایل اصل مقاله: 14 |
||