A spectral characterization of the \(s\)-clique extension of the triangular graphs. (English) Zbl 1433.05212
Summary: A regular graph is co-edge regular if there exists a constant \(\mu\) such that any two distinct and non-adjacent vertices have exactly \(\mu\) common neighbors. In this paper, we show that for integers \(s \geq 2\) and \(n\) large enough, any co-edge-regular graph which is cospectral with the \(s\)-clique extension of the triangular graph \(T (n)\) is exactly the \(s\)-clique extension of the triangular graph \(T (n)\).
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C75 | Structural characterization of families of graphs |
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
References:
| [1] | A.E. Brouwer, A.M. Cohen and A. Neumaier, Distance-Regular Graphs (Springer-Verlag, Berlin, 1989). doi:10.1007/978-3-642-74341-2 · Zbl 0747.05073 |
| [2] | A.E. Brouwer and W.H. Haemers, Spectra of Graphs (Springer, Heidelberg, 2012). doi:10.1007/978-1-4614-1939-6 · Zbl 1231.05001 |
| [3] | L.C. Chang, The uniqueness and non-uniqueness of the triangular association scheme, Sci. Record 3 (1959) 604-613. · Zbl 0089.15102 |
| [4] | S. Hayat, J.H. Koolen and M. Riaz, A spectral characterization of the s-clique extension of the square grid graphs, European J. Combin. 76 (2019) 104-116. doi:10.1016/j.ejc.2018.09.009 · Zbl 1402.05166 |
| [5] | C.D. Godsil, G. Royle, Algebraic Graph Theory (Springer-Verlag, Berlin, 2001). doi:10.1007/978-1-4613-0163-9 · Zbl 0968.05002 |
| [6] | W.H. Haemers, Interlacing eigenvalues and graphs, Linear Algebra Appl. 226-228 (1995) 593-616. doi:10.1016/0024-3795(95)00199-2 · Zbl 0831.05044 |
| [7] | A.J. Hoffman, On the polynomial of a graph, Amer. Math. Monthly 70 (1963) 30-36. doi:10.1080/00029890.1963.11990038 · Zbl 0112.14901 |
| [8] | J.H. Koolen, B. Gebremichel and J.Y. Yang, Sesqui-regular graphs with fixed smallest eigenvalue. https://arxiv.org/abs/1904.01274v1 · Zbl 1512.05269 |
| [9] | P. Terwilliger, Algebraic Graph Theory, Lecture Notes, unpublished. https://icu-hsuzuki.github.io/lecturenote/ |
| [10] | E.R. van Dam, Regular graphs with four eigenvalues, Linear Algebra Appl. 226-228 (1995) 139-162. doi:10.1016/0024-3795(94)00346-F · Zbl 0839.05072 |
| [11] | E.R. van Dam, J.H. Koolen and H. Tanaka, Distance-regular graphs, Electron. J. Combin. (2016) #DS22. · Zbl 1335.05062 |
| [12] | J.Y. Yang and J.H. Koolen, On the order of regular graphs with fixed second largest eigenvalue. http://arxiv.org/abs/1809.01888v1 · Zbl 1458.05160 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
