J. Robert Johnson  H. A. Kierstead 《Order》2004,21(1):19-27

In this note we show how 1-factors in the middle two layers of the discrete cube can be used to construct 2-factors in the Odd graph (the Kneser graph of (k − 1)-sets from a (2k − 1)-set). In particular, we use the lexical matchings of Kierstead and Trotter, and the modular matchings of Duffus, Kierstead and Snevily, to give explicit constructions of two different 2-factorisations of the Odd graph. This revised version was published online in September 2006 with corrections to the Cover Date.  相似文献   

    

Andrey A. Dobrynin  Leonid S. Melnikov  Artem V. Pyatkin 《Journal of Graph Theory》2004,46(2):103-130

In 1960, Dirac posed the conjecture that r‐connected 4‐critical graphs exist for every r ≥ 3. In 1989, Erd?s conjectured that for every r ≥ 3 there exist r‐regular 4‐critical graphs. In this paper, a technique of constructing r‐regular r‐connected vertex‐transitive 4‐critical graphs for even r ≥ 4 is presented. Such graphs are found for r = 6, 8, 10. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 103–130, 2004  相似文献   

    

Cai Heng Li  Zai Ping Lu  Gai Xia Wang 《Journal of Graph Theory》2014,75(1):1-19

A classification of connected vertex‐transitive cubic graphs of square‐free order is provided. It is shown that such graphs are well‐characterized metacirculants (including dihedrants, generalized Petersen graphs, Möbius bands), or Tutte's 8‐cage, or graphs arisen from simple groups PSL(2, p).  相似文献   

    

Sanming Zhou 《Journal of Graph Theory》2014,75(1):37-47

Unitary graphs are arc‐transitive graphs with vertices the flags of Hermitian unitals and edges defined by certain elements of the underlying finite fields. They played a significant role in a recent classification of a class of arc‐transitive graphs that admit an automorphism group acting imprimitively on the vertices. In this article, we prove that all unitary graphs are connected of diameter two and girth three. Based on this, we obtain, for any prime power , a lower bound of order on the maximum number of vertices in an arc‐transitive graph of degree and diameter two.  相似文献   

    

Martin Knor  Jozef Širáň 《Journal of Graph Theory》2014,75(2):137-149

For every d and k, we determine the smallest order of a vertex‐transitive graph of degree d and diameter k, and in each such case we show that this order is achieved by a Cayley graph.  相似文献   

    

Maria Chudnovsky  Matthieu Plumettaz 《Journal of Graph Theory》2014,75(3):203-230

  相似文献   

    

John Lenz  Dhruv Mubayi 《Journal of Graph Theory》2014,77(1):19-38

Let be graphs. The multicolor Ramsey number is the minimum integer r such that in every edge‐coloring of by k colors, there is a monochromatic copy of in color i for some . In this paper, we investigate the multicolor Ramsey number , determining the asymptotic behavior up to a polylogarithmic factor for almost all ranges of t and m. Several different constructions are used for the lower bounds, including the random graph and explicit graphs built from finite fields. A technique of Alon and Rödl using the probabilistic method and spectral arguments is employed to supply tight lower bounds. A sample result is for any t and m, where c₁ and c₂ are absolute constants.  相似文献   

    

Pablo De Caria 《Journal of Graph Theory》2014,77(1):39-57

Let be the class of all graphs and K be the clique operator. The validity of the equality has been an open question for several years. A graph in but not in is exhibited here.  相似文献   

    

P. Majerski  J. Przybyło 《Journal of Graph Theory》2014,76(1):34-41

Consider a graph of minimum degree δ and order n. Its total vertex irregularity strength is the smallest integer k for which one can find a weighting such that for every pair of vertices of G. We prove that the total vertex irregularity strength of graphs with is bounded from above by . One of the cornerstones of the proof is a random ordering of the vertices generated by order statistics.  相似文献   

    

M. N. Ellingham  Justin Z. Schroeder 《Journal of Graph Theory》2014,77(3):219-236

In an earlier article the authors constructed a hamilton cycle embedding of in a nonorientable surface for all and then used these embeddings to determine the genus of some large families of graphs. In this two‐part series, we extend those results to orientable surfaces for all . In part II, a voltage graph construction is presented for building embeddings of the complete tripartite graph on an orientable surface such that the boundary of every face is a hamilton cycle. This construction works for all such that p is prime, completing the proof started by part I (which covers the case ) that there exists an orientable hamilton cycle embedding of for all , . These embeddings are then used to determine the genus of several families of graphs, notably for and, in some cases, for .  相似文献