[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A Characterization of Q-Polynomial Distance-Regular Graphs Using the Intersection Numbers

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

We consider a primitive distance-regular graph \(\varGamma \) with diameter at least 3. We use the intersection numbers of \(\varGamma \) to find a positive semidefinite matrix G with integer entries. We show that G has determinant zero if and only if \(\varGamma \) is Q-polynomial.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance-Regular Graphs. Springer, Berlin (1989)

    Book  MATH  Google Scholar 

  2. Hanson, E.: A characterization of Leonard pairs using the parameters \(\{a_i\}_{i=0}^d\). Linear Algebra Appl. 438, 2289–2305 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  3. Jurišić, A., Terwilliger, P., Žitnik, A.: The \(Q\)-polynomial idempotents of a distance-regular graph. J. Comb. Theory Ser. B 100, 683–690 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  4. Kurihara, H., Nozaki, H.: A characterization of \(Q\)-polynomial association schemes. J. Comb. Theory Ser. A 119, 57–62 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  5. Nomura, K., Terwilliger, P.: Tridiagonal matrices with nonnegative entries. Linear Algebra Appl. 434, 2527–2538 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  6. Pascasio, A.A.: A characterization of \(Q\)-polynomial distance-regular graphs. Discret. Math. 308, 3090–3096 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  7. Terwilliger, P.: A characterization of \(P\)- and \(Q\)-polynomial association schemes. J. Comb. Theory Ser. A 45, 8–26 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  8. Terwilliger, P.: A new inequality for distance-regular graphs. Discret. Math. 137, 319–332 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  9. Terwilliger, P.: The subconstituent algebra of an association scheme I. J. Algebraic Comb. 1, 363–388 (1992)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The author would like to thank Professor Paul Terwilliger for many valuable ideas and suggestions. This paper was written while the author was an Honorary Fellow at the University of Wisconsin-Madison supported by the Development and Promotion of Science and Technology Talents (DPST) Project, Thailand.

Author information

Authors and Affiliations

  1. Nakhon Pathom Rajabhat University, Nakhon Pathom, Thailand

    Supalak Sumalroj

Authors
  1. Supalak Sumalroj
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Supalak Sumalroj.

Electronic supplementary material

Below is the link to the electronic supplementary material.

Supplementary material 1 (mw 254 KB)

Appendices

Appendix 1

Recall the distance-regular graph \(\varGamma \) with diameter D. Recall for \(0\le h \le D\)

$$\begin{aligned} \begin{array}{lll} p^h_{1,h-1}=c_h, &{} \quad p^h_{1h}=a_h, &{} \quad p^h_{1,h+1}=b_h, \\ p^1_{h,h-1}=\dfrac{k_hc_h}{k}, &{} \quad p^1_{hh}=\dfrac{k_ha_h}{k}, &{} \quad p^1_{h,h+1}=\dfrac{k_hb_h}{k}.\\ \end{array} \end{aligned}$$

We now give \(p^h_{2j}\) for \(h-2\le j \le h+2\).

$$\begin{aligned}&p^h_{2,h-2}=\dfrac{c_{h-1}c_h}{c_2}, \\&p^h_{2,h-1}=\dfrac{c_h(a_{h-1}+a_h-a_1)}{c_2}, \\&p^h_{2h}= \dfrac{c_h(b_{h-1}-1)+a_h(a_h-a_1-1)+b_h(c_{h+1}-1)}{c_2}, \\&p^h_{2,h+1}= \dfrac{b_h(a_{h+1}+a_h-a_1)}{c_2}, \\&p^h_{2,h+2}= \dfrac{b_hb_{h+1}}{c_2}. \end{aligned}$$

We now give \(p^h_{3j}\) for \(h-3\le j \le h+3\).

$$\begin{aligned} p^h_{3,h-3}= & {} \dfrac{c_{h-2}c_{h-1}c_h}{c_2c_3},\\ p^h_{3,h-2}= & {} \dfrac{(a_h-a_2)c_{h-1}c_h}{c_2c_3}+\dfrac{c_{h-1}c_h(a_{h-2}+a_{h-1}-a_1)}{c_2c_3},\\ p^h_{3,h-1}= & {} \dfrac{c_{h-1}c_h(b_{h-2}-1)+c_ha_{h-1}(a_{h-1}-a_1-1)+c_hb_{h-1}(c_h-1)}{c_2c_3}\\&+\,\dfrac{c_h(a_h-a_2)(a_{h-1}+a_h-a_1)}{c_2c_3}+\dfrac{b_hc_hc_{h+1}}{c_2c_3}-\dfrac{b_1c_h}{c_3}, \\ p^h_{3h}= & {} \dfrac{c_hb_{h-1}(a_{h}+a_{h-1}-a_1)}{c_2c_3}\\&+\,\dfrac{(a_h-a_2)(c_h(b_{h-1}-1)+a_h(a_h-a_1-1)+b_h(c_{h+1}-1))}{c_2c_3}\\&+\,\dfrac{b_hc_{h+1}(a_h+a_{h+1}-a_1)}{c_2c_3}-\dfrac{b_1a_h}{c_3}, \\ p^h_{3,h+1}= & {} \dfrac{c_hb_{h-1}b_h}{c_2c_3} +\dfrac{b_h(a_h-a_2)(a_{h+1}+a_h-a_1)}{c_2c_3}\\&+\,\dfrac{b_h(c_{h+1}(b_h-1)+a_{h+1}(a_{h+1}-a_1-1)+b_{h+1}(c_{h+2}-1))}{c_2c_3}-\dfrac{b_1b_h}{c_3}, \\ p^h_{3,h+2}= & {} \dfrac{(a_h-a_2)b_hb_{h+1}}{c_2c_3} +\dfrac{b_hb_{h+1}(a_{h+2}+a_{h+1}-a_1)}{c_2c_3}, \\ p^h_{3,h+3}= & {} \dfrac{b_hb_{h+1}b_{h+2}}{c_2c_3}. \end{aligned}$$

Appendix 2

Recall the matrix G from Theorem 1. In this appendix we give G for \(D=3\).

Example 1

Assume \(D=3\). The rows and columns of G are indexed by the following matrices, in the specified order:

figure a

So the matrix G is \(12\times 12\). G has the form

$$\begin{aligned} G=\left[ \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} \mathbb {X} &{} 0 &{} 0 &{} \mathbb {S}_1 \\ 0 &{} \mathbb {Y} &{} 0 &{} \mathbb {S}_2 \\ 0 &{} 0 &{} \mathbb {Z} &{} \mathbb {S}_3 \\ \mathbb {S}_1 &{} \mathbb {S}_2 &{} \mathbb {S}_3 &{} \mathbb {W} \\ \end{array}\right] , \end{aligned}$$

where each block is a \(3\times 3\) symmetric matrix as shown below.

$$\begin{aligned} \mathbb {X}= & {} \left[ \begin{array}{c@{\quad }c@{\quad }c} 2k_3k &{} -2k_3c_3 &{} -2k_3a_3 \\ -2k_3c_3 &{} 2k_3(k_2-p^3_{22}) &{} -2k_3p^3_{23} \\ -2k_3a_3 &{} -2k_3p^3_{23} &{} 2k_3(k_3-p^3_{33}) \end{array}\right] ,\\ \mathbb {Y}= & {} \left[ \begin{array}{c@{\quad }c@{\quad }c} 2k_2(k-c_2) &{} -2k_2a_2 &{} -2k_2b_2 \\ -2k_2a_2 &{} 2k_2(k_2-p^2_{22}) &{} -2k_2p^2_{23} \\ -2k_2b_2 &{} -2k_2p^2_{23} &{} 2k_2(k_3-p^2_{33}) \end{array}\right] ,\\ \mathbb {Z}= & {} \left[ \begin{array}{c@{\quad }c@{\quad }c} 2k(k-a_1) &{} -2kb_1 &{} 0 \\ -2kb_1 &{} 2k(k_2-p^1_{22}) &{} -2kp^1_{23} \\ 0 &{} -2kp^1_{23} &{} 2k(k_3-p^1_{33}) \end{array}\right] ,\\ \mathbb {S}= & {} 2k_2 \left[ \begin{array}{ccc} a_1-c_2 &{} \quad b_1-a_2 &{}\quad -b_2 \\ b_1-a_2 &{}\quad p^1_{22}-p^2_{22} &{}\quad p^1_{23}-p^2_{23} \\ -b_2 &{}\quad p^1_{23}-p^2_{23} &{}\quad p^1_{33}-p^2_{33} \end{array}\right] , \end{aligned}$$

\(\mathbb {S}_1=b_2\mathbb {S}\), \(\mathbb {S}_2=a_2\mathbb {S}\) and \(\mathbb {S}_3=c_2\mathbb {S}\).

The matrix \(\mathbb {W}\) is symmetric with entries

$$\begin{aligned} {\mathbb W}_{11}= & {} 2(k^2k_2+(k_2a_1a_2-kb_1^2)a_1 +(k_2(c_2(b_1-1)+a_2(a_2-a_1-1)\\&+\,b_2(c_3-1))-k_2a_2^2)c_2),\\ {\mathbb W}_{12}= & {} 2((k_2a_1a_2-kb_1^2)b_1 +(k_2(c_2(b_1-1)+a_2(a_2-a_1-1)\\&+\,b_2(c_3-1)) -k_2a_2^2)a_2-k_3c_3^3),\\ {\mathbb W}_{13}= & {} 2((k_2(c_2(b_1-1)+a_2(a_2-a_1-1)+b_2(c_3-1))-k_2a_2^2)b_2-k_3c_3^2a_3),\\ {\mathbb W}_{22}= & {} 2(kk_2^2+(k_2a_1a_2-kb_1^2)p^1_{22} +(k_2(c_2(b_1-1)+a_2(a_2-a_1-1)\\&+\,b_2(c_3-1))-k_2a_2^2)p^2_{22}-k_3c_3^2p^3_{22}),\\ {\mathbb W}_{23}= & {} 2((k_2a_1a_2-kb_1^2)p^1_{23} +(k_2(c_2(b_1-1)+a_2(a_2-a_1-1)\\&+\,b_2(c_3-1))-k_2a_2^2)p^2_{23}-k_3c_3^2p^3_{23}),\\ {\mathbb W}_{33}= & {} 2(kk_2k_3+(k_2a_1a_2-kb_1^2)p^1_{33} +(k_2(c_2(b_1-1)+a_2(a_2-a_1-1)\\&+\,b_2(c_3-1))-k_2a_2^2)p^2_{33}-k_3c_3^2p^3_{33}). \end{aligned}$$

From Appendix 1, we find

$$\begin{aligned} p^1_{22}= & {} \dfrac{k_2a_2}{k},\quad p^2_{22}=\dfrac{c_2(b_1-1)+a_2(a_2-a_1-1)+b_2(c_3-1)}{c_2},\\ p^3_{22}= & {} \dfrac{c_3(a_2+a_3-a_1)}{c_2}, \\ p^1_{23}= & {} \dfrac{k_2b_2}{k},\quad p^2_{23}=\dfrac{b_2(a_3+a_2-a_1)}{c_2},\\ p^3_{23}= & {} \dfrac{c_3(b_2-1)+a_3(a_3-a_1-1)-b_3}{c_2}, \\ p^1_{33}= & {} \dfrac{k_3a_3}{k},\quad p^2_{33}=\dfrac{b_2(c_3(b_2-1)+a_3(a_3-a_1-1)-b_3)}{c_2c_3}, \\ p^3_{33}= & {} \dfrac{c_3b_{2}(a_3+a_2-a_1)}{c_2c_3} +\dfrac{(a_3-a_2)(c_3(b_2-1)+a_3(a_3-a_1-1)-b_3)}{c_2c_3}\\&-\,\dfrac{b_1a_3}{c_3}. \end{aligned}$$

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sumalroj, S. A Characterization of Q-Polynomial Distance-Regular Graphs Using the Intersection Numbers. Graphs and Combinatorics 34, 863–877 (2018). https://doi.org/10.1007/s00373-018-1917-5

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-018-1917-5

Keywords

Mathematics Subject Classification

Search

Navigation