共查询到20条相似文献,搜索用时 62 毫秒
1.
《Discrete Mathematics》2022,345(5):112787
In this paper, we study the problem that which of distance-regular graphs admit a perfect 1-code. Among other results, we characterize distance-regular line graphs which admit a perfect 1-code. Moreover, we characterize all known distance-regular graphs with small valency at most 4, the distance-regular graphs with known putative intersection arrays for valency 5, and all distance-regular graphs with girth 3 and valency 6 or 7 which admit a perfect 1-code. 相似文献
2.
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. 相似文献
3.
Manley Perkel Cheryl E. Praeger Richard Weiss 《Journal of Algebraic Combinatorics》2001,13(3):257-273
A connected graph of girth m 3 is called a polygonal graph if it contains a set of m-gons such that every path of length two is contained in a unique element of the set. In this paper we investigate polygonal graphs of girth 6 or more having automorphism groups which are transitive on the vertices and such that the vertex stabilizers are 3-homogeneous on adjacent vertices. We previously showed that the study of such graphs divides naturally into a number of substantial subcases. Here we analyze one of these cases and characterize the k-valent polygonal graphs of girth 6 which have automorphism groups transitive on vertices, which preserve the set of special hexagons, and which have a suborbit of size k – 1 at distance three from a given vertex. 相似文献
4.
Méziane Aïder 《Discrete Mathematics》2009,309(22):6402-6407
Isometric subgraphs of hypercubes are known as partial cubes. These graphs have first been investigated by Graham and Pollack [R.L. Graham, H. Pollack, On the addressing problem for loop switching, Bell System Technol. J. 50 (1971) 2495-2519; and D. Djokovi?, Distance preserving subgraphs of hypercubes, J. Combin. Theory Ser. B 14 (1973) 263-267]. Several papers followed with various characterizations of partial cubes. In this paper, we determine all subdivisions of a given configuration which can be embedded isometrically in the hypercube. More specifically, we deal with the case where this configuration is a connected graph of order 4, a complete graph of order 5 and the case of a k-fan Fk(k≥3). 相似文献
5.
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. 相似文献
6.
Let be a distance-regular graph of valencyk 3 and diameterd. Suppose the intersection array hast columns different from
t
(1, 0,k – 1). Then it is shown thatd is bounded from above by a certain functionf(k, t) depending only onk andt. As an application, this theorem eliminates certain cubic distance-regular graphs to complete the classification of such graphs by Biggs et al.Supported in part by NSF grant MCS-8301826 and by the British SERC grant. 相似文献
7.
Fan R. K. Chung 《Journal of Graph Theory》1992,16(3):273-286
We investigate several Ramsey-Turán type problems for subgraphs of a hypercube. We obtain upper and lower bounds for the maximum number of edges in a subgraph of a hypercube containing no four-cycles or more generally, no 2k-cycles C2k. These extermal results imply, for example, the following Ramsey theorems for hypercubes: A hypercube can always be edge-partitioned into four subgraphs, each of which contains no six-cycle. However, for any integer t, if the n-cube is edge-partitioned into t sub-graphs, then one of the subgraphs must contain an edight-cycle, provided only than n is sufficiently large (depending only on t). 相似文献
8.
Paul Terwilliger 《Journal of Combinatorial Theory, Series B》1983,34(2):151-164
A diameter-bound theorem for a class of distance-regular graphs which includes all those with even girth is presented. A new class of graphs, called (s, c, a, k)-graphs, is introduced, which are conjectured to contain enough of the local structure of finite distance-regular graphs for them all to be finite. It is proved that they are finite and a bound on the diameter is given in the case a ≤ c. 相似文献
9.
Maya Jakobine Stein 《Journal of Graph Theory》2007,54(4):331-349
A theorem of Mader states that highly connected subgraphs can be forced in finite graphs by assuming a high minimum degree. We extend this result to infinite graphs. Here, it is necessary to require not only high degree for the vertices but also high vertex‐degree (or multiplicity) for the ends of the graph, that is, a large number of disjoint rays in each end. We give a lower bound on the degree of vertices and the vertex‐degree of the ends which is quadratic in k, the connectedness of the desired subgraph. In fact, this is not far from best possible: we exhibit a family of graphs with a degree of order 2k at the vertices and a vertex‐degree of order k log k at the ends which have no k‐connected subgraphs. Furthermore, if in addition to the high degrees at the vertices, we only require high edge‐degree for the ends (which is defined as the maximum number of edge‐disjoint rays in an end), Mader's theorem does not extend to infinite graphs, not even to locally finite ones. We give a counterexample in this respect. But, assuming a lower bound of at least 2k for the edge‐degree at the ends and the degree at the vertices does suffice to ensure the existence (k + 1)‐edge‐connected subgraphs in arbitrary graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 331–349, 2007 相似文献
10.
Anna Kasikova 《Journal of Algebraic Combinatorics》1997,6(3):247-252
In [3] Cameron et al. classified strongly regular graphs with strongly regular subconstituents. Here we prove a theorem which implies that distance-regular graphs with strongly regular subconstituents are precisely the Taylor graphs and graphs with a
1 = 0 and a
i {0,1} for i = 2,...,d. 相似文献
11.
A. D. Korshunov 《Mathematical Notes》1971,9(3):155-160
LetG(n) be the set of all nonoriented graphs with n enumerated points without loops or multiple lines, and let vk(G) be the number of mutually nonisomorphic k-point subgraphs of G G(n). It is proved that at least |G(n)| (1–1/n) graphs G G(n) possess the following properties: a) for any k [6log2n], where c=–c log2c–(1–c)×log2(1–c) and c>1/2, we havev
k(G) > C
n
k
(1–1/n2); b) for any k [cn + 5 log2n] we havev
k(G) = C
n
k
. Hence almost all graphs G G(n) containv(G) 2n pairwise nonisomorphic subgraphs.Translated from Matematicheskie Zametki, Vol. 9, No. 3, pp. 263–273, March, 1971. 相似文献
12.
Abdelhafid Berrachedi Ivan Havel Henry Martyn Mulder 《Czechoslovak Mathematical Journal》2003,53(2):295-309
The main subject of our study are spherical (weakly spherical) graphs, i.e. connected graphs fulfilling the condition that in each interval to each vertex there is exactly one (at least one, respectively) antipodal vertex. Our analysis concerns properties of these graphs especially in connection with convexity and also with hypercube graphs. We deal e.g. with the problem under what conditions all intervals of a spherical graph induce hypercubes and find a new characterization of hypercubes: G is a hypercube if and only if G is spherical and bipartite. 相似文献
13.
The homogeneous, monotonic, P-polynomial table algebras with valency k ≥ 2 are classified. It is also determined which of these algebras, when integral, have integer multiplicities. In particular, it is shown that all multiplicities are integers only if k = 2 or the diameter d = 2. Some of these algebras come from distance-regular graphs, and some do not. 相似文献
14.
Boštjan Brešar Jérémie Chalopin Victor Chepoi Matjaž Kovše Arnaud Labourel Yann Vaxès 《Journal of Graph Theory》2013,73(2):161-180
In this article, we characterize the graphs G that are the retracts of Cartesian products of chordal graphs. We show that they are exactly the weakly modular graphs that do not contain K2, 3, the 4‐wheel minus one spoke , and the k‐wheels (for as induced subgraphs. We also show that these graphs G are exactly the cage‐amalgamation graphs as introduced by Bre?ar and Tepeh Horvat (Cage‐amalgamation graphs, a common generalization of chordal and median graphs, Eur J Combin 30 (2009), 1071–1081); this solves the open question raised by these authors. Finally, we prove that replacing all products of cliques of G by products of Euclidean simplices, we obtain a polyhedral cell complex which, endowed with an intrinsic Euclidean metric, is a CAT(0) space. This generalizes similar results about median graphs as retracts of hypercubes (products of edges) and median graphs as 1‐skeletons of CAT(0) cubical complexes. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 161–180, 2013 相似文献
15.
In this paper, we study different classes of intersection graphs of maximal hypercubes of median graphs. For a median graph G and k≥0, the intersection graph Qk(G) is defined as the graph whose vertices are maximal hypercubes (by inclusion) in G, and two vertices Hx and Hy in Qk(G) are adjacent whenever the intersection Hx∩Hy contains a subgraph isomorphic to Qk. Characterizations of clique-graphs in terms of these intersection concepts when k>0, are presented. Furthermore, we introduce the so-called maximal 2-intersection graph of maximal hypercubes of a median graph G, denoted , whose vertices are maximal hypercubes of G, and two vertices are adjacent if the intersection of the corresponding hypercubes is not a proper subcube of some intersection of two maximal hypercubes. We show that a graph H is diamond-free if and only if there exists a median graph G such that H is isomorphic to . We also study convergence of median graphs to the one-vertex graph with respect to all these operations. 相似文献
16.
We investigate a connection between distance-regular graphs and U
q(sl(2)), the quantum universal enveloping algebra of the Lie algebra sl(2). Let be a distance-regular graph with diameter d 3 and valency k 3, and assume is not isomorphic to the d-cube. Fix a vertex x of , and let
(x) denote the Terwilliger algebra of with respect to x. Fix any complex number q {0, 1, –1}. Then
is generated by certain matrices satisfying the defining relations of U
q(sl(2)) if and only if is bipartite and 2-homogeneous. 相似文献
17.
We prove the nonexistence of a distance-regular graph with intersection array {74,54,15;1,9,60} and of distance-regular graphs with intersection arrays
{4r3+8r2+6r+1,2r(r+1)(2r+1),2r2+2r+1;1,2r(r+1),(2r+1)(2r2+2r+1)}