1,721,086 research outputs found
Distance-regular graphs with complete multipartite mu-graphs and AT4 family
No full textLet Gamma be an antipodal distance-regular graph of diameter 4, with eigenvalues theta(0) > theta(1) >theta(2) >theta(3) >theta(4). Then its Krein parameter q(11)(4) vanishes precisely when Gamma is tight in the sense of Jurisic, Koolen and Terwilliger, and furthermore, precisely when Gamma is locally strongly regular with nontrivial eigenvalues p :=theta(2) and - q :=theta(3). When this is the case, the intersection parameters of Gamma can be parametrized by p, q and the size of the antipodal classes r of Gamma. Let Gamma be an antipodal tight graph of diameter 4, denoted by AT4(p, q, r), and let the mu-graph be a graph that is induced by the common neighbours of two vertices at distance 2. Then we show that all the mu-graphs of Gamma are complete multipartite if and only if Gamma is AT4(sq, q, q) for some natural number s. As a consequence, we derive new existence conditions for graphs of the AT4 family whose mu-graphs are not complete multipartite. Another interesting application of our results is also that we were able to show that the mu-graphs of a distance-regular graph with the same intersection array as the Patterson graph are the complete bipartite graph K-4,K-4.X113sciescopu
A Higman-Haemers inequality for thick regular near polygons
No full textIn this note we will generalize the Higman-Haemers inequalities for generalized polygons to thick regular near polygons.X115sciescopu
Classification of the family AT4(qs, q, q) of antipodal tight graphs
No full textLet Gamma be an antipodal distance-regular graph with diameter 4 and eigenvalues theta(0) > theta(1) > theta(2) > theta(3) > theta(4). Then its Krein parameter q(11)(4) vanishes precisely when Gamma is tight in the sense of Jurisic, Koolen and Terwilliger, and furthermore, precisely when Gamma is locally strongly regular with nontrivial eigenvalues p := theta(2) and -q := theta(3). When this is the case, the intersection parameters of Gamma can be parameterized by p, q and the size of the antipodal classes r of Gamma, hence we denote Gamma by AT4(p, q, r). Jurisic conjectured that the AT4(p, q, r) family is finite and that, aside from the Conway-Smith graph, the Soicher2 graph and the 3.Fi(24)(-) graph, all graphs in this family have parameters belonging to one of the following four subfamilies: (i) q vertical bar p, r = q, (ii) q vertical bar p, r = 2, (iii) p = q - 2, r = q - 1, (iv) p = q - 2, r = 2. In this paper we settle the first subfamily. Specifically, we show that for a graph AT4(qs,q,q) there are exactly five possibilities for the pair (s, q), with an example for each: the Johnson graph J(8,4) for (1,2). the halved 8-cube for (2,2), the 3.O-6(-) (3) graph for (1,3), the Meixner2 graph for (2,4) and the 3.O-7 (3) graph for (3,3). The fact that the mu-graphs of the graphs in this subfamily are completely multipartite is very crucial in this paper. (C) 2010 Elsevier Inc. All rights reserved.X1165sciescopu
A note on regular near polygons
No full textLet Gamma be a regular near polygon of order (s, t) with s > 1 and t greater than or equal to 3. Let d be the diameter of Gamma, and let r : = max{i\ (c(i); a(i); b(i)) = (c(1); a(1); b(1))}: In this note we prove several inequalities for Gamma. In particular, we show that s is bounded from above by function in t if d < 3/2 (r + 1). We also consider regular near polygons of order (s, 3).X113sciescopu
A conjecture of Biggs concerning the resistance of a distance-regular graph
No full textBiggs conjectured that the resistance between any two points on a distance-regular graph of valency greater than 2 is bounded by twice the resistance between adjacent points. We prove this conjecture, give the sharp constant for the inequality, and display the graphs for which the conjecture most nearly fails. Some necessary background material is included, as well as some consequences.X111sciescopu
The regular near polygons of order (s,2)
No full textIn this note we classify the regular near polygons of order (s, 2).X112sciescopu
Triangle-free distance-regular graphs with an eigenvalue multiplicity equal to their valency and diameter 3
No full textIn this paper, triangle-free distance-regular graphs with diameter 3 and an eigenvalue theta with multiplicity equal to their valency are studied. Let Gamma be such a graph. We first show that theta = -1 if and only if Gamma is antipodal. Then we assume that the graph Gamma is primitive. We show that it is formally self-dual (and hence Q-polynomial and I-homogeneous), all its eigenvalues are integral, and the eigenvalue with multiplicity equal to the valency is either second largest or the smallest. Let x, y is an element of V Gamma be two adjacent vertices, and z is an element of Gamma(2)(x) boolean AND Gamma(2)(y). Then the intersection number tau(2) := vertical bar Gamma(z) boolean AND Gamma(3)(x) boolean AND Gamma(3)(y)vertical bar is independent of the choice of vertices x, y and z. In the case of the coset graph of the doubly truncated binary Golay code, we have b(2) = tau(2). We classify all the graphs with b(2) = tau(2) and establish that the just mentioned graph is the only example. In particular, we rule out an infinite family of otherwise feasible intersection arrays. (c) 2006 Elsevier Ltd. All rights reserved.X112sciescopu
On triangle-free distance-regular graphs with an eigenvalue multiplicity equal to the valency
No full textLet Gamma be a triangle-free distance-regular graph with diameter d >= 3, valency k >= 3 and intersection number a(2) not equal 0. Assume Gamma has an eigenvalue with multiplicity k. We show that Gamma is 1-homogeneous in the sense of Nomura when d = 3 or when d >= 4 and a(4) = 0. In the latter case we prove that r is an antipodal cover of a strongly regular graph, which means that it has diameter 4 or 5. For d = 5 the following infinite family of feasible intersection arrays: {2 mu(2) + mu, 2 mu(2) + mu -1, mu(2), mu,1; 1, mu, mu(2), 2 mu(2) + mu - 1, 2 mu(2) + mu}, mu is an element of N, is known. For mu = 1 the intersection array is uniquely realized by the dodecahedron. For mu = 1 we show that there are no distance-regular graphs with this intersection array. (c) 2007 Elsevier Ltd. All rights reserved.X114sciescopu
Triangle- and pentagon-free distance-regular graphs with an eigenvalue multiplicity equal to the valency
No full textWe classify triangle- and pentagon-free distance-regular graphs with diameter d >= 2, valency k, and an eigenvalue multiplicity k. In particular, we prove that such a graph is isomorphic to a cycle, a k-cube, a complete bipartite graph minus a matching, a Hadamard graph, a distance-regular graph with intersection array {k, k-1, k-c, c, 1; 1, c, k-c, k-1, k}, where k = gamma(gamma(2) + 3 gamma + 1), c = gamma(gamma + 1), gamma is an element of N, or a folded k-cube, k odd and k >= 7. This is a generalization of the results of Nomura (J. Combin. Theory Ser. B 64 (1995) 300-313) and Yamazaki (J. Combin. Theory Ser. B 66 (1996) 34-37), where they classified bipartite distance-regular graphs with an eigenvalue multiplicity k and showed that all such graphs are 2-homogeneous. We also classify bipartite almost 2-homogeneous distance-regular graphs with diameter d >=, 4. In particular, we prove that such a graph is either 2-homogeneous (and thus classified by Nomura and Yamazaki), or a folded k-cube for k even, or a generalized 2d-gon with order (1, k-1). (c) 2005 Elsevier Inc. All rights reserved.X116sciescopu
Optimal realizations of generic five-point metrics
No full textGiven a metric cl oil a finite set X, a realization of d is a triple (G, phi, omega) consisting of a graph G = (V, E), a labeling phi : X -> V, and a weighting omega : E -> R(>0) such that for all x, y is an element of X the length of any shortest path in G between phi(x) and phi(y) equals d(x, y). Such a realization is called optimal if parallel to G parallel to := Sigma(e is an element of E) omega(e) is minimal amongst all realizations of d. In this paper we will consider optimal realizations of generic five-point metric spaces. In particular, we show that there is a canonical subdivision C Of the metric fail of five-point metrics into cones such that (i) every metric d in the interior of a cone C is an element of C has a unique optimal realization (G, phi, omega), (ii) if d' is also in the interior of C with optimal realization (G', phi', omega') then (G, phi) and (G', phi') are isomorphic as labeled graphs, and (iii) any labeled graph that underlies all optimal realizations of the metrics in the interior of some cone C e C must belong to one of three isomorphism classes. (C) 2008 Elsevier Ltd. All rights reserved.X115sciescopu
- …
