On coherent configuration of circular-arc graphs

Document Type : Original paper

Authors

1 Department of Mathematics, University of Farhangian, Tabriz

2 Department of Mathematics, K. N. Toosi University of Technology, Tehran, Iran,

Abstract

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.

Keywords

Main Subjects

References

[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.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 27 September 2023

Files

Share

How to cite

Statistics