共查询到20条相似文献,搜索用时 31 毫秒
1.
LiuYING LiuYANPEI 《高校应用数学学报(英文版)》1997,12(3):253-258
The purpose of this paper is to display a new kind of simple graphs which belong to B. inwhich any graph has its orientable genus n,n≥3. Furthermore, for any integer k,1≤k≤n,there exists a graph B^kn of B. such that the non-orientable genus of B^kn is k. 相似文献
2.
A graph G is close to regular or more precisely a (d, d + k)-graph, if the degree of each vertex of G is between d and d + k. Let d ≥ 2 be an integer, and let G be a connected bipartite (d, d+k)-graph with partite sets X and Y such that |X|- |Y|+1. If G is of order n without an almost perfect matching, then we show in this paper that·n ≥ 6d +7 when k = 1,·n ≥ 4d+ 5 when k = 2,·n ≥ 4d+3 when k≥3.Examples will demonstrate that the given bounds on the order of G are the best possible. 相似文献
3.
The main result of this article is a classification of distance-transitive Cayley graphs on dihedral groups. We show that a Cayley graph X on a dihedral group is distance-transitive if and only if X is isomorphic to one of the following graphs: the complete graph K
2n
; a complete multipartite graph K
t×m
with t anticliques of size m, where t
m is even; the complete bipartite graph without 1-factor K
n,n
− nK
2; the cycle C
2n
; the incidence or the non-incidence graph of the projective geometry PG
d-1(d,q), d ≥ 2; the incidence or the non-incidence graph of a symmetric design on 11 vertices. 相似文献
4.
The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d
G
(x) + d
G
(y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d
G
(u) ≥ k. 相似文献
5.
E. J. Cheon 《Designs, Codes and Cryptography》2009,51(1):9-20
In this paper, we determine the smallest lengths of linear codes with some minimum distances. We construct a [g
q
(k, d) + 1, k, d]
q
code for sq
k-1 − sq
k-2 − q
s
− q
2 + 1 ≤ d ≤ sq
k-1 − sq
k-2 − q
s
with 3 ≤ s ≤ k − 2 and q ≥ s + 1. Then we get n
q
(k, d) = g
q
(k, d) + 1 for (k − 2)q
k-1 − (k − 1)q
k-2 − q
2 + 1 ≤ d ≤ (k − 2)q
k-1 − (k − 1)q
k-2, k ≥ 6, q ≥ 2k − 3; and sq
k-1 − sq
k-2 − q
s
− q + 1 ≤ d ≤ sq
k-1 − sq
k-2 − q
s
, s ≥ 2, k ≥ 2s + 1 and q ≥ 2s − 1.
This work was partially supported by the Com2MaC-SRC/ERC program of MOST/KOSEF (grant # R11-1999-054) and was partially supported by the Korea Research Foundation Grant funded by the Korean Government(MOEHRD)(KRF-2005-214-C00175). 相似文献
6.
The generalised Johnson graphs are the graphs J(n, k, m) whose vertices are the k subsets of {1, 2, . . . , n}, with two vertices J 1 and J 2 joined by an edge if and only if ${{|J_1 \cap J_2| = m}}$ . A graph is called d-regular if every vertex has exactly d edges incident to it. A d-regular graph on v vertices is called a (v, d, a, c)-strongly regular graph if every pair of adjacent vertices have exactly a common neighbours and every pair of non-adjacent vertices have exactly c common neighbours. The triangular graphs J(n, 2, 1), their complements J(n, 2, 0), the sporadic examples J(10, 3, 1) and J(7, 3, 1), as well as the trivially strongly regular graphs J(2k, k, 0) are examples of strongly regular generalised Johnson graphs. In this paper we prove that there are no other strongly regular generalised Johnson graphs. 相似文献
7.
The (isotropic) unitary graph U (n, q2){U \left(n, q^{2}\right)} is introduced. When n = 2 or 3, U (2, q2){U \left(2, q^{2}\right)} or U (3, q2){U \left(3, q^{2}\right)} are complete graphs with q + 1 or q
3 + 1 vertices, respectively. When n ≥ 4, it is shown that U (n, q2){U \left(n, q^{2}\right)} is strongly regular and its parameters are computed. The group of graph automorphisms of U (n, q2){U \left(n, q^{2}\right)} , when n ≠ 4, 5, is determined. 相似文献
8.
Most results on the crossing number of a graph focus on the special graphs, such as Cartesian products of small graphs with
paths Pn, cycles Cn or stars Sn. In this paper, we extend the results to Cartesian products of complete bipartite graphs K2,m with paths Pn for arbitrary m ≥ 2 and n ≥ 1.
Supported by the NSFC (No. 10771062) and the program for New Century Excellent Talents in University. 相似文献
9.
Stephen D. Cohen 《Finite Fields and Their Applications》1998,4(4):316-346
The main theme is the distribution of polynomials of given degree which split into a product of linear factors over a finite field. The work was motivated by the following problem on regular directed graphs. Extending a notion of Chung, Katz has defined a regular directed graph based on thek-algebrak[X]/(f), wherekis the finite field of orderqandfa monic polynomial of degreenoverk. It is shown that the diameter of this graph is at mostn+2 wheneverq≥B(n)=[n(n+2)!]2. This improves on the work of Katz who gave a similar result for square-free polynomialsfwithout specifyingB(n). 相似文献
10.
11.
Eric David Belsley 《Probability Theory and Related Fields》1998,112(4):493-533
When run on any non-bipartite q-distance regular graph from a family containing graphs of arbitrarily large diameter d, we show that d steps are necessary and sufficient to drive simple random walk to the uniform distribution in total variation distance, and
that a sharp cutoff phenomenon occurs. For most examples, we determine the set on which the variation distance is achieved,
and the precise rate at which it decays.
The upper bound argument uses spectral methods – combining the usual Cauchy-Schwarz bound on variation distance with a bound
on the tail probability of a first-hitting time, derived from its generating function.
Received: 2 April 1997 / Revised version: 10 May 1998 相似文献
12.
We consider the problem of finding in a graph a set R of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular
bipartite graphs with n nodes on each side, we give sufficient conditions for the existence of a set R with |R|=n+1 such that perfect matchings with k red edges exist for all k,0≤k≤n. Given two integers p<q we also determine the minimum cardinality of a set R of red edges such that there are perfect matchings with p red edges and with q red edges. For 3-regular bipartite graphs, we show that if p≤4 there is a set R with |R|=p for which perfect matchings Mk exist with |Mk∩R|≤k for all k≤p. For trees we design a linear time algorithm to determine a minimum set R of red edges such that there exist maximum matchings with k red edges for the largest possible number of values of k. 相似文献
13.
Belov, Logachev and Sandimirov construct linear codes of minimum distance d for roughly 1/q
k/2 of the values of d < q
k-1. In this article we shall prove that, for q = p prime and roughly
\frac38{\frac{3}{8}}-th’s of the values of d < q
k-1, there is no linear code meeting the Griesmer bound. This result uses Blokhuis’ theorem on the size of a t-fold blocking set in PG(2, p), p prime, which we generalise to higher dimensions. We also give more general lower bounds on the size of a t-fold blocking set in PG(δ, q), for arbitrary q and δ ≥ 3. It is known that from a linear code of dimension k with minimum distance d < q
k-1 that meets the Griesmer bound one can construct a t-fold blocking set of PG(k−1, q). Here, we calculate explicit formulas relating t and d. Finally we show, using the generalised version of Blokhuis’ theorem, that nearly all linear codes over
\mathbb Fp{{\mathbb F}_p} of dimension k with minimum distance d < q
k-1, which meet the Griesmer bound, have codewords of weight at least d + p in subcodes, which contain codewords satisfying certain hypotheses on their supports. 相似文献
14.
In 1990, Acharya and Hegde introduced the concept of strongly k-indexable graphs: A (p,q)-graph G=(V,E) is said to be strongly k-indexable if its vertices can be assigned distinct numbers 0,1,2,…,p−1 so that the values of the edges, obtained as the sums of the numbers assigned to their end vertices form an arithmetic progression k,k+1,k+2,…,k+(q−1). When k=1, a strongly k-indexable graph is simply called a strongly indexable graph. In this paper, we report some results on strongly k-indexable graphs and give an application of strongly k-indexable graphs to plane geometry, viz; construction of polygons of same internal angles and sides of distinct lengths. 相似文献
15.
Sean McGuinness 《Combinatorica》2005,25(4):451-463
We show that for any k-connected graph having cocircumference c*, there is a cycle which intersects every cocycle of size c*-k + 2 or greater. We use this to show that in a 2-connected graph, there is a family of at most c* cycles for which each edge of the graph belongs to at least two cycles in the family. This settles a question raised by
Oxley.
A certain result known for cycles and cocycles in graphs is extended to matroids. It is shown that for a k-connected regular matroid having circumference c ≥ 2k if C1 and C2 are disjoint circuits satisfying r(C1)+r(C2)=r(C1∪C2), then |C1|+|C2|≤2(c-k + 1). 相似文献
16.
Large Vertex-Disjoint Cycles in a Bipartite Graph 总被引:4,自引:0,他引:4
Hong Wang 《Graphs and Combinatorics》2000,16(3):359-366
Let s≥2 and k be two positive integers. Let G=(V
1,V
2;E) be a bipartite graph with |V
1|=|V
2|=n≥s
k and the minimum degree at least (s−1)k+1. When s=2 and n >2k, it is proved in [5] that G contains k vertex-disjoint cycles. In this paper, we show that if s≥3, then G contains k vertex-disjoint cycles of length at least 2s.
Received: March 2, 1998 Revised: October 26, 1998 相似文献
17.
Van H. Vu 《Journal of Graph Theory》1996,22(2):137-149
A graph is called of type k if it is connected, regular, and has k distinct eigenvalues. For example graphs of type 2 are the complete graphs, while those of type 3 are the strongly regular graphs. We prove that for any positive integer n, every graph can be embedded in n cospectral, non-isomorphic graphs of type k for every k ≥ 3. Furthermore, in the case k ≥ 5 such a family of extensions can be found at every sufficiently large order. Some bounds for the extension will also be given. © 1996 John Wiley & Sons, Inc. 相似文献
18.
A tree is called a k-tree if the maximum degree is at most k. We prove the following theorem, by which a closure concept for spanning k-trees of n-connected graphs can be defined. Let k ≥ 2 and n ≥ 1 be integers, and let u and v be a pair of nonadjacent vertices of an n-connected graph G such that deg
G
(u) + deg
G
(v) ≥ |G| − 1 − (k − 2)n, where |G| denotes the order of G. Then G has a spanning k-tree if and only if G + uv has a spanning k-tree. 相似文献
19.
For an ordered k-decomposition ? = {G
1, G
2,…,G
k
} of a connected graph G and an edge e of G, the ?-representation of e is the k-tuple r(e|?) = (d(e, G
1), d(e, G
2),…,d(e, G
k
)), where d(e, G
i
) is the distance from e to G
i
. A decomposition ? is resolving if every two distinct edges of G have distinct representations. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dec(G). It is shown that for every two positive integers k and n≥ 2, there exists a tree T of order n with dec(T) = k. It is also shown that dec(G) ≤n for every graph G of order n≥ 3 and that dec(K
n
) ≤⌊(2n + 5)/3⌋ for n≥ 3.
Received: June 17, 1998 Final version received: August 10, 1999 相似文献
20.
V. A. Ustimenko 《Journal of Mathematical Sciences》2007,140(3):461-471
The paper is devoted to the study of a linguistic dynamical system of dimension n ≥ 2 over an arbitrary commutative ring K,
i.e., a family F of nonlinear polynomial maps f
α : K
n
→ K
n
depending on “time” α ∈ {K − 0} such that f
α
−1 = f
−αM, the relation f
α1 (x) = f
α2 (x) for some x ∈ Kn implies α1 = α2, and each map f
α has no invariant points. The neighborhood {f
α (υ)∣α ∈ K − {0}} of an element v determines the graph Γ(F) of the dynamical system on the vertex set Kn. We refer to F as a linguistic dynamical system of rank d ≥ 1 if for each string a = (α1, υ, α2), s ≤ d, where αi + αi+1 is a nonzero divisor for i = 1, υ, d − 1, the vertices υ
a = f
α1 × ⋯ × f
αs
(υ) in the graph are connected by a unique path. For each commutative ring K and each even integer n ≠= 0 mod 3, there is a family of linguistic dynamical systems Ln(K) of rank d ≥ 1/3n. Let L(n, K) be the graph of the dynamical system Ln(q). If K = Fq, the graphs L(n, Fq) form a new family of graphs of large girth. The projective limit L(K) of L(n, K), n → ∞, is well defined for each commutative
ring K; in the case of an integral domain K, the graph L(K) is a forest. If K has zero divisors, then the girth of K drops
to 4. We introduce some other families of graphs of large girth related to the dynamical systems Ln(q) in the case of even q. The dynamical systems and related graphs can be used for the development of symmetric or asymmetric
cryptographic algorithms. These graphs allow us to establish the best known upper bounds on the minimal order of regular graphs
without cycles of length 4n, with odd n ≥ 3. Bibliography: 42 titles.
Published in Zapiski Nauchnykh Seminarov POMI, Vol. 326, 2005, pp. 214–234. 相似文献