آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 125 |
| تعداد مقالات | 1,584 |
| تعداد مشاهده مقاله | 1,747,040 |
| تعداد دریافت فایل اصل مقاله | 1,624,023 |
On coherent configuration of circular-arc graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 1، دوره 10، شماره 1، خرداد 2025، صفحه 1-19 اصل مقاله (450.96 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2023.28816.1735 | ||
| نویسندگان | ||
| Fatemeh Raei Barandagh* 1؛ Amir Rahnamai Barghi2 | ||
| 1Department of Mathematics Education, Farhangian University, P.O. Box 14665-889, Tehran, Iran | ||
| 2Department of Mathematics, K. N. Toosi University of Technology, Tehran, Iran | ||
| چکیده | ||
| For any graph, Weisfeiler and Leman assigned the smallest matrix algebra which contains the adjacency matrix of the graph. The coherent configuration underlying this algebra for a graph $\Gamma$ is called the coherent configuration of $\Gamma$, denoted by $\mathcal{X}(\Gamma)$. In this paper, we study the coherent configuration of circular-arc graphs. We give a characterization of the circular-arc graphs $\Gamma$, where $\mathcal{X}(\Gamma)$ is a homogeneous coherent configuration. Moreover, all homogeneous coherent configurations which are obtained in this way are characterized as a subclass of Schurian coherent configurations. | ||
| کلیدواژهها | ||
| coherent configuration؛ homogeneous؛ circular-arc graph؛ wreath product | ||
| مراجع | ||
|
[1] J.A. Bondy and U.S.R. Murty, Graph Theory, Springer, New York, 2008.
[2] S. Chakraborty and S. Jo, Compact representation of interval graphs and circulararc graphs of bounded degree and chromatic number, Theor. Comput. Sci. 941 (2023), 156–166. https://doi.org/10.1016/j.tcs.2022.11.010
[3] G. Chen and I. Ponomarenko, Tensor products of coherent configurations, Front. Math. 17 (2022), 1–24. https://doi.org/10.1007/s11464–021–0975–9
[4] G. Durán and M.C. Lin, On some subclasses of circular-arc graphs, Congr. Numer. 146 (2000), 201–212.
[5] S. Evdokimov and I. Ponomarenko, Permutation group approach to association schemes, European J. Comb. 30 (2009), no. 6, 1456–1476. https://doi.org/10.1016/j.ejc.2008.11.005
[6] S. Evdokimov, I. Ponomarenko, and G. Tinhofer, Forestal algebras and algebraic forests (on a new class of weakly compact graphs), Discrete Math. 225 (2000), no. 1-3, 149–172. https://doi.org/10.1016/S0012–365X(00)00152–7
[7] D.G. Higman, Coherent configurations I, Rend. Mat. Sem. Padova. 44 (1970), 1–25.
[8] M.C. Lin and J.L. Szwarcfiter, Characterizations and recognition of circular-arc graphs and subclasses: A survey, Discrete Math. 309 (2009), no. 18, 5618–5635. https://doi.org/10.1016/j.disc.2008.04.003
[9] R.M. McConnell, Linear-time recognition of circular-arc graphs, Algorithmica 37 (2003), 93–147. https://doi.org/10.1007/s00453–003–1032–7
[10] A. Tucker, Characterizing circular-arc graphs, Bull. Amer. Math. Soc. 76 (1970), no. 6, 1257–1260.
[11] A. Tucker, Structure theorems for some circular-arc graphs, Discrete Math. 7 (1974), no. 1-2, 167–195. https://doi.org/10.1016/S0012–365X(74)80027–0
[12] A. Tucker, An efficient test for circular-arc graphs, SIAM J. Comput. 9 (1980), no. 1, 1–24. https://doi.org/10.1137/0209001
[13] B. Weisfeiler, On construction and identification of graphs, vol. 558, Springer Lecture Notes, 1976.
[14] P.H. Zieschang, Theory of Association Schemes, Springer Science & Business Media, 2005. | ||
|
آمار تعداد مشاهده مقاله: 565 تعداد دریافت فایل اصل مقاله: 1,994 |
||