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     

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.     

Graphs with unavoidable subgraphs with large degrees

Let ??(n, m) denote the class of simple graphs on n vertices and m edges and let G ∈ ?? (n, m). There are many results in graph theory giving conditions under which G contains certain types of subgraphs, such as cycles of given lengths, complete graphs, etc. For example, Turan's theorem gives a sufficient condition for G to contain a K_{k + 1} in terms of the number of edges in G. In this paper we prove that, for m = αn², α > (k - 1)/2k, G contains a K_{k + 1}, each vertex of which has degree at least f(α)n and determine the best possible f(α). For m = ?n²/4? + 1 we establish that G contains cycles whose vertices have certain minimum degrees. Further, for m = αn², α > 0 we establish that G contains a subgraph H with δ(H) ≥ f(α, n) and determine the best possible value of f(α, n).     

Covering a graph with cycles passing through given edges

We propose a conjecture: for each integer k ≥ 2, there exists N(k) such that if G is a graph of order n ≥ N(k) and d(x) + d(y) ≥ n + 2k - 2 for each pair of non-adjacent vertices x and y of G, then for any k independent edges e₁, …, e_k of G, there exist k vertex-disjoint cycles C₁, …, C_k in G such that e_i ∈ E(C_i) for all i ∈ {1, …, k} and V(C₁ ∪ ···∪ C_k) = V(G). If this conjecture is true, the condition on the degrees of G is sharp. We prove this conjecture for the case k = 2 in the paper. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 105–109, 1997     

Chromatic factorizations of a graph

Let n₁ ? n₂ ? …? ? n_k ? 2 be integers. We say that G has an (n₁, n₂, …?, n_k-chromatic factorization if G) can be edge-factored as G₁ ⊕ G₂ ⊕ …? ⊕ G_k with χ(G_i) = nA_i, for i = 1,2,…, k. The following results are proved:

• i If (n₁ ? 1)n₂ …? n_k < χ(G) ? n₁n₂ …? n_k, then G has an (n₁, n₂, …?, n_k)-chromatic factorization.
• ii If n₁ + n₂ + …? + n_k ? (k - 1) ? n ? n₁n₂ …? n_k, then K_n has an (n₁, n₂, …?, n_k)-chromatic factorization.

     

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     

Decreasing the diameter of bounded degree graphs

Let f_d (G) denote the minimum number of edges that have to be added to a graph G to transform it into a graph of diameter at most d. We prove that for any graph G with maximum degree D and n > n₀ (D) vertices, f₂(G) = n − D − 1 and f₃(G) ≥ n − O(D³). For d ≥ 4, f_d (G) depends strongly on the actual structure of G, not only on the maximum degree of G. We prove that the maximum of f_d (G) over all connected graphs on n vertices is n/⌊d/2 ⌋ − O(1). As a byproduct, we show that for the n‐cycle C_n, f_d (C_n) = n/(2⌊d/2 ⌋ − 1) − O(1) for every d and n, improving earlier estimates of Chung and Garey in certain ranges. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 161–172, 2000     

Posets and planar graphs

A k-decomposition (G₁,…,G_k) of a graph G is a partition of its edge set to form k spanning subgraphs G₁,…,G_k. The classical theorem of Nordhaus and Gaddum bounds χ(G₁) + χ(G₂) and χ(G₁)χ(G₂) over all 2-decompositions of K_n. For a graph parameter p, let p(k;G) denote the maximum of over all k-decompositions of the graph G. The clique number ω, chromatic number χ, list chromatic number χℓ, and Szekeres–Wilf number σ satisfy ω(2;K_n) = χ(2;K_n) = χℓ(2;K_n) = σ(2;K_n) = n + 1. We obtain lower and upper bounds for ω(k;K_n), χ(k;K_n), χℓ(k;K_n), and σ(k;K_n). The last three behave differently for large k. We also obtain lower and upper bounds for the maximum of χ(k;G) over all graphs embedded on a given surface. © 2005 Wiley Periodicals, Inc. J Graph Theory     

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.     

Partitioning complete multipartite graphs by monochromatic trees

The tree partition number of an r‐edge‐colored graph G, denoted by t_r(G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex‐disjoint monochromatic trees. We determine t₂(K(n₁, n₂,…, n_k)) of the complete k‐partite graph K(n₁, n₂,…, n_k). In particular, we prove that t₂(K(n, m)) = ? (m‐2)/2ⁿ? + 2, where 1 ≤ n ≤ m. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 133–141, 2005     

A degree condition for the circumference of a graph

We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let m be any positive integer. Suppose G is a 2-connected graph with vertices x₁,…,x_n and edge set E that satisfies the property that, for any two integers j and k with j < k, x_jx_k ? E, d(x_i) ? j and d(x_k) ? K - 1, we have (1) d(x_i) + d(x_k ? m if j + k ? n and (2) if j + k < n, either m ? n or d(x_j) + d(x_k) ? min(K + 1,m). Then c(G) ? min(m, n). This result unifies previous results of J.C. Bermond and M. Las Vergnas, respectively.     

On the Grassmann modules for the unitary groups

Let V be 2n-dimensional vector space over a field 𝕂 equipped with a nondegenerate skew-ψ-Hermitian form f of Witt index n ≥ 1, let 𝕂₀ ? 𝕂 be the fix field of ψ and let G denote the group of isometries of (V, f). For every k ∈ {1, …, 2n}, there exist natural representations of the groups G ? U(2n, 𝕂/𝕂₀) and H = G ∩ SL(V) ? SU(2n, 𝕂/𝕂₀) on the k-th exterior power of V. With the aid of linear algebra, we prove some properties of these representations. We also discuss some applications to projective embeddings and hyperplanes of Hermitian dual polar spaces.     

Some results on starlike trees and sunlike graphs

A tree is called starlike if it has exactly one vertex of degree greater than two. In [4] it was proved that two starlike treesG andH are cospectral if and only if they are isomorphic. We prove here that there exist no two non-isomorphic Laplacian cospectral starlike trees. Further, letG be a simple graph of ordern with vertex setV(G)={1,2, …,n} and letH={H ₁,H ₂, ...H _n } be a family of rooted graphs. According to [2], the rooted productG(H) is the graph obtained by identifying the root ofH _i with thei-th vertex ofG. In particular, ifH is the family of the paths $P_{k_1 } , P_{k_2 } , ..., P_{k_n } $ with the rooted vertices of degree one, in this paper the corresponding graphG(H) is called the sunlike graph and is denoted byG(k ₁,k ₂, …,k _n ). For any (x ₁,x ₂, …,x _n ) ∈I _* ⁿ , whereI _*={0,1}, letG(x ₁,x ₂, …,x _n ) be the subgraph ofG which is obtained by deleting the verticesi ₁, i₂, …,i _j ∈ V(G) (0≤j≤n), provided that $x_{i_1 } = x_{i_2 } = ... = x_{i_j } = 0$ . LetG(x ₁,x ₂,…, x _n] be the characteristic polynomial ofG(x ₁,x ₂,…, x _n ), understanding thatG[0, 0, …, 0] ≡ 1. We prove that $$G[k_1 , k_2 ,..., k_n ] = \Sigma _{x \in ^{I_ * ^n } } \left[ {\Pi _{i = 1}^n P_{k_i + x_i - 2} (\lambda )} \right]( - 1)^{n - (\mathop \Sigma \limits_{i = 1}^n x_i )} G[x_1 , x_2 , ..., x_n ]$$ where x=(x ₁,x ₂,…,x _n );G[k ₁,k ₂,…,k _n ] andP _n (γ) denote the characteristic polynomial ofG(k ₁,k ₂,…,k _n ) andP _n , respectively. Besides, ifG is a graph with λ₁(G)≥1 we show that λ₁(G)≤λ₁(G(k ₁,k ₂, ...,k _n )) < for all positive integersk ₁,k ₂,…,k _n , where λ₁ denotes the largest eigenvalue.     

An asymptotic version of a conjecture by Enomoto and Ota

In 2000, Enomoto and Ota [J Graph Theory 34 (2000), 163–169] stated the following conjecture. Let G be a graph of order n, and let n₁, n₂, …, n_k be positive integers with \begin{eqnarray*}\sum\nolimits_{{{i}} = {{1}}}^{{{k}}} {{n}}_{{{i}}} = {{n}}\end{eqnarray*}. If σ₂(G)≥n+ k?1, then for any k distinct vertices x₁, x₂, …, x_k in G, there exist vertex disjoint paths P₁, P₂, …, P_k such that |P_i|=n_i and x_i is an endpoint of P_i for every i, 1≤i≤k. We prove an asymptotic version of this conjecture in the following sense. For every k positive real numbers γ₁, …, γ_k with \begin{eqnarray*}\sum\nolimits_{{{i}} = {{1}}}^{{{k}}} \gamma_{{{i}}} = {{1}}\end{eqnarray*}, and for every ε>0, there exists n₀ such that for every graph G of order n≥n₀ with σ₂(G)≥n+ k?1, and for every choice of k vertices x₁, …, x_k∈V(G), there exist vertex disjoint paths P₁, …, P_k in G such that \begin{eqnarray*}\sum\nolimits_{{{i}} = {{1}}}^{{{k}}} |{{P}}_{{{i}}}| = {{n}}\end{eqnarray*}, the vertex x_i is an endpoint of the path P_i, and (γ_i?ε)n<|P_i|<(γ_i + ε)n for every i, 1≤i≤k. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 37–51, 2010     

A generalization of perfect graphs—i-perfect graphs

Let i be a positive integer. We generalize the chromatic number _X(G) of G and the clique number o(G) of G as follows: The i-chromatic number of G, denoted by _X(G), is the least number k for which G has a vertex partition V₁, V₂,…, V_k such that the clique number of the subgraph induced by each V_j, 1 ≤ j ≤ k, is at most i. The i-clique number, denoted by o_i(G), is the i-chromatic number of a largest clique in G, which equals [o(G/i]. Clearly _X1(G) = _X(G) and o₁(G) = o(G). An induced subgraph G′ of G is an i-transversal iff o(G′) = i and o(G − G′) = o(G) − i. We generalize the notion of perfect graphs as follows: (1) A graph G is i-perfect iff _Xi(H) = o_i(H) for every induced subgraph H of G. (2) A graph G is perfectly i-transversable iff either o(G) ≤ i or every induced subgraph H of G with o(H) > i contains an i-transversal of H. We study the relationships among i-perfect graphs and perfectly i-transversable graphs. In particular, we show that 1-perfect graphs and perfectly 1-transversable graphs both coincide with perfect graphs, and that perfectly i-transversable graphs form a strict subset of i-perfect graphs for every i ≥ 2. We also show that all planar graphs are i-perfect for every i ≥ 2 and perfectly i-transversable for every i ≥ 3; the latter implies a new proof that planar graphs satisfy the strong perfect graph conjecture. We prove that line graphs of all triangle-free graphs are 2-perfect. Furthermore, we prove for each i greater than or equal to2, that the recognition of i-perfect graphs and the recognition of perfectly i-transversable graphs are intractable and not likely to be in co-NP. We also discuss several issues related to the strong perfect graph conjecture. © 1996 John Wiley & Sons, Inc.     

On the Slowly Well Orderedness of εo

For α < ε₀, N_α denotes the number of occurrences of ω in the Cantor normal form of α with the base ω. For a binary number-theoretic function f let B(K; f) denote the length n of the longest descending chain (α₀, …, α_n–1) of ordinals <ε₀ such that for all i < n, Nα_i ≤ f (K, i). Simpson [2] called ε₀ as slowly well ordered when B (K; f) is totally defined for f (K; i) = K · (i+ 1). Let |n| denote the binary length of the natural number n, and |n|_k the k-times iterate of the logarithmic function |n|. For a unary function h let L(K; h) denote the function B (K; h₀(K; i)) with h₀(K, i) = K + |i| · |i|_h(i). In this note we show, inspired from Weiermann [4], that, under a reasonable condition on h, the functionL (K; h) is primitive recursive in the inverse h^–1 and vice versa.     

On three zero-sum Ramsey-type problems

For a graph G whose number of edges is divisible by k, let R(G,Z_k) denote the minimum integer r such that for every function f: E(K_r) ? Z_k there is a copy G¹ of G in K_r so that Σe∈E(G¹) f(e) = 0 (in Z_k). We prove that for every integer k₁ R(K_n, Z_k) ≤ n + O(k³ log k) provided n is sufficiently large as a function of k and k divides (). If, in addition, k is an odd prime-power then R(K_n, Z_k) ≤ n + 2k - 2 and this is tight if k is a prime that divides n. A related result is obtained for hypergraphs. It is further shown that for every graph G on n vertices with an even number of edges R(G,Z₂) ≤ n + 2. This estimate is sharp. © 1993 John Wiley & Sons, Inc.     

Finding a monochromatic subgraph or a rainbow path

For simple graphs G and H, let f(G,H) denote the least integer N such that every coloring of the edges of K_N contains either a monochromatic copy of G or a rainbow copy of H. Here we investigate f(G,H) when H = P_k. We show that even if the number of colors is unrestricted when defining f(G,H), the function f(G,P_k), for k = 4 and 5, equals the (k ? 2)‐ coloring diagonal Ramsey number of G. © 2006 Wiley Periodicals, Inc. J Graph Theory     

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