The symmetric (2k,k)‐graphs

A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and G − X is not (n − |X| + 1)‐connected for any X ⊆ V(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K_{2k + 2} − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001     

Tiling Transitive Tournaments and Their Blow-ups

Let TT _k denote the transitive tournament on k vertices. Let TT(h,k) denote the graph obtained from TT _k by replacing each vertex with an independent set of size h≥1. The following result is proved: Let c ₂=1/2, c ₃=5/6 and c _k =1−2^{−k−log k} for k≥4. For every ∈>0 there exists N=N(∈,h,k) such that for every undirected graph G with n>N vertices and with δ(G)≥c _k n, every orientation of G contains vertex disjoint copies of TT(h,k) that cover all but at most ∈n vertices. In the cases k=2 and k=3 the result is asymptotically tight. For k≥4, c _k cannot be improved to less than 1−2^{−0.5k(1+o(1))}. This revised version was published online in June 2006 with corrections to the Cover Date.     

On hamiltonian cycles in the prism over the odd graphs

The Kneser graph K(n, k) has as its vertex set all k‐subsets of an n‐set and two k‐subsets are adjacent if they are disjoint. The odd graph O_k is a special case of Kneser graph when n = 2k + 1. A long standing conjecture claims that O_k is hamiltonian for all k>2. We show that the prism over O_k is hamiltonian for all k even. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:177‐188, 2011     

Maximum Zagreb index, minimum hyper-Wiener index and graph connectivity

In this work we show that among all n-vertex graphs with edge or vertex connectivity k, the graph G=K_k(K₁+K_n−k−1), the join of K_k, the complete graph on k vertices, with the disjoint union of K₁ and K_n−k−1, is the unique graph with maximum sum of squares of vertex degrees. This graph is also the unique n-vertex graph with edge or vertex connectivity k whose hyper-Wiener index is minimum.     

Hamiltonian Kneser Graphs

The Kneser graph K(n,k) has as vertices the k-subsets of {1, 2, ..., n}. Two vertices are adjacent if the corresponding k-subsets are disjoint. It was recently proved by the first author [2] that Kneser graphs have Hamilton cycles for n >= 3k. In this note, we give a short proof for the case when k divides n. Received September 14, 1999     

Factorizations of complete multipartite graphs into generalized cubes

For a positive integer d, the usual d‐dimensional cube Q_d is defined to be the graph (K₂)^d, the Cartesian product of d copies of K₂. We define the generalized cube Q(K_k, d) to be the graph (K_k)^d for positive integers d and k. We investigate the decomposition of the complete multipartite graph K into factors that are vertex‐disjoint unions of generalized cubes Q(K_k, d_i), where k is a power of a prime, n and j are positive integers with j ≤ n, and the d_i may be different in different factors. We also use these results to partially settle a problem of Kotzig on Q_d‐factorizations of K_n. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 144–150, 2000     

List multicoloring problems involving the k‐fold Hall numbers

We show that the four‐cycle has a k‐fold list coloring if the lists of colors available at the vertices satisfy the necessary Hall's condition, and if each list has length at least ?5k/3?; furthermore, the same is not true with shorter list lengths. In terms of h^(k)(G), the k ‐fold Hall number of a graph G, this result is stated as h^(k)(C₄)=2k??k/3?. For longer cycles it is known that h^(k)(C_n)=2k, for n odd, and 2k??k/(n?1)?≤h^(k)(C_n)≤2k, for n even. Here we show the lower bound for n even, and conjecture that this is the right value (just as for C₄). We prove that if G is the diamond (a four‐cycle with a diagonal), then h^(k)(G)=2k. Combining these results with those published earlier we obtain a characterization of graphs G with h^(k)(G)=k. As a tool in the proofs we obtain and apply an elementary generalization of the classical Hall–Rado–Halmos–Vaughan theorem on pairwise disjoint subset representatives with prescribed cardinalities. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 16–34, 2010.     

Hall parameters of complete and complete bipartite graphs

Given a graph G, for each υ ∈V(G) let L(υ) be a list assignment to G. The well‐known choice number c(G) is the least integer j such that if |L(υ)| ≥j for all υ ∈V(G), then G has a proper vertex colouring ? with ?(υ) ∈ L (υ) (?υ ∈V(G)). The Hall number h(G) is like the choice number, except that an extra non‐triviality condition, called Hall's condition, has to be satisfied by the list assignment. The edge‐analogue of the Hall number is called the Hall index, h′(G), and the total analogue is called the total Hall number, h″(G), of G. If the stock of colours from which L(υ) is selected is restricted to a set of size k, then the analogous numbers are called k‐restricted, or restricted, Hall parameters, and are denoted by h_k(G), h′_k(G) and h″_k(G). Our main object in this article is to determine, or closely bound, h′(K), h″(K_n), h′(K_m,n) and h′_k(K_m,n). We also answer some hitherto unresolved questions about Hall parameters. We show in particular that there are examples of graphs G with h′(G)?h′(G ? e)>1. We show that there are examples of graphs G and induced subgraphs H with h_k(G)<h_k(H) [this phenomenon cannot occur with unrestricted Hall numbers]. We also give an example of a graph G and an integer k such that h_k(G)<χ(G)<h(G). © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 208–237, 2002     

Non-traceability of large connected claw-free graphs

Let G be a connected claw-free graph on n vertices. Let ς₃(G) be the minimum degree sum among triples of independent vertices in G. It is proved that if ς₃(G) ≥ n − 3 then G is traceable or else G is one of graphs G_n each of which comprises three disjoint nontrivial complete graphs joined together by three additional edges which induce a triangle K₃. Moreover, it is shown that for any integer k ≥ 4 there exists a positive integer ν(k) such that if ς₃(G) ≥ n − k, n > ν(k) and G is non-traceable, then G is a factor of a graph G_n. Consequently, the problem HAMILTONIAN PATH restricted to claw-free graphs G = (V, E) (which is known to be NP-complete) has linear time complexity O(|E|) provided that ς₃(G) ≥ . This contrasts sharply with known results on NP-completeness among dense graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 75–86, 1998     

Weak quasi‐randomness for uniform hypergraphs

We study quasi‐random properties of k‐uniform hypergraphs. Our central notion is uniform edge distribution with respect to large vertex sets. We will find several equivalent characterisations of this property and our work can be viewed as an extension of the well known Chung‐Graham‐Wilson theorem for quasi‐random graphs. Moreover, let K_k be the complete graph on k vertices and M(k) the line graph of the graph of the k‐dimensional hypercube. We will show that the pair of graphs (K_k,M(k)) has the property that if the number of copies of both K_k and M(k) in another graph G are as expected in the random graph of density d, then G is quasi‐random (in the sense of the Chung‐Graham‐Wilson theorem) with density close to d. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Magic labelings of triangles

The first proof is given that for every even integer s≥4, the graph consisting of s vertex disjoint copies of C₃, (denoted sC₃) is vertex-magic. Hence it is also edge-magic. It is shown that for each even integer s≥6, sC₃ has vertex-magic total labelings with at least 2s−2 different magic constants. If s≡2mod4, two extra vertex-magic total labelings with the highest possible and lowest possible magic constants are given. If s=2⋅3^k, k≥1, it is shown that sC₃ has a vertex-magic total labeling with magic constant h if and only if (1/2)(15s+4)≤h≤(1/2)(21s+2). It is also shown that 2C₃ is not vertex-magic. If s is odd, vertex-magic total labelings for sC₃ with s+1 different magic constants are provided.     

Vertex disjoint equivalent subgraphs of order 3

Let k be a fixed integer at least 3. It is proved that every graph of order (2k ? 1 ? 1/k)n + O(1) contains n vertex disjoint induced subgraphs of order k such that these subgraphs are equivalent to each other and they are equivalent to one of four graphs: a clique, an independent set, a star, or the complement of a star. In particular, by substituting 3 for k, it is proved that every graph of order 14n/3 + O(1) contains n vertex disjoint induced subgraphs of order 3 such that they are equivalent to each other. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 159–166, 2007     

The circular chromatic number of series‐parallel graphs with large girth

It was proved by Hell and Zhu that, if G is a series‐parallel graph of girth at least 2⌊(3k − 1)/2⌋, then χ_c(G) ≤ 4k/(2k − 1). In this article, we prove that the girth requirement is sharp, i.e., for any k ≥ 2, there is a series‐parallel graph G of girth 2⌊(3k − 1)/2⌋ − 1 such that χ_c(G) > 4k/(2k − 1). © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 185–198, 2000     

On the diameter of i‐center in a graph without long induced paths

A graph G is said to be P_t‐free if it does not contain an induced path on t vertices. The i‐center C_i(G) of a connected graph G is the set of vertices whose distance from any vertex in G is at most i. Denote by I(t) the set of natural numbers i, ⌊t/2⌋ ≤ i ≤ t − 2, with the property that, in every connected P_t‐free graph G, the i‐center C_i(G) of G induces a connected subgraph of G. In this article, the sharp upper bound on the diameter of G[C_i(G)] is established for every i ∈ I(t). The sharp lower bound on I(t) is obtained consequently. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 235–241, 1999     

On cliques and bicliques

For integers m, n ≥ 2, let g(m, n) be the minimum order of a graph, where every vertex belongs to both a clique K_m of order m and a biclique K(n, n). We show that g(m, n) = 2(m + n − 2) if m ≤ n − 2. Furthermore, for m ≥ n − 1, we establish that ≡ 0 mod(n − 1) or, if m is sufficiently large and is not an integer. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 60–66, 2000     

Petersen Graph Decompositions of Complete Multipartite Graphs

Let P be the Petersen graph, and K _u(h) the complete multipartite graph with u parts of size h. A decomposition of K _u(h) into edge-disjoint copies of the Petersen graph P is called a P-decomposition of K _u(h) or a P-group divisible design of type h ^u . In this paper, we show that there exists a P-decomposition of K _u(h) if and only if h²u(u-1) o 0 mod 30{h^2u(u-1)\equiv 0 \pmod {30}} , h(u-1) o 0 mod 3{h(u-1)\equiv 0\pmod 3} , and u ≥ 3 with a definite exception (h, u) = (1, 10).     

A note on vertex pancyclic oriented graphs

Let D be an oriented graph of order n ≥ 9, minimum degree at least n − 2, such that, for the choice of distinct vertices x and y, either xy ∈ E(D) or d⁺(x) + d⁻(y) ≥ n − 3. Song (J. Graph Theory 18 (1994), 461–468) proved that D is pancyclic. In this note, we give a short proof, based on Song's result, that D is, in fact, vertex pancyclic. This also generalizes a result of Jackson (J. Graph Theory 5 (1981), 147–157) for the existence of a hamiltonian cycle in oriented graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 313–318, 1999     

Another two graphs with no planar covers

A graph H is a cover of a graph G if there exists a mapping φ from V( H ) onto V( G ) such that φ maps the neighbors of every vertex υ in H bijectively to the neighbors of φ(υ) in G . Negami conjectured in 1986 that a connected graph has a finite planar cover if and only if it embeds in the projective plane. It follows from the results of Archdeacon, Fellows, Negami, and the author that the conjecture holds as long as K _1,2,2,2 has no finite planar cover. However, this is still an open question, and K _1,2,2,2 is not the only minor‐minimal graph in doubt. Let ??₄ (?₂) denote the graph obtained from K _1,2,2,2 by replacing two vertex‐disjoint triangles (four edge‐disjoint triangles) not incident with the vertex of degree 6 with cubic vertices. We prove that the graphs ??₄ and ?₂ have no planar covers. This fact is used in [P. Hlin?ný, R. Thomas, On possible counterexamples to Negami's planar cover conjecture, 1999 (submitted)] to show that there are, up to obvious constructions, at most 16 possible counterexamples to Negami's conjecture. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 227–242, 2001     

On k-ordered Hamiltonian graphs

A Hamiltonian graph G of order n is k-ordered, 2 ≤ k ≤ n, if for every sequence v₁, v₂, …, v_k of k distinct vertices of G, there exists a Hamiltonian cycle that encounters v₁, v₂, …, v_k in this order. Define f(k, n) as the smallest integer m for which any graph on n vertices with minimum degree at least m is a k-ordered Hamiltonian graph. In this article, answering a question of Ng and Schultz, we determine f(k, n) if n is sufficiently large in terms of k. Let g(k, n) = − 1. More precisely, we show that f(k, n) = g(k, n) if n ≥ 11k − 3. Furthermore, we show that f(k, n) ≥ g(k, n) for any n ≥ 2k. Finally we show that f(k, n) > g(k, n) if 2k ≤ n ≤ 3k − 6. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 17–25, 1999     

Connected subgraphs with small degree sums in 3‐connected planar graphs

It is well‐known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3‐connected planar graph has an edge xy such that deg(x) + deg (y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t, every 3‐connected planar graph G with |V(G)| ≥ t has a connected subgraph H of order t such that Σ_x∈V(H) deg_G(x) ≤ 8t − 1. As a tool for proving this result, we consider decompositions of 3‐connected planar graphs into connected subgraphs of order at least t and at most 2t − 1. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 191–203, 1999