A sufficient condition for a graph to be weakly k-linked

For a pair (s, t) of vertices of a graph G, let λ_G(s, t) denote the maximal number of edge-disjoint paths between s and t. Let (s₁, t₁), (s₂, t₂), (s₃, t₃) be pairs of vertices of G and k > 2. It is shown that if λ_G(s_i, t_i) ≥ 2k + 1 for each i = 1, 2, 3, then there exist 2k + 1 edge-disjoint paths such that one joins s₁ and t₁, another joins s₂ and t₂ and the others join s₃ and t₃. As a corollary, every (2k + 1)-edge-connected graph is weakly (k + 2)-linked for k ≥ 2, where a graph is weakly k-linked if for any k vertex pairs (s_i, t_i), 1 ≤ i ≤ k, there exist k edge-disjoint paths P₁, P₂,…, P_k such that P_i joins s_i and t_i for i = 1, 2,…, k.     

Multicommodity flows in graphs

Suppose that G is a graph, and (s_i,t_i) (1≤i≤k) are pairs of vertices; and that each edge has a integer-valued capacity (≥0), and that q_i≥0 (1≤i≤k) are integer-valued demands. When is there a flow for each i, between s_i and t_i and of value q_i, such that the total flow through each edge does not exceed its capacity? Ford and Fulkerson solved this when k=1, and Hu when k=2. We solve it for general values of k, when G is planar and can be drawn so that s₁,…, s_l, t₁, …, t_l,…,t_l are all on the boundary of a face and s_l+1, …,S_k, t_l+1,…,t_k are all on the boundary of the infinite face or when t₁=?=t_l and G is planar and can be drawn so that s_l+1,…,s_k, t₁,…,t_k are all on the boundary of the infinite face. This extends a theorem of Okamura and Seymour.     

Optimal labelling of a product of two paths

If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.P_n will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. P_m × P_n will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(P_m × P_n) = min(m, n).     

The extremal function for 3-linked graphs

A graph is k-linked if for every set of 2k distinct vertices {s₁,…,s_k,t₁,…,t_k} there exist disjoint paths P₁,…,P_k such that the endpoints of P_i are s_i and t_i. We prove every 6-connected graph on n vertices with 5n−14 edges is 3-linked. This is optimal, in that there exist 6-connected graphs on n vertices with 5n−15 edges that are not 3-linked for arbitrarily large values of n.     

Metrics and undirected cuts

Suppose thatG is an undirected graph whose edges have nonnegative integer-valued lengthsl(e), and that {s ₁,t ₁},?, {s _m ,t _m } are pairs of its vertices. Can one assign nonnegative weights to the cuts ofG such that, for each edgee, the total weight of cuts containinge does not exceedl(e) and, for eachi, the total weight of cuts ‘separating’s _i andt _i is equal to the distance (with respect tol) betweens _i andt _i ? Using linear programming duality, it follows from Papernov's multicommodity flow theorem that the answer is affirmative if the graph induced by the pairs {s ₁,t ₁},?, {s _m ,t _m } is one of the following: (i) the complete graph with four vertices, (ii) the circuit with five vertices, (iii) a union of two stars. We prove that if, in addition, each circuit inG has an even length (with respect tol) then there exists a suitable weighting of the cuts with the weights integer-valued; moreover, an algorithm of complexity O(n ³) (n is the number of vertices ofG) is developed for solving such a problem. Also a class of metrics decomposable into a nonnegative linear combination of cut-metrics is described, and it is shown that the separation problem for cut cones isNP-hard.     

Graph powers and k-ordered Hamiltonicity

It is known that if G is a connected simple graph, then G³ is Hamiltonian (in fact, Hamilton-connected). A simple graph is k-ordered Hamiltonian if for any sequence v₁, v₂,…,v_k of k vertices there is a Hamiltonian cycle containing these vertices in the given order. In this paper, we prove that if k?4, then G^⌊3k/2⌋-2 is k-ordered Hamiltonian for every connected graph G on at least k vertices. By considering the case of the path graph P_n, we show that this result is sharp. We also give a lower bound on the power of the cycle C_n that guarantees k-ordered Hamiltonicity.     

The insulation sequence of a graph

In a graph G, a k-insulated set S is a subset of the vertices of G such that every vertex in S is adjacent to at most k vertices in S, and every vertex outside S is adjacent to at least k+1 vertices in S. The insulation sequencei₀,i₁,i₂,… of a graph G is defined by setting i_k equal to the maximum cardinality of a k-insulated set in G. We determine the insulation sequence for paths, cycles, fans, and wheels. We also study the effect of graph operations, such as the disjoint union, the join, the cross product, and graph composition, upon k-insulated sets. Finally, we completely characterize all possible orderings of the insulation sequence, and prove that the insulation sequence is increasing in trees.     

Edge-colored saturated graphs

A graph G is (k₁, k₂, …, k_t)-saturated if there exists a coloring C of the edges of G in t colors 1, 2, …, t in such a way that there is no monochromatic complete k_i-subgraph K of color i, 1 ? i ? t, but the addition of any new edge of color i, joining two nonadjacent vertices in G, with C, creates a monochromatic K of color i, 1 ? i ? t. We determine the maximum and minimum number of edges in such graphs and characterize the unique extremal graphs.     

[r,s,t]-Coloring of K n,n

Let G=(V(G),E(G)) be a simple graph. Given non-negative integers r,s, and t, an [r,s,t]-coloring of G is a mapping c from V(G)∪E(G) to the color set {0,1,…,k?1} such that |c(v _i )?c(v _j )|≥r for every two adjacent vertices v _i ,v _j , |c(e _i )?c(e _j )|≥s for every two adjacent edges e _i ,e _j , and |c(v _i )?c(e _j )|≥t for all pairs of incident vertices and edges, respectively. The [r,s,t]-chromatic number χ _r,s,t (G) of G is defined to be the minimum k such that G admits an [r,s,t]-coloring. We determine χ _r,s,t (K _n,n ) in all cases.     

Edge-disjoint paths and cycles in n-edge-connected graphs

We consider finite undirected loopless graphs G in which multiple edges are possible. For integers k,l ≥ 0 let g(k, l) be the minimal n ≥ 0 with the following property: If G is an n-edge-connected graph, s₁, ?,s_k, t₁, ?,t_k are vertices of G, and f₁, ?,f_l, g₁, ?,g_l, are pairwise distinct edges of G, then for each i = 1, ?, k there exists a path P_i in G, connecting s_i and t_i and for each i = 1, ?,l there exists a cycle C_i in G containing f_i and g_i such that P₁, ?,P_k, C₁, ?, C_l are pairwise edge-disjoint. We give upper and lower bounds for g(k, l).     

Covering the vertices of a graph by cycles of prescribed length

The main theorem of that paper is the following: let G be a graph of order n, of size at least (n² - 3n + 6)/2. For any integers k, n₁, n₂,…,n_k such that n = n₁ + n₂ +. + n_k and n_i ? 3, there exists a covering of the vertices of G by disjoint cycles (C_i) =l…k with |C_i| = ni, except when n = 6, n₁ = 3, n₂ = 3, and G is isomorphic to G₁, the complement of G₁ consisting of a C₃ and a stable set of three vertices, or when n = 9, n₁ = n₂ = n₃ = 3, and G is isomorphic to G₂, the complement of G₂ consisting of a complete graph on four vertices and a stable set of five vertices. We prove an analogous theorem for bipartite graphs: let G be a bipartite balanced graph of order 2n, of size at least n² - n + 2. For any integers s, n₁, n₂,…,n_s with n_i ? 2 and n = n₁ + n₂ + ? + n_s, there exists a covering of the vertices of G by s disjoint cycles C_i, with |C_i| = 2n_i.     

Mutually orthogonal graph squares

A decomposition ??={G₁, G₂,…,G_s} of a graph G is a partition of the edge set of G into edge‐disjoint subgraphs G₁, G₂,…,G_s. If G_i?H for all i∈{1, 2, …, s}, then ?? is a decomposition of G by H. Two decompositions ??={G₁, G₂, …, G_n} and ?={F₁, F₂,…,F_n} of the complete bipartite graph K_n,n are orthogonal if |E(G_i)∩E(F_j)|=1 for all i,j∈{1, 2, …, n}. A set of decompositions {??₁, ??₂, …, ??_k} of K_{n, n} is a set of k mutually orthogonal graph squares (MOGS) if ??_i and ??_j are orthogonal for all i, j∈{1, 2, …, k} and i≠j. For any bipartite graph G with n edges, N(n, G) denotes the maximum number k in a largest possible set {??₁, ??₂, …, ??_k} of MOGS of K_{n, n} by G. El‐Shanawany conjectured that if p is a prime number, then N(p, P_{p+ 1})=p, where P_{p+ 1} is the path on p+ 1 vertices. In this article, we prove this conjecture. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 369–373, 2009     

Graph minors. I. Excluding a forest

The path-width of a graph is the minimum value ofk such that the graph can be obtained from a sequence of graphsG₁,…,G_r each of which has at mostk + 1 vertices, by identifying some vertices ofG_i pairwise with some ofG_i+1 (1 ≤ i < r). For every forestH it is proved that there is a numberk such that every graph with no minor isomorphic toH has path-width?k. This, together with results of other papers, yields a “good” algorithm to test for the presence of any fixed forest as a minor, and implies that ifP is any property of graphs such that some forest does not have propertyP, then the set of minor-minimal graphs without propertyP is finite.     

Induced disjoint paths problem in a planar digraph

As an extension of the disjoint paths problem, we introduce a new problem which we call the induced disjoint paths problem. In this problem we are given a graph G and a collection of vertex pairs {(s₁,t₁),…,(s_k,t_k)}. The objective is to find k paths P₁,…,P_k such that P_i is a path from s_i to t_i and P_i and P_j have neither common vertices nor adjacent vertices for any distinct i,j.The induced disjoint paths problem has several variants depending on whether k is a fixed constant or a part of the input, whether the graph is directed or undirected, and whether the graph is planar or not. We investigate the computational complexity of several variants of the induced disjoint paths problem. We show that the induced disjoint paths problem is (i) solvable in polynomial time when k is fixed and G is a directed (or undirected) planar graph, (ii) NP-hard when k=2 and G is an acyclic directed graph, (iii) NP-hard when k=2 and G is an undirected general graph.As an application of our first result, we show that we can find in polynomial time certain structures called a “hole” and a “theta” in a planar graph.     

Some Bistar Bipartite Ramsey Numbers

For bipartite graphs G ₁, G ₂, . . . ,G _k , the bipartite Ramsey number b(G ₁, G ₂, . . . , G _k ) is the least positive integer b so that any colouring of the edges of K _b,b with k colours will result in a copy of G _i in the ith colour for some i. A tree of diameter three is called a bistar, and will be denoted by B(s, t), where s ≥ 2 and t ≥ 2 are the degrees of the two support vertices. In this paper we will obtain some exact values for b(B(s, t), B(s, t)) and b(B(s, s), B(s, s)). Furtermore, we will show that if k colours are used, with k ≥ 2 and s ≥ 2, then \({b_{k}(B(s, s)) \leq \lceil k(s - 1) + \sqrt{(s - 1)^{2}(k^{2} - k) - k(2s - 4)} \rceil}\) . Finally, we show that for s ≥ 3 and k ≥ 2, the Ramsey number \({r_{k}(B(s, s)) \leq \lceil 2k(s - 1)+ \frac{1}{2} + \frac{1}{2} \sqrt{(4k(s - 1) + 1)^{2} - 8k(2s^{2} - s - 2)} \rceil}\) .     

Minimum number of edges in graphs that are both P2- and Pi-connected

A simple graph with n vertices is called P_i-connected if any two distinct vertices are connected by an elementary path of length i. In this paper, lower bounds of the number of edges in graphs that are both P₂- and P_i-connected are obtained. Namely if $\text{i?}\text{1}\text{2}\text{(n+1)}$, then |E(G)|?((4i?5)/(2i?2))(n?1), and if $\text{i >}\text{1}\text{2}\text{(n+ 1)}$, then |E(G)|?2(n?1) apart from one exeptional graph. Furthermore, extremal graphs are determined in the former.     

Partitions of a graph into paths with prescribed endvertices and lengths

For a graph G, let σ₂(G) denote the minimum degree sum of a pair of nonadjacent vertices. We conjecture that if |V(G)| = n = Σ^k_{i = 1} a_i and σ₂(G) ≥ n + k − 1, then for any k vertices v₁, v₂,…, v_k in G, there exist vertex‐disjoint paths P₁, P₂,…, P_k such that |V(P_i)| = a_i and v_i is an endvertex of P_i for 1 ≤ i ≤ k. In this paper, we verify the conjecture for the cases where almost all a_i ≤ 5, and the cases where k ≤ 3. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 163–169, 2000     

Paths and edge-connectivity in graphs III. Six-terminalk paths

Suppose thatk ≥ 1 is an odd integer, (s ₁,t ₁),..., (s _k> ,t _k ) are pairs of vertices of a graphG andλ(s _i ,t _i ) is the maximal number of edge-disjoint paths betweens _i andt _i . We prove that ifλ(s _i ,t _i )≥ k (1≤ i ≤ k) and |{s ₁,...s _k ,t ₁,...,t _k }| ≤ 6, then there exist edge-disjoint pathsP ₁,...,P _k such thatP _i has endss _i andt _i (1≤ i ≤ k).     

A sufficient condition for graphs to be weaklyk-linked

We consider graphs, which are finite, undirected, without loops and in which multiple edges are possible. For each natural numberk letg(k) be the smallest natural numbern, so that the following holds:LetG be ann-edge-connected graph and lets ₁,...,s _k,t ₁,...,t _k be vertices ofG. Then for everyi {1,..., k} there existsa pathP _i froms _i tot _i, so thatP ₁,...,P _k are pairwise edge-disjoint. We prove      

Double cycle covers and the petersen graph

Let O(G) denote the set of odd-degree vertices of a graph G. Let t ? N and let ??_t denote the family of graphs G whose edge set has a partition. E(g) = E₁ U E₂ U … U E_tsuch that O(G) = O(G[E_i]) (1 ? i ? t). This partition is associated with a double cycle cover of G. We show that if a graph G is at most 5 edges short of being 4-edge-connected, then exactly one of these holds: G ? ??₃, G has at least one cut-edge, or G is contractible to the Petersen graph. We also improve a sufficient condition of Jaeger for G ? ??_2p+1(p ? N).