首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
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.  相似文献   

2.
For a distance-regular graph with second largest eigenvalue (resp., smallest eigenvalue) θ1 (resp., θD) we show that (θ1+1)(θD+1)?-b1 holds, where equality only holds when the diameter equals two. Using this inequality we study distance-regular graphs with fixed second largest eigenvalue.  相似文献   

3.
We characterize the distance-regular Ivanov-Ivanov-Faradjev graph from the spectrum, and construct cospectral graphs of the Johnson graphs, Doubled Odd graphs, Grassmann graphs, Doubled Grassmann graphs, antipodal covers of complete bipartite graphs, and many of the Taylor graphs. We survey the known results on cospectral graphs of the Hamming graphs, and of all distance-regular graphs on at most 70 vertices.  相似文献   

4.
A graph X is walk-regular if the vertex-deleted subgraphs of X all have the same characteristic polynomial. Examples of such graphs are vertex-transitive graphs and distance-regular graphs. We show that the usual feasibility conditions for the existence of a distance-regular graph with a given intersection array can be extended so that they apply to walk-regular graphs. Despite the greater generality, our proofs are more elementary than those usually given for distance-regular graphs. An application to the computation of vertex-transitive graphs is described.  相似文献   

5.
Distance-regular graphs are a key concept in Algebraic Combinatorics and have given rise to several generalizations, such as association schemes. Motivated by spectral and other algebraic characterizations of distance-regular graphs, we study ‘almost distance-regular graphs’. We use this name informally for graphs that share some regularity properties that are related to distance in the graph. For example, a known characterization of a distance-regular graph is the invariance of the number of walks of given length between vertices at a given distance, while a graph is called walk-regular if the number of closed walks of given length rooted at any given vertex is a constant. One of the concepts studied here is a generalization of both distance-regularity and walk-regularity called m-walk-regularity. Another studied concept is that of m-partial distance-regularity or, informally, distance-regularity up to distance m. Using eigenvalues of graphs and the predistance polynomials, we discuss and relate these and other concepts of almost distance-regularity, such as their common generalization of (?,m)-walk-regularity. We introduce the concepts of punctual distance-regularity and punctual walk-regularity as a fundament upon which almost distance-regular graphs are built. We provide examples that are mostly taken from the Foster census, a collection of symmetric cubic graphs. Two problems are posed that are related to the question of when almost distance-regular becomes whole distance-regular. We also give several characterizations of punctually distance-regular graphs that are generalizations of the spectral excess theorem.  相似文献   

6.
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.  相似文献   

7.
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.  相似文献   

8.
We investigate graphs G such that the line graph L(G) is hamiltonian connected if and only if L(G) is 3-connected, and prove that if each 3-edge-cut contains an edge lying in a short cycle of G, then L(G) has the above mentioned property. Our result extends Kriesell’s recent result in [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected line graph of a claw free graph is hamiltonian connected. Another application of our main result shows that if L(G) does not have an hourglass (a graph isomorphic to K5E(C4), where C4 is an cycle of length 4 in K5) as an induced subgraph, and if every 3-cut of L(G) is not independent, then L(G) is hamiltonian connected if and only if κ(L(G))≥3, which extends a recent result by Kriesell [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected hourglass free line graph is hamiltonian connected.  相似文献   

9.
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.  相似文献   

10.
We study the amply regular diameter d graphs Γ such that for some vertex a the set of vertices at distance d from a is the set of points of a 2-design whose set of blocks consists of the intersections of the neighborhoods of points with the set of vertices at distance d-1 from a. We prove that the subgraph induced by the set of points is a clique, a coclique, or a strongly regular diameter 2 graph. For diameter 3 graphs we establish that this construction is a 2-design for each vertex a if and only if the graph is distance-regular and for each vertex a the subgraph Γ3(a) is a clique, a coclique, or a strongly regular graph. We obtain the list of admissible parameters for designs and diameter 3 graphs under the assumption that the subgraph induced by the set of points is a Seidel graph. We show that some of the parameters found cannot correspond to distance-regular graphs.  相似文献   

11.
Suppose G is a connected, k-regular graph such that Spec(G)=Spec(Γ) where Γ is a distance-regular graph of diameter d with parameters a 1=a 2=⋯=a d−1=0 and a d>0; i.e., a generalized odd graph, we show that G must be distance-regular with the same intersection array as that of Γ in terms of the notion of Hoffman Polynomials. Furthermore, G is isomorphic to Γ if Γ is one of the odd polygon C 2d+1, the Odd graph O d+1, the folded (2d+1)-cube, the coset graph of binary Golay code (d=3), the Hoffman-Singleton graph (d=2), the Gewirtz graph (d=2), the Higman-Sims graph (d=2), or the second subconstituent of the Higman-Sims graph (d=2). Received: March 28, 1996 / Revised: October 20, 1997  相似文献   

12.
We construct two families of distance-regular graphs, namely the subgraph of the dual polar graph of type B 3(q) induced on the vertices far from a fixed point, and the subgraph of the dual polar graph of type D 4(q) induced on the vertices far from a fixed edge. The latter is the extended bipartite double of the former.  相似文献   

13.
We characterize the distance-regular graphs with diameter three by giving an expression for the number of vertices at distance two from each given vertex, in terms of the spectrum of the graph.  相似文献   

14.
For a poset P=(X,≤), the upper bound graph (UB-graph) of P is the graph U=(X,EU), where uvEU if and only if uv and there exists mX such that u,vm. For a graph G, the distance two graph DS2(G) is the graph with vertex set V(DS2(G))=V(G) and u,vV(DS2(G)) are adjacent if and only if dG(u,v)=2. In this paper, we deal with distance two graphs of upper bound graphs. We obtain a characterization of distance two graphs of split upper bound graphs.  相似文献   

15.
Distance-regular graphs of diameter three are of three (almost distinct) kinds: primitive, bipartite, and antipodal. An antipodal graph of diameter three is just an r-fold covering of a complete graph Kk+1 for some r?k. Its intersection array and spectrum are determined by the parameters r, k together with the number c of 2-arcs joining any two vertices at distance two. Most such graphs have girth three. In this note we consider antipodal distance-regular graphs of diameter three and girth ? 4. If r=2, then the only graphs are “Kk+1, k+1 minus a 1-factor.” We therefore assume r?3. The graphs with c=1 necessarily have r=k and were classified in lsqb3rsqb. We prove the inequality r?2>c12 (Theorem 2), list the feasible parameter sets when c=2 or 3 (Corollary 1), and conclude that every 3-fold or 4-fold antipodal covering of a complete graph has girth three (Corollary 2).  相似文献   

16.
In this paper, we study a conjecture of Andries E. Brouwer from 1996 regarding the minimum number of vertices of a strongly regular graph whose removal disconnects the graph into non-singleton components.We show that strongly regular graphs constructed from copolar spaces and from the more general spaces called Δ-spaces are counterexamples to Brouwer?s Conjecture. Using J.I. Hall?s characterization of finite reduced copolar spaces, we find that the triangular graphs T(m), the symplectic graphs Sp(2r,q) over the field Fq (for any q prime power), and the strongly regular graphs constructed from the hyperbolic quadrics O+(2r,2) and from the elliptic quadrics O(2r,2) over the field F2, respectively, are counterexamples to Brouwer?s Conjecture. For each of these graphs, we determine precisely the minimum number of vertices whose removal disconnects the graph into non-singleton components. While we are not aware of an analogue of Hall?s characterization theorem for Δ-spaces, we show that complements of the point graphs of certain finite generalized quadrangles are point graphs of Δ-spaces and thus, yield other counterexamples to Brouwer?s Conjecture.We prove that Brouwer?s Conjecture is true for many families of strongly regular graphs including the conference graphs, the generalized quadrangles GQ(q,q) graphs, the lattice graphs, the Latin square graphs, the strongly regular graphs with smallest eigenvalue −2 (except the triangular graphs) and the primitive strongly regular graphs with at most 30 vertices except for few cases.We leave as an open problem determining the best general lower bound for the minimum size of a disconnecting set of vertices of a strongly regular graph, whose removal disconnects the graph into non-singleton components.  相似文献   

17.
A matching covered graph is a non-trivial connected graph in which every edge is in some perfect matching. A non-bipartite matching covered graph G is near-bipartite if there are two edges e1 and e2 such that Ge1e2 is bipartite and matching covered. In 2000, Fischer and Little characterized Pfaffian near-bipartite graphs in terms of forbidden subgraphs [I. Fischer, C.H.C. Little, A characterization of Pfaffian near bipartite graphs, J. Combin. Theory Ser. B 82 (2001) 175-222.]. However, their characterization does not imply a polynomial time algorithm to recognize near-bipartite Pfaffian graphs. In this article, we give such an algorithm.We define a more general class of matching covered graphs, which we call weakly near-bipartite graphs. This class includes the near-bipartite graphs. We give a polynomial algorithm for recognizing weakly near-bipartite Pfaffian graphs. We also show that Fischer and Little’s characterization of near-bipartite Pfaffian graphs extends to this wider class.  相似文献   

18.
A connected graph is said to be a completely regular clique graph with parameters (sc), \(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 (sc); 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.  相似文献   

19.
Circulant graphs are an important class of interconnection networks in parallel and distributed computing. Integral circulant graphs play an important role in modeling quantum spin networks supporting the perfect state transfer as well. The integral circulant graph ICGn(D) has the vertex set Zn = {0, 1, 2, … , n − 1} and vertices a and b are adjacent if gcd(a − bn) ∈ D, where D ⊆ {d : dn, 1 ? d < n}. These graphs are highly symmetric, have integral spectra and some remarkable properties connecting chemical graph theory and number theory. The energy of a graph was first defined by Gutman, as the sum of the absolute values of the eigenvalues of the adjacency matrix. Recently, there was a vast research for the pairs and families of non-cospectral graphs having equal energies. Following Bapat and Pati [R.B. Bapat, S. Pati, Energy of a graph is never an odd integer, Bull. Kerala Math. Assoc. 1 (2004) 129-132], we characterize the energy of integral circulant graph modulo 4. Furthermore, we establish some general closed form expressions for the energy of integral circulant graphs and generalize some results from Ili? [A. Ili?, The energy of unitary Cayley graphs, Linear Algebra Appl. 431 (2009), 1881-1889]. We close the paper by proposing some open problems and characterizing extremal graphs with minimal energy among integral circulant graphs with n vertices, provided n is even.  相似文献   

20.
Brouwer, Godsil, Koolen and Martin [Width and dual width of subsets in polynomial association schemes, J. Combin. Theory Ser. A 102 (2003) 255-271] introduced the width w and the dual width w* of a subset in a distance-regular graph and in a cometric association scheme, respectively, and then derived lower bounds on these new parameters. For instance, subsets with the property w+w*=d in a cometric distance-regular graph with diameter d attain these bounds. In this paper, we classify subsets with this property in Grassmann graphs, bilinear forms graphs and dual polar graphs. We use this information to establish the Erd?s-Ko-Rado theorem in full generality for the first two families of graphs.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号