The distance-regular graphs with valency k≥2, diameter D≥3 and k_D-1+k_D@?2k

North-Holland Pub. Co ; Elsevier Science Ltd 2017 Discrete mathematics Vol.340 No.3

<P>Let Gamma be a distance-regular graph with valency k and diameter D, and let x be a vertex of Gamma. We denote by k(i) (0 <= i <= D) the number of vertices at distance i from x. In this paper, we try to quantify the difference between antipodal and non-antipodal distance-regular graphs. We will look at the sum k(D-1) + k(D) and consider the situation where k(D-1) + k(D) <= 2k. If Gamma is an antipodal distance-regular graph, then k(D-1) + k(D) = k(D)(k + 1). It follows that either k(D) = 1 or the graph is non-antipodal. And for a non-antipodal distance-regular graph, it was known that k(D)(k(D-1)) >= k and k(D-1) >= k both hold. So, this paper concerns on obtaining more detailed information on the number of vertices for a non-antipodal distance-regular graph. We first concentrate on the case where the diameter equals three. In this case, the condition k(D) + k(D-1) <= 2k is equivalent to the condition that the number of vertices is at most 3k + 1. And we extend this result to all diameters. We note that although the result of the diameter 3 case is a corollary of the result of all diameters, the main difficulty is the diameter 3 case, and that the diameter 3 case confirms the following conjecture: there is no primitive distance-regular graph with diameter 3 having the M-property. (C) 2016 Elsevier B.V. All rights reserved.</P>

On the Wiener index, distance cospectrality and transmission-regular graphs

Abiad, A.,Brimkov, B.,Erey, A.,Leshock, L.,Martinez-Rivera, X.,O, S.,Song, S.Y.,Williford, J. Elsevier BV, North-Holland 2017 Discrete Applied Mathematics Vol.230 No.-

In this paper, we investigate various algebraic and graph theoretic properties of the distance matrix of a graph. Two graphs are D-cospectral if their distance matrices have the same spectrum. We construct infinite pairs of D-cospectral graphs with different diameter and different Wiener index. A graph is k-transmission-regular if its distance matrix has constant row sum equal to k. We establish tight upper and lower bounds for the row sum of a k-transmission-regular graph in terms of the number of vertices of the graph. Finally, we determine the Wiener index and its complexity for linear k-trees, and obtain a closed form for the Wiener index of block-clique graphs in terms of the Laplacian eigenvalues of the graph. The latter leads to a generalization of a result for trees which was proved independently by Mohar and Merris.

An inequality involving the second largest and smallest eigenvalue of a distance-regular graph

Koolen, Jack H.,Park, Jongyook,Yu, Hyonju Elsevier 2011 Linear algebra and its applications Vol.434 No.12

<P><B>Abstract</B></P><P>For a distance-regular graph with second largest eigenvalue (resp., smallest eigenvalue) <SUB>θ1</SUB> (resp., <SUB>θD</SUB>) we show that (<SUB>θ1</SUB>+1)(<SUB>θD</SUB>+1)⩽-<SUB>b1</SUB> holds, where equality only holds when the diameter equals two. Using this inequality we study distance-regular graphs with fixed second largest eigenvalue.</P>

A Relationship between the Second Largest Eigenvalue and Local Valency of an Edge-regular Graph

Park, Jongyook Department of Mathematics 2021 Kyungpook mathematical journal Vol.61 No.3

For a distance-regular graph with valency k, second largest eigenvalue r and diameter D, it is known that r ≥ $min\{\frac{{\lambda}+\sqrt{{\lambda}^2+4k}}{2},\;a_3\}$ if D = 3 and r ≥ $\frac{{\lambda}+\sqrt{{\lambda}^2+4k}}{2}$ if D ≥ 4, where λ = a₁. This result can be generalized to the class of edge-regular graphs. For an edge-regular graph with parameters (v, k, λ) and diameter D ≥ 4, we compare $\frac{{\lambda}+\sqrt{{\lambda}^2+4k}}{2}$ with the local valency λ to find a relationship between the second largest eigenvalue and the local valency. For an edge-regular graph with diameter 3, we look at the number $\frac{{\lambda}-\bar{\mu}+\sqrt{({\lambda}-\bar{\mu})^2+4(k-\bar{\mu})}}{2}$, where $\bar{\mu}=\frac{k(k-1-{\lambda})}{v-k-1}$, and compare this number with the local valency λ to give a relationship between the second largest eigenvalue and the local valency. Also, we apply these relationships to distance-regular graphs.

Geometric distance-regular graphs without 4-claws

North Holland [etc.] 2013 Linear algebra and its applications Vol.438 No.1

A non-complete distance-regular graph Γ is called geometric if there exists a set C of Delsarte cliques such that each edge of Γ lies in a unique clique in C. In this paper we determine the non-complete distance-regular graphs satisfying 3,83(a<SUB>1</SUB>+1)<k<4a<SUB>1</SUB>+10-6c<SUB>2</SUB>. To prove this result, we first show by considering non-existence of 4-claws that any non-complete distance-regular graph satisfying 3,83(a<SUB>1</SUB>+1)<k<4a<SUB>1</SUB>+10-6c<SUB>2</SUB> is a geometric distance-regular graphs smallest eigenvalue -3. Moreover, we classify the geometric distance-regular graphs with smallest eigenvalue -3. As an application, two feasible intersection arrays in the list of [7, Chapter 14] are ruled out.

AN UPPER BOUND ON THE CHEEGER CONSTANT OF A DISTANCE-REGULAR GRAPH

Kim, Gil Chun,Lee, Yoonjin Korean Mathematical Society 2017 대한수학회보 Vol.54 No.2

We present an upper bound on the Cheeger constant of a distance-regular graph. Recently, the authors found an upper bound on the Cheeger constant of distance-regular graph under a certain restriction in their previous work. Our new bound in the current paper is much better than the previous bound, and it is a general bound with no restriction. We point out that our bound is explicitly computable by using the valencies and the intersection matrix of a distance-regular graph. As a major tool, we use the discrete Green's function, which is defined as the inverse of ${\beta}$-Laplacian for some positive real number ${\beta}$. We present some examples of distance-regular graphs, where we compute our upper bound on their Cheeger constants.

An upper bound on the Cheeger constant of a distance-regular graph

김길천,이윤진 대한수학회 2017 대한수학회보 Vol.54 No.2

We present an upper bound on the Cheeger constant of a distance-regular graph. Recently, the authors found an upper bound on the Cheeger constant of distance-regular graph under a certain restriction in their previous work. Our new bound in the current paper is much better than the previous bound, and it is a general bound with no restriction. We point out that our bound is explicitly computable by using the valencies and the intersection matrix of a distance-regular graph. As a major tool, we use the discrete Green's function, which is defined as the inverse of $\beta$-Laplacian for some positive real number $\beta$. We present some examples of distance-regular graphs, where we compute our upper bound on their Cheeger constants.

2-Walk-regular graphs with a small number of vertices compared to the valency

Qiao, Z.,Koolen, J.H.,Park, J. North Holland [etc.] 2016 Linear algebra and its applications Vol.510 No.-

<P>In 2013, it was shown that, for a given real number alpha > 2, there are only finitely many distance-regular graphs Gamma with valency k and diameter D >= 3 having at most alpha k vertices, except for the following two cases: (i) D = 3 and Gamma is imprimitive; (ii) D = 4 and Gamma is antipodal and bipartite. In this paper, we will generalize this result to 2-walk-regular graphs. In this case, also incidence graphs of certain group divisible designs appear. (C) 2016 Elsevier Inc. All rights reserved.</P>

Partially metric association schemes with a multiplicity three

van Dam, Edwin R.,Koolen, Jack H.,Park, Jongyook Elsevier 2018 Journal of combinatorial theory. Series B Vol.130 No.-

<P><B>Abstract</B></P> <P>An association scheme is called partially metric if it has a connected relation whose distance-two relation is also a relation of the scheme. In this paper we determine the symmetric partially metric association schemes with a multiplicity three. Besides the association schemes related to regular complete 4-partite graphs, we obtain the association schemes related to the Platonic solids, the bipartite double scheme of the dodecahedron, and three association schemes that are related to well-known 2-arc-transitive covers of the cube: the Möbius–Kantor graph, the Nauru graph, and the Foster graph F048A. In order to obtain this result, we also determine the symmetric association schemes with a multiplicity three and a connected relation with valency three. Moreover, we construct an infinite family of cubic arc-transitive 2-walk-regular graphs with an eigenvalue with multiplicity three that give rise to non-commutative association schemes with a symmetric relation of valency three and an eigenvalue with multiplicity three.</P>

A Cheeger inequality of a distance regular graph using Green's function

Kim, G.C.,Lee, Y. North-Holland Pub. Co ; Elsevier Science Ltd 2013 Discrete mathematics Vol.313 No.20

We give a Cheeger inequality of distance regular graphs in terms of the smallest positive eigenvalue of the Laplacian and a value α<SUB>d</SUB> which is defined using q-numbers. We can approximate α<SUB>d</SUB> with arbitrarily small positive error β. The method is to use a Green's function, which is the inverse of the β-Laplacian.