共查询到20条相似文献,搜索用时 15 毫秒
1.
Paul Terwilliger 《Journal of Combinatorial Theory, Series B》1982,32(2):182-188
It is shown that any bipartite distance-regular graph with finite valency k and at least one cycle is finite, with diameter d and girth g satisfying . In particular, the number of bipartite distance-regular graphs with fixed valency and girth is finite. 相似文献
2.
M. R. Alfuraidan 《Graphs and Combinatorics》2013,29(5):1151-1174
As a consequence of a famous theorem by Derek Smith, an unknown distance-transitive graph is either primitive of diameter at least two and valency at least three or is antipodal, bipartite, or both. In the imprimitive cases an unknown graph must have a primitive core of diameter at least two and valency at least three. It seems that the known list of primitive graphs is complete. Here, starting from earlier work by Hemmeter we find every bipartite distance-transitive double whose primitive halved is one of the known distance-transitive graphs of diameter two and valency at least three. 相似文献
3.
As a consequence of a famous theorem by Derek Smith, an unknown distance-transitive graph is either primitive of diameter at least two and valency at least three or is antipodal, bipartite, or both. In the imprimitive cases an unknown graph must have a primitive core of diameter at least two and valency at least three. It seems that the known list of primitive graphs is complete. Here, starting from an earlier work by Brouwer and Van Bon, we find every distance-transitive antipodal cover whose primitive quotient is one of the known distance-transitive graphs of diameter two and valency at least three. 相似文献
4.
A generic distance-regular graph is primitive of diameter at least two and valency at least three. We give a version of Derek Smith's famous theorem for reducing the classification of distance-regular graphs to that of primitive graphs. There are twelve cases—the generic case, four canonical imprimitive cases that reduce to the generic case, and seven exceptional cases. All distance-transitive graphs were previously known in six of the seven exceptional cases. We prove that the 6-cube is the only distance-transitive graph coming under the remaining exceptional case. 相似文献
5.
Hiroshi Suzuki 《Graphs and Combinatorics》2008,24(6):571-585
Many known distance-regular graphs have extra combinatorial regularities: One of them is t-homogeneity. A bipartite or almost bipartite distance-regular graph is 2-homogeneous if the number γ
i
= |{x | ∂(u, x) = ∂(v, x) = 1 and ∂(w, x) = i − 1}| (i = 2, 3,..., d) depends only on i whenever ∂(u, v) = 2 and ∂(u, w) = ∂(v, w) = i. K. Nomura gave a complete classification of bipartite and almost bipartite 2-homogeneous distance-regular graphs. In this
paper, we generalize Nomura’s results by classifying 2-homogeneous triangle-free distance-regular graphs. As an application,
we show that if Γ is a distance-regular graph of diameter at least four such that all quadrangles are completely regular then
Γ is isomorphic to a binary Hamming graph, the folded graph of a binary Hamming graph or the coset graph of the extended binary
Golay code of valency 24. We also consider the case Γ is a parallelogram-free distance-regular graph.
This research was partially supported by the Grant-in-Aid for Scientific Research (No.17540039), Japan Society of the Promotion
of Science. 相似文献
6.
J.H. Koolen 《Journal of Algebraic Combinatorics》1992,1(4):353-362
Terwilliger [15] has given the diameter bound d (s – 1)(k – 1) + 1 for distance-regular graphs with girth 2s and valency k. We show that the only distance-regular graphs with even girth which reach this bound are the hypercubes and the doubled Odd graphs. Also we improve this bound for bipartite distance-regular graphs. Weichsel [17] conjectures that the only distance-regular subgraphs of a hypercube are the even polygons, the hypercubes and the doubled Odd graphs and proves this in the case of girth 4. We show that the only distance-regular subgraphs of a hypercube with girth 6 are the doubled Odd graphs. If the girth is equal to 8, then its valency is at most 12. 相似文献
7.
Benjamin V. C. Collins 《Graphs and Combinatorics》1997,13(1):21-30
Let Γ be a distance-regular graph of diameterd≥3. For each vertexx of Γ, letT(x) denote the Terwilliger algebra for Γ with respect tox. An irreducibleT(x)-moduleW is said to bethin if dimE i * (x)W≤1 for 0≤i≤d, whereE i * (x) is theith dual idempotent for Γ with respect tox. The graph Γ isthin if for each vertexx of Γ, every irreducibleT(x)-module is thin. Aregular generalized quadrangle is a bipartite distance-regular graph with girth 8 and diameter 4. Our main results are as follows: Theorem. Let Γ=(X,R) be a distance-regular graph with diameter d≥3 and valency k≥3. Then the following are equivalent:
- Γis a regular generalized quadrangle.
- Γis thin and c 3=1.
8.
Qian Kong 《Discrete Mathematics》2010,310(24):3523-3527
Let Γ denote a distance-regular graph with a strongly closed regular subgraph Y. Hosoya and Suzuki [R. Hosoya, H. Suzuki, Tight distance-regular graphs with respect to subsets, European J. Combin. 28 (2007) 61-74] showed an inequality for the second largest and least eigenvalues of Γ in the case Y is of diameter 2. In this paper, we study the case when Γ is bipartite and Y is of diameter 3, and obtain an inequality for the second largest eigenvalue of Γ. Moreover, we characterize the distance-regular graphs with a completely regular strongly closed subgraph H(3,2). 相似文献
9.
M. A. Fiol 《Journal of Algebraic Combinatorics》2016,43(4):827-836
Let \(\Gamma \) be a distance-regular graph with diameter d and Kneser graph \(K=\Gamma _d\), the distance-d graph of \(\Gamma \). We say that \(\Gamma \) is partially antipodal when K has fewer distinct eigenvalues than \(\Gamma \). In particular, this is the case of antipodal distance-regular graphs (K with only two distinct eigenvalues) and the so-called half-antipodal distance-regular graphs (K with only one negative eigenvalue). We provide a characterization of partially antipodal distance-regular graphs (among regular graphs with \(d+1\) distinct eigenvalues) in terms of the spectrum and the mean number of vertices at maximal distance d from every vertex. This can be seen as a more general version of the so-called spectral excess theorem, which allows us to characterize those distance-regular graphs which are half-antipodal, antipodal, bipartite, or with Kneser graph being strongly regular. 相似文献
10.
In an earlier paper, the first two authors found all distance-regular antipodal covers of all known primitive distance-transitive graphs of diameter at least 3 with one possible exception. That remaining case is resolved here with the proof that a primitive and distance-transitive collinearity graph of a finite generalized 2d-gon with \(d\ge 3\) has no distance-regular antipodal cover of diameter 2d. 相似文献
11.
In this paper we will look at the relationship between the intersection number c 2 and the diameter of a distance-regular graph. We also give some tools to show that a distance-regular graph with large c 2 is bipartite, and a tool to show that if k D is too small then the distance-regular graph has to be antipodal. 相似文献
12.
Hiroshi Suzuki 《Journal of Algebraic Combinatorics》2018,48(3):369-404
A connected graph is said to be a completely regular clique graph with parameters (s, c), \(s, c \in {\mathbb {N}}\), if there is a collection \(\mathcal {C}\) of completely regular cliques of size \(s+1\) such that every edge is contained in exactly c members of \(\mathcal {C}\). It is known that many families of distance-regular graphs are completely regular clique graphs. In this paper, we determine completely regular clique graph structures, i.e., the choices of \(\mathcal {C}\), of all known families of distance-regular graphs with unbounded diameter. In particular, we show that all distance-regular graphs in this category are completely regular clique graphs except the Doob graphs, the twisted Grassmann graphs and the Hermitean forms graphs. We also determine parameters (s, c); however, in a few cases we determine only s and give a bound on the value c. Our result is a generalization of a series of works by J. Hemmeter and others who determined distance-regular graphs in this category that are bipartite halves of bipartite distance-regular graphs. 相似文献
13.
Let be a distance-regular graph of diameterd andi-th valencyk
i. We show that ifk
2 = kj for 2 +j d and 2 <j, then is a polygon (k = 2) or an antipodal 2-cover (k
d = 1). We also give a short proof of Terwilliger's inequality for bipartite distance-regular graphs and a refinement of Ivanov's argument on diameter bound. 相似文献
14.
We construct a bipartite distance-regular graph with intersection array {45, 44, 36, 5; 1, 9, 40, 45} and automorphism group 35 :(2 ×M10) (acting edge-transitively) and discuss its relation to previously known combinatorial structures. 相似文献
15.
A Gardiner 《Journal of Combinatorial Theory, Series B》1974,16(3):255-273
A graph of valency k with a group G of automorphisms may be studied via the action of G on the vertex set . If G acts transitively on , then the notions of primitivity and imprimitivity are meaningful. We consider a natural notion of “block system” for a general graph , which allows us to derive a “quotient” graph Γ whose vertices correspond to the blocks. The ideas are applied to antipodal systems in antipodal graphs: in particular we prove that for an antipodal distance-regular graph, the block size r cannot exceed the valency k; we further show that an antipodal distance-regular graph with r = k is (i) a circuit graph, (ii) a complete bipartite graph, or (iii) a threefold covering of Tutte's trivalent eight-cage. 相似文献
16.
We study 1-codes in distance-regular graphs of diameter 3 that achieve three different bounds. We show that the intersection array of a distance-regular graph containing such a code has the form $${\{a(p+1), cp, a+1; 1, c, a p\}\quad{\rm or}\quad\{a(p+1), (a+1)p,c; 1, c, a p\}}$$ for c =? c 2,?a =? a 3 and ${p = p_{33}^3}$ . These two families contain 10?+?15 known feasible intersection arrays out of which four are uniquely realized by the Sylvester graph, the Hamming graph H(3, 3), the Doro graph and the Johnson graph J(9, 3), but not all members of these two families are feasible. We construct four new one-parameter infinite subfamilies of feasible intersection arrays, two of which have a nontrivial vanishing Krein parameter: $${\{(2r^2-1)(2r+1), 4r(r^2-1), 2r^2; 1, 2(r^2-1), r(4r^2-2)\}}$$ and $${\{2r^2(2r+1), (2r-1)(2r^2+r+1), 2r^2; 1, 2r^2, r(4r^2-1)\}}$$ for r > 1 (the second family actually generalizes to a two-parameter family with the same property). Using this information we calculate some triple intersection numbers for these two families to show that they must contain the desired code. Finally, we use some additional combinatorial arguments to prove nonexistence of distance-regular graphs with such intersection arrays. 相似文献
17.
A connected graph of even order is called -extendable if it contains a perfect matching, and any matching of edges is contained in some perfect matching. The extendability of is the maximum such that is -extendable. Since its introduction by Plummer in the 1980s, this combinatorial parameter has been studied for many classes of interesting graphs. In 2005, Brouwer and Haemers proved that every distance-regular graph of even order is -extendable and in 2014, Cioabă and Li showed that any connected strongly regular graph of even order is 3-extendable except for a small number of exceptions.In this paper, we extend and generalize these results. We prove that all distance-regular graphs with diameter are 2-extendable and we also obtain several better lower bounds for the extendability of distance-regular graphs of valency that depend on , and , where is the number of common neighbors of any two adjacent vertices and is the number of common neighbors of any two vertices in distance two. In many situations, we show that the extendability of a distance-regular graph with valency grows linearly in . We conjecture that the extendability of a distance-regular graph of even order and valency is at least and we prove this fact for bipartite distance-regular graphs.In course of this investigation, we obtain some new bounds for the max-cut and the independence number of distance-regular graphs in terms of their size and odd girth and we prove that our inequalities are incomparable with known eigenvalue bounds for these combinatorial parameters. 相似文献
18.
The Hoffman-Singleton graph is the unique strongly regular graph with parameters (50, 7, 0, 1). A well-known hypothesis states that a distance-regular graph in which the neighborhood of each vertex is isomorphic to the Hoffman-Singleton graph has intersection array {50, 42, 1; 1, 2, 50} or {50, 42, 9; 1, 2, 42}. In the present paper, we prove this hypothesis under the assumption that a distance-regular graph is a Terwilliger graph and the graph diameter is at most 5. 相似文献
19.
Akira Hiraki 《Graphs and Combinatorics》2012,28(4):449-467
In this paper we study a distance-regular graph Γ of diameter d ≥? 3 which satisfies the following two conditions: (a) For any integer i with 1 ≤? i ≤? d ? 1 and for any pair of vertices at distance i in Γ there exists a strongly closed subgraph of diameter i containing them; (b) There exists a strongly closed subgraph Δ which is completely regular in Γ. It is known that if Δ has diameter 1, then Γ is a regular near polygon. We prove that if a strongly closed subgraph Δ of diameter j with 2 ≤? j ≤? d ? 1 is completely regular of covering radius d ? j in Γ, then Γ is either a Hamming graph or a dual polar graph. 相似文献
20.
A t-walk-regular graph is a graph for which the number of walks of given length between two vertices depends only on the distance between these two vertices, as long as this distance is at most t. Such graphs generalize distance-regular graphs and t-arc-transitive graphs. In this paper, we will focus on 1- and in particular 2-walk-regular graphs, and study analogues of certain results that are important for distance-regular graphs. We will generalize Delsarte?s clique bound to 1-walk-regular graphs, Godsil?s multiplicity bound and Terwilliger?s analysis of the local structure to 2-walk-regular graphs. We will show that 2-walk-regular graphs have a much richer combinatorial structure than 1-walk-regular graphs, for example by proving that there are finitely many non-geometric 2-walk-regular graphs with given smallest eigenvalue and given diameter (a geometric graph is the point graph of a special partial linear space); a result that is analogous to a result on distance-regular graphs. Such a result does not hold for 1-walk-regular graphs, as our construction methods will show. 相似文献