Graph minors. VI. Disjoint paths across a disc

Let G be a graph drawn on a disc, and let the vertices of G on the boundary of the disc be s₁, …, s_k, t₁, …, t_k in some order. When are there k vertex-disjoint paths of G joining s_i and t_i (1 ≤ i ≤ k), respectively? We give a structural characterization and a polynomial algorithm for this problem. We also solve the same question when the disc is replaced by a cylinder.     

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

Independent cycles with limited size in a graph

Letk and s be two positive integers with s≥3. LetG be a graph of ordern ≥sk. Writen =qk + r, 0 ≤r ≤k - 1. Suppose thatG has minimum degree at least (s - l)k. Then G containsk independent cyclesC ₁,C ₂,...,C _k such thats ≤l(C _i ) ≤q for 1 ≤i ≤r arnds ≤l(C _i ) ≤q + 1 fork -r <i ≤k, where l(C_i) denotes the length ofC _i .     

The irredundant ramsey number s(3,3,3) = 13

Let G₁, G₂,. …, G_t be an arbitrary t-edge coloring of K_n, where for each i ∈ {1,2, …, t}, G_i is the spanning subgraph of K_n consisting of all edges colored with the ith color. The irredundant Ramsey number s(q₁, q₂, …, q_t) is defined as the smallest integer n such that for any t-edge coloring of K_n, _i has an irredundant set of size q_i for at least one i ∈ {1,2, …,t}. It is proved that s(3,3,3) = 13, a result that improves the known bounds 12 ≤ s(3,3,3) ≤ 14.     

Small cycles and 2-factor passing through any given vertices in graphs

The theory of vertex-disjoint cycles and 2-factor of graphs has important applications in computer science and network communication. For a graph G, let σ ₂(G):=min?{d(u)+d(v)|uv ? E(G),u≠v}. In the paper, the main results of this paper are as follows:

1. Let k≥2 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k of length at most four such that v _i ∈V(C _i ) for all 1≤i≤k.
2. Let k≥1 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k such that:
   1. v _i ∈V(C _i ) for all 1≤i≤k.
   2. V(C ₁)∪???∪V(C _k )=V(G), and
   3. |C _i |≤4, 1≤i≤k?1.

Moreover, the condition on σ ₂(G)≥n+2k?2 is sharp.     

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.     

A lower bound for the packing chromatic number of the Cartesian product of cycles

Let G = (V, E) be a simple graph of order n and i be an integer with i ≥ 1. The set X _i ? V(G) is called an i-packing if each two distinct vertices in X _i are more than i apart. A packing colouring of G is a partition X = {X ₁, X ₂, …, X _k } of V(G) such that each colour class X _i is an i-packing. The minimum order k of a packing colouring is called the packing chromatic number of G, denoted by χ_ρ(G). In this paper we show, using a theoretical proof, that if q = 4t, for some integer t ≥ 3, then 9 ≤ χ_ρ(C ₄ □ C _q ). We will also show that if t is a multiple of four, then χ_ρ(C ₄ □ C _q ) = 9.     

An improved linear edge bound for graph linkages

A graph is said to be k-linked if it has at least 2k vertices and for every sequence s₁,…,s_k,t₁,…,t_k of distinct vertices there exist disjoint paths P₁,…,P_k such that the ends of P_i are s_i and t_i. Bollobás and Thomason showed that if a simple graph G on n vertices is 2k-connected and G has at least 11kn edges, then G is k-linked. We give a relatively simple inductive proof of the stronger statement that 8kn edges and 2k-connectivity suffice, and then with more effort improve the edge bound to 5kn.     

Mixed ramsey numbers: Chromatic numbers versus graphs

For positive integers n₁, n₂, …, n_I and graphs G_I+1, G_I+2, …, G_k, 1 ≤ / < k, the mixed Ramsey number _χ(n₁, …, n₁, G_I+1, …, G_k) is define as the least positive integer p such that for each factorization K_p = F₁⊕ … ⊕ F_⊕ F_I+1⊕ … ⊕ F_k, it it follows that χ(F_i) ≥ n_i for some i, 1 ? i ? l, or G_i is a subgraph of F_i for some i, l < i ? k. Formulas are presented for maxed Ramsey numbers in which the graphs G_I+1, G_I+2, …, G_k are connected, and in which k = I+1 and G_I+1 is arbitray.     

Job shop scheduling with unit time operations under resource constraints and release dates

We consider the problem of job shop scheduling with m machines and n jobs J_i, each consisting of l_i unit time operations. There are s distinct resources R_h and a quantity q_h available of each one. The execution of the j-th operation of J_i requires the presence of u_ijh units of R_h, 1 ≤i≤n, 1 ≤j≤l_i, and 1 ≤h≤s. In addition, each J_i has a release date r_i, that is J_i cannot start before time r_i. We describe algorithms for finding schedules having minimum length or sum of completion times of the jobs. Let l=max{l_i} and u=|{u_ijh}|. If m, u and l are fixed, then both algorithms terminate within polynomial time.     

Nonsingular Equations over Groups II

Let G be a group, t an element distinct from G, and r(t) = g ₁ t ^{l ₁} …g _k t ^{l _k}  ∈ G* ?t?, where each g _i is an element of G order greater than 2, and the l _i are nonzero integers such that l ₁ + l ₂+…+l _k  ≠ 0 and |l _i | ≠ |l _j | for i ≠ j. We prove that if k = 4, then the natural map from G to the one-relator product ?G*t | r(t)? is injective. This together with previous results show that the natural map from G is injective for k ≥ 1.     

Sharp bounds for the number of 3‐independent partitions and the chromaticity of bipartite graphs

Given a graph G and an integer k ≥ 1, let α(G, k) denote the number of k‐independent partitions of G. Let ??^?s(p,q) (resp., ??₂^?s(p,q)) denote the family of connected (resp., 2‐connected) graphs which are obtained from the complete bipartite graph K_p,q by deleting a set of s edges, where p ≥ q ≥ 2. This paper first gives a sharp upper bound for α(G,3), where G ∈ ?? ^?s(p,q) and 0 ≤ s ≤ (p ? 1)(q ? 1) (resp., G ∈ ?? ₂^?s(p,q) and 0 ≤ s ≤ p + q ? 4). These bounds are then used to show that if G ∈ ?? ^?s(p,q) (resp., G ∈ ?? ₂^?s (p,q)), then the chromatic equivalence class of G is a subset of the union of the sets ??^?s_i(p+i,q?i) where max and s_i = s ? i(p?q+i) (resp., a subset of ??₂^?s(p,q), where either 0 ≤ s ≤ q ? 1, or s ≤ 2q ? 3 and p ≥ q + 4). By applying these results, we show finally that any 2‐connected graph obtained from K_p,q by deleting a set of edges that forms a matching of size at most q ? 1 or that induces a star is chromatically unique. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 48–77, 2001     

On (s,t)-supereulerian graphs in locally highly connected graphs

Given two nonnegative integers s and t, a graph G is (s,t)-supereulerian if for any disjoint sets X,Y⊂E(G) with |X|≤s and |Y|≤t, there is a spanning eulerian subgraph H of G that contains X and avoids Y. We prove that if G is connected and locally k-edge-connected, then G is (s,t)-supereulerian, for any pair of nonnegative integers s and t with s+t≤k−1. We further show that if s+t≤k and G is a connected, locally k-edge-connected graph, then for any disjoint sets X,Y⊂E(G) with |X|≤s and |Y≤t, there is a spanning eulerian subgraph H that contains X and avoids Y, if and only if G−Y is not contractible to K₂ or to K_2,l with l odd.     

On B(n,k) 2-groups

A finite group G is said to be a B(n, k) group if for any n-element subset {a ₁,…, a _n } of G, |{a _i a _j |1 ≤ i, j ≤ n}| ≤k. In this article, we give characterizations of the B(5, 19) 2-groups, and the B(6, k) 2-groups for 21 ≤ k ≤ 28.     

On 2-factors with cycles containing specified vertices in a bipartite graph

Let k≥1 be an integer and G=(V ₁,V ₂;E) a bipartite graph with |V ₁|=|V ₂|=n such that n≥2k+2. Our result is as follows: If $d(x)+d(y)\geq \lceil\frac{4n+k}{3}\rceil$ for any nonadjacent vertices x∈V ₁ and y∈V ₂, then for any k distinct vertices z ₁,…,z _k , G contains a 2-factor with k+1 cycles C ₁,…,C _k+1 such that z _i ∈V(C _i ) and l(C _i )=4 for each i∈{1,…,k}.     

Relation between frobenius and 2-frobenius groups with order components of finite groups

IfG is a finite group, we define its prime graph Г(G), as follows: its vertices are the primes dividing the order ofG and two verticesp, q are joined by an edge, if there is an element inG of orderpq. We denote the set of all the connected components of the graph Г(G) by T(G)= {π_i(G), fori = 1,2, …,t(G)}, where t(G) is the number of connected components of Г(G). We also denote by π(n) the set of all primes dividingn, wheren is a natural number. Then ¦G¦ can be expressed as a product of m₁, m₂, …, m_t(G), where m_i’s are positive integers with π(m_i) = π_i. Thesem _i ’s are called the order components ofG. LetOC(G) := {m ₁,m ₂, …,m _t (G)} be the set of order components ofG. In this paper we prove that, if G is a finite group andOC(G) =OC(M), where M is a finite simple group witht(M) ≥ 2, thenG is neither Frobenius nor 2-Frobenius.     

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).     

Path Ramsey numbers in multicolorings

In this paper we consider the general Ramsey number problem for paths when the complete graph is colored with k colors. Specifically, given paths P_i1, P_i2,…, P_ik with i₁, i₂,…, i_k vertices, we determine for certain i_j (1 ≤ j ≤ k) the smallest positive integer n such that a k coloring of the complete graph K_n contains, for some l, a P_il in the lth color. For k = 3, given i₂, i₃, the problem is solved for all but a finite number of values of i₁. The procedure used in the proof uses an improvement of an extremal theorem for paths by P. Erdös and T. Gallai.     

Disjoint triangles and quadrilaterals in a graph

Let G be a simple graph of order n and s and k be two positive integers. Brandt et al. obtained the following result: If s?k, n?3s+4(k-s) and σ₂(G)?n+s, then G contains k disjoint cycles C₁,…,C_k satisfying |C_i|=3 for 1?i?s and |C_i|?4 for s<i?k. In the above result, the length of C_i is not specified for s<i?k. We get a result specifying the length of C_i for each s<i?k if n?3s+4(k-s)+3.