EMBEDDINGS OF ONE KIND OF GRAPHS

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.     

Smallest close to regular bipartite graphs without an almost perfect matching

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.     

Distance-transitive dihedrants

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 ₂; 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.     

A sufficient degree condition for a graph to contain all trees of size <Emphasis Type="Italic">k</Emphasis>

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.     

A class of optimal linear codes of length one above the Griesmer bound

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 ² + 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 ² + 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 Com²MaC-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).     

A Classification of the Strongly Regular Generalised Johnson Graphs

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 ₁ and J ₂ 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.     

Unitary Graphs and Their Automorphisms

The (isotropic) unitary graph U (n, q²){U \left(n, q^{2}\right)} is introduced. When n = 2 or 3, U (2, q²){U \left(2, q^{2}\right)} or U (3, q²){U \left(3, q^{2}\right)} are complete graphs with q + 1 or q ³ + 1 vertices, respectively. When n ≥ 4, it is shown that U (n, q²){U \left(n, q^{2}\right)} is strongly regular and its parameters are computed. The group of graph automorphisms of U (n, q²){U \left(n, q^{2}\right)} , when n ≠ 4, 5, is determined.     

The Crossing Number of Cartesian Products of Complete Bipartite Graphs K 2, m with Paths P n

Most results on the crossing number of a graph focus on the special graphs, such as Cartesian products of small graphs with paths P_n, cycles C_n or stars S_n. In this paper, we extend the results to Cartesian products of complete bipartite graphs K_2,m with paths P_n for arbitrary m ≥ 2 and n ≥ 1. Supported by the NSFC (No. 10771062) and the program for New Century Excellent Talents in University.     

Polynomial Factorisation and an Application to Regular Directed Graphs

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)!]². This improves on the work of Katz who gave a similar result for square-free polynomialsfwithout specifyingB(n).     

Rates of convergence of random walk on distance regular graphs

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     

Bicolored Matchings in Some Classes of Graphs

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 M_k exist with |M_k∩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.     

Multiple blocking sets in finite projective spaces and improvements to the Griesmer bound for linear codes

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 F_p{{\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.     

Strongly indexable graphs and applications

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.     

Circuits Through Cocircuits In A Graph With Extensions To Matroids

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 C₁ and C₂ are disjoint circuits satisfying r(C₁)+r(C₂)=r(C₁∪C₂), then |C₁|+|C₂|≤2(c-k + 1).     

Large Vertex-Disjoint Cycles in a Bipartite Graph

Let s≥2 and k be two positive integers. Let G=(V ₁,V ₂;E) be a bipartite graph with |V ₁|=|V ₂|=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     

On the embedding of graphs into graphs with few eigenvalues

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.     

Spanning k-Trees of n-Connected Graphs

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.     

The Decomposition Dimension of Graphs

 For an ordered k-decomposition ? = {G ₁, G ₂,…,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 ₁), d(e, G ₂),…,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     

On linguistic dynamical systems,families of graphs of large girth,and cryptography

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 ⁿ → K ⁿ depending on “time” α ∈ {K − 0} such that f _α ⁻¹ = f _−αM, the relation f _α1 (x) = f _α2 (x) for some x ∈ Kⁿ implies α₁ = α₂, 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 Kⁿ. We refer to F as a linguistic dynamical system of rank d ≥ 1 if for each string a = (α₁, υ, α₂), 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 L_n(K) of rank d ≥ 1/3n. Let L(n, K) be the graph of the dynamical system L_n(q). If K = F_q, the graphs L(n, F_q) 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 L_n(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.