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.     

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

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.     

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

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.     

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.     

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.     

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.     

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

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

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      

The 2-pebbling property for dense graphs

Given a distribution of pebbles on the vertices of a connected graph G, a pebbling move on G consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The pebbling number f(G) is the smallest number m such that for every distribution of m pebbles and every vertex v,a pebble can be moved to v. A graph G is said to have the 2-pebbling property if for any distribution with more than 2f(G) q pebbles, where q is the number of vertices with at least one pebble, it is possible,using pebbling moves, to get two pebbles to any vertex. Snevily conjectured that G(s,t) has the 2-pebbling property, where G(s, t) is a bipartite graph with partite sets of size s and t (s ≥ t). Similarly, the-pebbling number f (G) is the smallest number m such that for every distribution of m pebbles and every vertex v, pebbles can be moved to v. Herscovici et al. conjectured that f(G) ≤ 1.5n + 8-6 for the graph G with diameter 3, where n = |V (G)|. In this paper, we prove that if s ≥ 15 and G(s, t) has minimum degree at least (s+1)/ 2 , then f (G(s, t)) = s + t, G(s, t) has the 2-pebbling property and f (G(s, t)) ≤ s + t + 8(-1). In other words, we extend a result due to Czygrinow and Hurlbert, and show that the above Snevily conjecture and Herscovici et al. conjecture are true for G(s, t) with s ≥ 15 and minimum degree at least (s+1)/ 2 .     

Greedy F-colorings of graphs

Let G=(V,E) be a connected graph. For a symmetric, integer-valued function δ on V×V, where K is an integer constant, N₀ is the set of nonnegative integers, and Z is the set of integers, we define a C-mapping by F(u,v,m)=δ(u,v)+m−K. A coloring c of G is an F-coloring if F(u,v,|c(u)−c(v)|)?0 for every two distinct vertices u and v of G. The maximum color assigned by c to a vertex of G is the value of c, and the F-chromatic number F(G) is the minimum value among all F-colorings of G. For an ordering of the vertices of G, a greedy F-coloring c of s is defined by (1) c(v₁)=1 and (2) for each i with 1?i<n, c(v_i+1) is the smallest positive integer p such that F(v_j,v_i+1,|c(v_j)−p|)?0, for each j with 1?j?i. The greedy F-chromatic number gF(s) of s is the maximum color assigned by c to a vertex of G. The greedy F-chromatic number of G is gF(G)=min{gF(s)} over all orderings s of V. The Grundy F-chromatic number is GF(G)=max{gF(s)} over all orderings s of V. It is shown that gF(G)=F(G) for every graph G and every F-coloring defined on G. The parameters gF(G) and GF(G) are studied and compared for a special case of the C-mapping F on a connected graph G, where δ(u,v) is the distance between u and v and .     

The upper traceable number of a graph

For a nontrivial connected graph G of order n and a linear ordering s: v ₁, v ₂, …, v _n of vertices of G, define . The traceable number t(G) of a graph G is t(G) = min{d(s)} and the upper traceable number t ⁺(G) of G is t ⁺(G) = max{d(s)}, where the minimum and maximum are taken over all linear orderings s of vertices of G. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs G for which t ⁺(G) − t(G) = 1 are characterized and a formula for the upper traceable number of a tree is established. Research supported by Srinakharinwirot University, the Thailand Research Fund and the Commission on Higher Education, Thailand under the grant number MRG 5080075.     

The circular dimension of a graph

A graph is a pair (V, I), V being the vertices and I being the relation of adjacency on V. Given a graph G, then a collection of functions {f_i}^m_n=1, each f_i mapping each vertex of V into anarc on a fixed circle, is said to define an m-arc intersection model for G if for all x,y ? V, xly ? (∨_i?m)(f_i(x)∩f_i(y)≠Ø). The circular dimension of a graph G is defined as the smallest integer m such that G has an m-arc intersection model. In this paper we establish that the maximum circular dimension of any complete partite graph having n vertices is the largest integer p such that 2^p+p?n+1.     

The triangle-free process

Consider the following stochastic graph process. We begin with G₀, the empty graph on n vertices, and form Gi by adding a randomly chosen edge ei to Gi−1 where ei is chosen uniformly at random from the collection of pairs of vertices that neither appear as edges in Gi−1 nor form triangles when added as edges to Gi−1. Let the random variable M be the number of edges in the maximal triangle free graph generated by this process. We prove that asymptotically almost surely . This resolves a conjecture of Spencer. Furthermore, the independence number of GM is asymptotically almost surely , which implies that the Ramsey number R(3,t) is bounded below by a constant times t²/logt (a fact that was previously established by Jeong Han Kim). The methods introduced here extend to the K₄-free process, thereby establishing the bound R(4,t)=Ω(t5/2/log²t).     

<Emphasis Type="Italic">s</Emphasis>-Vertex Pancyclic Index

A graph G is vertex pancyclic if for each vertex \({v \in V(G)}\) , and for each integer k with 3 ≤ k ≤ |V(G)|, G has a k-cycle C _k such that \({v \in V(C_k)}\) . Let s ≥ 0 be an integer. If the removal of at most s vertices in G results in a vertex pancyclic graph, we say G is an s-vertex pancyclic graph. Let G be a simple connected graph that is not a path, cycle or K _1,3. Let l(G) = max{m : G has a divalent path of length m that is not both of length 2 and in a K ₃}, where a divalent path in G is a path whose interval vertices have degree two in G. The s-vertex pancyclic index of G, written vp _s (G), is the least nonnegative integer m such that L ^m (G) is s-vertex pancyclic. We show that for a given integer s ≥ 0,

$vp_s(G)\le \left\{\begin{array}{l@{\quad}l}\qquad\quad\quad\,\,\,\,\,\,\, l(G)+s+1: \quad {\rm if} \,\, 0 \le s \le 4 \\ l(G)+\lceil {\rm log}_2(s-2) \rceil+4: \quad {\rm if} \,\, s \ge 5 \end{array}\right.$

And we improve the bound for essentially 3-edge-connected graphs. The lower bound and whether the upper bound is sharp are also discussed.

     

A note on balanced bipartitions

A balanced bipartition of a graph G is a bipartition V₁ and V₂ of V(G) such that −1≤|V₁|−|V₂|≤1. Bollobás and Scott conjectured that if G is a graph with m edges and minimum degree at least 2 then G admits a balanced bipartition V₁,V₂ such that max{e(V₁),e(V₂)}≤m/3, where e(V_i) denotes the number of edges of G with both ends in V_i. In this note, we prove this conjecture for graphs with average degree at least 6 or with minimum degree at least 5. Moreover, we show that if G is a graph with m edges and n vertices, and if the maximum degree Δ(G)=o(n) or the minimum degree δ(G)→∞, then G admits a balanced bipartition V₁,V₂ such that max{e(V₁),e(V₂)}≤(1+o(1))m/4, answering a question of Bollobás and Scott in the affirmative. We also provide a sharp lower bound on max{e(V₁,V₂):V₁,V₂ is a balanced bipartition of G}, in terms of size of a maximum matching, where e(V₁,V₂) denotes the number of edges between V₁ and V₂.     

Perfect Matchings and K 4 3 -Tilings in Hypergraphs of Large Codegree

For a k-graph F, let t _l (n, m, F) be the smallest integer t such that every k-graph G on n vertices in which every l-set of vertices is included in at least t edges contains a collection of vertex-disjoint F-subgraphs covering all but at most m vertices of G. Let K _m ^k denote the complete k-graph on m vertices. The function $t_{k-1} (kn, 0, K_k^k)For a k-graph F, let t _l (n, m, F) be the smallest integer t such that every k-graph G on n vertices in which every l-set of vertices is included in at least t edges contains a collection of vertex-disjoint F-subgraphs covering all but at most m vertices of G. Let K _m ^k denote the complete k-graph on m vertices. The function (i.e. when we want to guarantee a perfect matching) has been previously determined by Kühn and Osthus [9] (asymptotically) and by R?dl, Ruciński, and Szemerédi [13] (exactly). Here we obtain asymptotic formulae for some other l. Namely, we prove that for any and , . Also, we present various bounds in another special but interesting case: t ₂(n, m, K ₄³) with m = 0 or m = o(n), that is, when we want to tile (almost) all vertices by copies of K ₄³, the complete 3-graph on 4 vertices. Reverts to public domain 28 years from publication. Oleg Pikhurko: Partially supported by the National Science Foundation, Grant DMS-0457512.