On 2‐factors of a bipartite graph

In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2‐factor with exactly k components? We will prove that if G = (V₁, V₂, E) is a bipartite graph with |V₁| = |V₂| = n ≥ 2k + 1 and δ (G) ≥ ⌈n/2⌉ + 1, then G contains a 2‐factor with exactly k components. We conjecture that if G = (V₁, V₂; E) is a bipartite graph such that |V₁| = |V₂| = n ≥ 2 and δ (G) ≥ ⌈n/2⌉ + 1, then, for any bipartite graph H = (U₁, U₂; F) with |U₁| ≤ n, |U₂| ≤ n and Δ (H) ≤ 2, G contains a subgraph isomorphic to H. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 101–106, 1999     

On partitioning the edges of graphs into connected subgraphs

For any positive integer s, an s-partition of a graph G = (V, E) is a partition of E into E₁ ∪ E₂ ∪…? ∪ E_k, where ∣E_i∣ = s for 1 ≤ i ≤ k ? 1 and 1 ≤ ∣E_k∣ ≤ s and each E_i induces a connected subgraph of G. We prove

• (i) If G is connected, then there exists a 2-partition, but not necessarily a 3-partition;
• (ii) If G is 2-edge connected, then there exists a 3-partition, but not necessarily a 4-partition;
• (iii) If G is 3-edge connected, then there exists a 4-partition;
• (iv) If G is 4-edge connected, then there exists an s-partition for all s.

     

A constructive approach for the lower bounds on the Ramsey numbers R (s,t)

Graph G is a (k, p)‐graph if G does not contain a complete graph on k vertices K_k, nor an independent set of order p. Given a (k, p)‐graph G and a (k, q)‐graph H, such that G and H contain an induced subgraph isomorphic to some K_k?1‐free graph M, we construct a (k, p + q ? 1)‐graph on n(G) + n(H) + n(M) vertices. This implies that R (k, p + q ? 1) ≥ R (k, p) + R (k, q) + n(M) ? 1, where R (s, t) is the classical two‐color Ramsey number. By applying this construction, and some its generalizations, we improve on 22 lower bounds for R (s, t), for various specific values of s and t. In particular, we obtain the following new lower bounds: R (4, 15) ≥ 153, R (6, 7) ≥ 111, R (6, 11) ≥ 253, R (7, 12) ≥ 416, and R (8, 13) ≥ 635. Most of the results did not require any use of computer algorithms. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 231–239, 2004     

Vertex Coverings by Coloured Induced Graphs—Frames and Umbrellas

A graph G homogeneously embeds in a graph H if for every vertex x of G and every vertex y of H there is an induced copy of G in H with x at y. The graph G uniformly embeds in H if for every vertex y of H there is an induced copy of G in H containing y. For positive integer k, let f_k(G) (respectively, g_k(G)) be the minimum order of a graph H whose edges can be k-coloured such that for each colour, G homogeneously embeds (respectively, uniformly embeds) in the graph given by V(H) and the edges of that colour. We investigate the values f₂(G) and g₂(G) for special classes of G, in particular when G is a star or balanced complete bipartite graph. Then we investigate f_k(G) and g_k(G) when k ≥ 3 and G is a complete graph.     

Rainbows in the Hypercube

Let Q_n be a hypercube of dimension n, that is, a graph whose vertices are binary n-tuples and two vertices are adjacent iff the corresponding n-tuples differ in exactly one position. An edge coloring of a graph H is called rainbow if no two edges of H have the same color. Let f(G,H) be the largest number of colors such that there exists an edge coloring of G with f(G,H) colors such that no subgraph isomorphic to H is rainbow. In this paper we start the investigation of this anti-Ramsey problem by providing bounds on f(Q_n,Q_k) which are asymptotically tight for k = 2 and by giving some exact results.     

The average Steiner distance of a graph

The average distance μ(G) of a graph G is the average among the distances between all pairs of vertices in G. For n ≥ 2, the average Steiner n-distance μ_n(G) of a connected graph G is the average Steiner distance over all sets of n vertices in G. It is shown that for a connected weighted graph G, μ_n(G) ≤ μ_k(G) + μ_n+1−k(G) where 2 ≤ k ≤ n − 1. The range for the average Steiner n-distance of a connected graph G in terms of n and |V(G)| is established. Moreover, for a tree T and integer k, 2 ≤ k ≤ n − 1, it is shown that μ_n(T) ≤ (n/k)μ_k(T) and the range for μ_n(T) in terms of n and |V(T)| is established. Two efficient algorithms for finding the average Steiner n-distance of a tree are outlined. © 1996 John Wiley & Sons, Inc.     

The graphs G(n, k) of the Johnson Schemes are unique for n ≥ 20

Let G(n, k) denote the graph of the Johnson Scheme J(n, k), i.e., the graph whose vertices are all k-subsets of a fixed n-set, with two vertices adjacent if and only if their intersection is of size k ? 1. It is known that G(n, k) is a distance regular graph with diameter k. Much work has been devoted to the question of whether a distance regular graph with the parameters of G(n, k) must isomorphic to G(n, k). In this paper, this question is settled affirmatively for n ≥ 20. In fact the result is proved with weaker conditions.     

Unique continuation for schrodinger operators with singular potentials

It is shown in this paper that the Schrodinger operator with a potential satisfying ∣V(x)∣ ≤ M/∣x∣²a.e. in the unit ball B has the strong unique continuation property in H^2,2(B) for for n≥2.     

Reconstructing graphs as subsumed graphs of hypergraphs,and some self-complementary triple systems

LetV be a set ofn elements. The set of allk-subsets ofV is denoted . Ak-hypergraph G consists of avertex-set V(G) and anedgeset , wherek≥2. IfG is a 3-hypergraph, then the set of edges containing a given vertexvεV(G) define a graphG _v . The graphs {G _v νvεV(G)} aresubsumed byG. Each subsumed graphG _v is a graph with vertex-setV(G) − v. They can form the set of vertex-deleted subgraphs of a graphH, that is, eachG _v ≽H −v, whereV(H)=V(G). In this case,G is a hypergraphic reconstruction ofH. We show that certain families of self-complementary graphsH can be reconstructed in this way by a hypergraphG, and thatG can be extended to a hypergraphG ^*, all of whose subsumed graphs are isomorphic toH, whereG andG ^* are self-complementary hypergraphs. In particular, the Paley graphs can be reconstructed in this way. This work was supported by an operating grant from the Natural Sciences and Engineering Research Council of Canada.     

A classification of graph capacity functions

Given two graphs G = (V(G), E(G)) and H = (V(H), E(H)), the sum of G and H, G + H, is the disjoint union of G and H. The product of G and H, G × H, is the graph with the vertex set V(G × H) that is the Cartesian product of V(G) and V(H), and two vertices (g₁, h₁), (g₂, h₂) are adjacent if and only if [g₁, g₂] (ELEMENT) E(G) and [h₁, h₂] (ELEMENT) E(H). Let G denote the set of all graphs. Given a graph G, the G-matching function, γ_G, assigns any graph H (ELEMENT) G to the maximum integer k such that kG is a subgraph of H. The graph capacity function for G, P_G: G → (RFRAKTUR), is defined as P_G(H) = lim_n→z[γ_G(Hⁿ)]^1/n, where Hⁿ denotes the n-fold product of H × H × … × H. Different graphs G may have different graph capacity functions, all of which are increasing. In this paper, we classify all graphs whose capacity functions are additive, multiplicative, and increasing; all graphs whose capacity functions are pseudo-additive, pseudo-multiplicative, and increasing; and all graphs whose capacity functions fall under neither of the above cases. © 1996 John Wiley & Sons, Inc.     

Reduced graphs of diameter two

A graph H is collapsible if for every subset X ? V(H), H has a spanning connected subgraph whose set of odd-degree vertices is X. In any graph G there is a unique collection of maximal collapsible subgraphs, and when all of them are contracted, the resulting contraction of G is a reduced graph. Interest in reduced graphs arises from the fact [4] that a graph G has a spanning closed trail if and only if its corresponding reduced graph has a spanning closed trail. The concept can also be applied to study hamiltonian line graphs [11] or double cycle covers [8]. In this article, we characterize the reduced graphs of diameter two. As applications, we obtain prior results in [12] and [14], and show that every 2-edge-connected graph with diameter at most two either admits a double cycle cover with three even subgraphs or is isomorphic to the Petersen graph.     

Long Paths Through Specified Vertices In 3-Connected Graphs

Let h ≥ 6 be an integer, let G be a 3-connected graph with ∣V(G)∣ ≥ h − 1, and let x and z be distinct vertices of G. We show that if for any nonadjacent distinct vertices u and v in V(G) − {x, z}, the sum of the degrees of u and v in G is greater than or equal to h, then for any subset Y of V(G) − {x, z} with ∣Y∣ ≤ 2, G contains a path which has x and z as its endvertices, passes through all vertices in Y, and has length at least h − 2. We also show a similar result for cycles in 2-connected graphs.     

The edge reconstruction number of a disconnected graph

The edge reconstruction number of a graph G, RN(G), is the minimum number of edge deleted subgraphs required to determine G up to isomorphism. We prove the following results for a disconnected graph G with at least two nontrivial components. If G has a pair of nontrivial nonisomorphic components then RN(G) ≤ 3. If G has a pair of nontrivial nonisomorphic components, is not a forest, and contains a nontrivial component other than K₃ or K_1,3 then RN(G) ≤ 2. Finally, if all nontrivial components of G are isomorphic to a graph with k edges, then RN(G) ≤ k + 2. The edge reconstruction results in this paper are similar to the vertex reconstruction results stated by Myrvold (“The Ally-Reconstruction Number of a Disconnected Graph,” Ars Combinatoria, Vol. 28 [1989] pp. 123-127), but a significant difference is that the edge reconstruction number of a disconnected graph is often two, while the vertex reconstruction number of a graph is always three or more. © 1995 John Wiley & Sons, Inc.     

k-Bounded classes of dominant-independent perfect graphs

Let α(G), γ(G), and i(G) be the independence number, the domination number, and the independent domination number of a graph G, respectively. For any k ≥ 0, we define the following hereditary classes: αi(k) = {G : α(H) − i(H) ≤ k for every H ∈ ISub(G)}; αγ(k) = {G : α(H) − γ(H) ≤ k for every H ∈ ISub(G)}; and iγ(k) = {G : i(H) − γ(H) ≤ k for every H ∈ ISub(G)}, where ISub(G) is the set of all induced subgraphs of a graph G. In this article, we present a finite forbidden induced subgraph characterization for αi(k) and αγ(k) for any k ≥ 0. We conjecture that iγ(k) also has such a characterization. Up to the present, it is known only for iγ(0) (domination perfect graphs [Zverovich & Zverovich, J Graph Theory 20 (1995), 375–395]). © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 303–310, 1999     

Degree conditions for k‐ordered hamiltonian graphs

For a positive integer k, a graph G is k-ordered hamiltonian if for every ordered sequence of k vertices there is a hamiltonian cycle that encounters the vertices of the sequence in the given order. It is shown that if G is a graph of order n with 3 ≤ k ≤ n/2, and deg(u) + deg(v) ≥ n + (3k − 9)/2 for every pair u, v of nonadjacent vertices of G, then G is k-ordered hamiltonian. Minimum degree conditions are also given for k-ordered hamiltonicity. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 199–210, 2003     

An extension of Vizing's theorem

Let G = (V (G), E (G)) be a simple graph of maximum degree δ ≤ D such that the graph induced by vertices of degree D is either a null graph or is empty. We give an upper bound on the number of colours needed to colour a subset S of V (G) ∪ E (G) such that no adjacent or incident elements of S receive the same colour. In particular, if S = E (G), we have the chromatic index χ′(G) ≤ D whereas if S = V (G) ∪ E (G) and for some positive integer k, we have the total chromatic number _χT(G) ≤ D + k. © 1997 John Wiley & Sons, Inc.     

Hamiltonicity of regular 2-connected graphs

Let G be a k-regular 2-connected graph of order n. Jackson proved that G is hamiltonian if n ≤ 3k. Zhu and Li showed that the upper bound 3k on n can be relaxed to 22/7k if G is 3-connected and k ≥ 63. We improve both results by showing that G is hamiltonian if n ≤ 7/2k − 7 and G does not belong to a restricted class F of nonhamiltonian graphs of connectivity 2. To establish this result we obtain a variation of Woodall's Hopping Lemma and use it to prove that if n ≤ 7/2k − 7 and G has a dominating cycle (i.e., a cycle such that the vertices off the cycle constitute an independent set), then G is hamiltonian. We also prove that if n ≤ 4k − 3 and G ∉ F, then G has a dominating cycle. For k ≥ 4 it is conjectured that G is hamiltonian if n ≤ 4k and G ∉ F. © 1996 John Wiley & Sons, Inc.     

The size of strength-maximal graphs

Let G be a graph and let k′(G) be the edge-connectivity of G. The strength of G, denoted by k?′(G), is the maximum value of k′(H), where H runs over all subgraphs of G. A simple graph G is called k-maximal if k?′(G) ≤ k but for any edge e ∈ E(G^c), k?′(G + e) ≥ k + 1. Let G be a k-maximal graph of order n. In [3], Mader proved |E(G)| ≤ (n - k)k + (). In this note, we shall show (n - 1)k - () In?n/k + 2)? ≤ |E(G|, and characterize the extremal graphs. We shall also give a characterization of all k-maximal graphs.     

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. Theorems by Dirac and Ore, presenting sufficient conditions for a graph to be hamiltonian, are generalized to k-ordered hamiltonian graphs. The existence of k-ordered graphs with small maximum degree is investigated; in particular, a family of 4-regular 4-ordered graphs is described. A graph G of order n ≥ 3 is k-hamiltonian-connected, 2 ≤ k ≤ n, if for every sequence v₁, v₂, …, v_k of k distinct vertices, G contains a v₁-v_k hamiltonian path that encounters v₁, v₂,…, v_k in this order. It is shown that for k ≥ 3, every (k + 1)-hamiltonian-connected graph is k-ordered and a result of Ore on hamiltonian-connected graphs is generalized to k-hamiltonian-connected graphs. © 1997 John Wiley & Sons, Inc.