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     

Multiplicative infinite loop space theory

Let G be a finitely presented group given by its pre-abelian presentation <X1,…,Xm; Xe11ζ1,…,Xemmζ,ζm+1,…>, where ei≥0 for i = 1,…, m and ζj?G′ for j≥1. Let N be the subgroup of G generated by the normal subgroups [xeii, G] for i = 1,…, m. Then Dn+2(G)≡γn+2(G) (modNG′) for all n≥0, where G” is the second commutator subgroup of G,γn+2(G) is the (n+2)th term of the lower central series of G and Dn+2(G) = G∩(1+△n+2(G)) is the (n+2)th dimension subgroup of G.     

The multi‐color Ramsey number of an odd cycle

Let r_k(G) be the k‐color Ramsey number of a graph G. It is shown that for k?2 and that r_k(C_{2m+ 1})?(c^kk!)^1/m if the Ramsey graphs of r_k(C_{2m+ 1}) are not far away from being regular. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 324–328, 2009     

Linear preservers of orthogonal decomposable Tensors

Let G be a subgroup of the symmetric group S_m and V be an n-dimensional unitary space where nm. Let V(G) be the symmetry class of tensors over V associated with G and the identity character. Let D(G) be the set of all decomposable elements of V(G) and O(G) be its subset consisting of all nonzero decomposable tensors x ₁ ^?…^? x_m such that {x ₁,…,x_m } is an orthogonal set. In this paper we study the structure of linear mappings on V(G) that preserve one of the following subsets: (i)O(G), (ii) D(G)\(O(G)?{0}).     

K4−‐factor in a graph

Let G be a graph of order 4k and let δ(G) denote the minimum degree of G. Let F be a given connected graph. Suppose that |V(G)| is a multiple of |V(F)|. A spanning subgraph of G is called an F‐factor if its components are all isomorphic to F. In this paper, we prove that if δ(G)≥5/2k, then G contains a K₄^?‐factor (K₄^? is the graph obtained from K₄ by deleting just one edge). The condition on the minimum degree is best possible in a sense. In addition, the proof can be made algorithmic. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 111–128, 2002     

Crossing properties of graph reliability functions

Let G be a graph and p ϵ (0, 1). Let A(G, p) denote the probability that if each edge of G is selected at random with probability p then the resulting spanning subgraph of G is connected. Then A(G, p) is a polynomial in p. We prove that for every integer k ≥ 1 and every k‐tuple (m₁, m₂, … ,m_k) of positive integers there exist infinitely many pairs of graphs G₁ and G₂ of the same size such that the polynomial A(G₁, p) − A(G₂, p) has exactly k roots x₁ < x₂ < ··· < x_k in (0, 1) such that the multiplicity of x_i is m_i. We also prove the same result for the two‐terminal reliability polynomial, defined as the probability that the random subgraph as above includes a path connecting two specified vertices. These results are based on so‐called A‐ and T‐multiplying constructions that are interesting in themselves. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 206–221, 2000     

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.     

GENERALISED MAXIMAL INDEPENDENCE AND CLIQUE NUMBERS OF GRAPHS

Abstract

A set B of vertices of a graph G = (V,E) is a k-maximal independent set (kMIS) if B is independent but for all ?-subsets X of B, where ? ? k—1, and all (? + 1)-subsets Y of V—B, the set (B—X) u Y is dependent. A set S of vertices of C is a k-maximal clique (kMc) of G iff S is a kMIS of [Gbar]. Let β_k, (G) (w_k(G) respectively) denote the smallest cardinality of a kMIS (kMC) of G—obviously β_k(G) = w_k([Gbar]). For the sequence m₁ ? m₂ ?…? m_n = r of positive integers, necessary and sufficient conditions are found for a graph G to exist such that w_k(G) = m_k for k = 1,2,…,n and w(G) = r (equivalently, β_k(G) = m_k for k = 1,2,…,n and β(G) = r). Define s_k(?,m) to be the largest integer such that for every graph G with at most s_k(?,m) vertices, β_k(G) ? ? or w_k(G) ? m. Exact values for s_k(?,m) if k ≥ 2 and upper and lower bounds for s₁(?,m) are de termined.     

Edge disjoint Hamilton cycles in graphs

Let G be a graph of order n and k ≥ 0 an integer. It is conjectured in [8] that if for any two vertices u and v of a 2(k + 1)‐connected graph G,d _G (u,v) = 2 implies that max{d(u;G), d(v;G)} ≥ (n/2) + 2k, then G has k + 1 edge disjoint Hamilton cycles. This conjecture is true for k = 0, 1 (see cf. [3] and [8]). It will be proved in this paper that the conjecture is true for every integer k ≥ 0. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 8–20, 2000     

Quasi‐randomness of graph balanced cut properties

Quasi‐random graphs can be informally described as graphs whose edge distribution closely resembles that of a truly random graph of the same edge density. Recently, Shapira and Yuster proved the following result on quasi‐randomness of graphs. Let k ≥ 2 be a fixed integer, α₁,…,α_k be positive reals satisfying \begin{align*}\sum_{i} \alpha_i = 1\end{align*} and (α₁,…,α_k)≠(1/k,…,1/k), and G be a graph on n vertices. If for every partition of the vertices of G into sets V ₁,…,V _k of size α₁n,…,α_kn, the number of complete graphs on k vertices which have exactly one vertex in each of these sets is similar to what we would expect in a random graph, then the graph is quasi‐random. However, the method of quasi‐random hypergraphs they used did not provide enough information to resolve the case (1/k,…,1/k) for graphs. In their work, Shapira and Yuster asked whether this case also forces the graph to be quasi‐random. Janson also posed the same question in his study of quasi‐randomness under the framework of graph limits. In this paper, we positively answer their question. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

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     

Long cycles passing through a specified path in a graph

For a graph G and an integer k ≥ 1, let ς_k(G) = d_G(v_i): {v₁, …, v_k} is an independent set of vertices in G}. Enomoto proved the following theorem. Let s ≥ 1 and let G be a (s + 2)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, ς₂(G) − s} passing through any path of length s. We generalize this result as follows. Let k ≥ 3 and s ≥ 1 and let G be a (k + s − 1)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, − s} passing through any path of length s. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 177–184, 1998     

Coloring of distance graphs with intervals as distance sets

Let D be a set of positive integers. The distance graph G(Z,D) with distance set D is the graph with vertex set Z in which two vertices x,y are adjacent if and only if |x−y|D. The fractional chromatic number, the chromatic number, and the circular chromatic number of G(Z,D) for various D have been extensively studied recently. In this paper, we investigate the fractional chromatic number, the chromatic number, and the circular chromatic number of the distance graphs with the distance sets of the form D_m,[k,k^′]={1,2,…,m}−{k,k+1,…,k^′}, where m, k, and k^′ are natural numbers with m≥k^′≥k. In particular, we completely determine the chromatic number of G(Z,D_m,[2,k^′]) for arbitrary m, and k^′.     

Edge‐face chromatic number and edge chromatic number of simple plane graphs

Given a simple plane graph G, an edge‐face k‐coloring of G is a function ? : E(G) ∪ F(G) → {1,…,k} such that, for any two adjacent or incident elements a, b ∈ E(G) ∪ F(G), ?(a) ≠ ?(b). Let χ_e(G), χ_ef(G), and Δ(G) denote the edge chromatic number, the edge‐face chromatic number, and the maximum degree of G, respectively. In this paper, we prove that χ_ef(G) = χ_e(G) = Δ(G) for any 2‐connected simple plane graph G with Δ (G) ≥ 24. © 2005 Wiley Periodicals, Inc. J Graph Theory     

On the convex hull of the multiform numerical range

Let A ₁,…,A_m be nxn hermitian matrices. Definine

W(A ₁,…,A_m )={(xA₁x ^?,…xA_mx ^?):x?C ⁿ ,xx ^?=1}. We will show that every point in the convex hull of W(A ₁,…,A_m ) can be represented as a convex combination of not more than k(m,n) points in W(A ₁,…,A_m ) where k(m,n)=min{n,[√m]+δ _n ² _m+1}.     

Tension polynomials of graphs

The tension polynomial F_G(k) of a graph G, evaluating the number of nowhere‐zero ?_k‐tensions in G, is the nontrivial divisor of the chromatic polynomial χ_G(k) of G, in that χ_G(k) = k^c(G)F_G(k), where c(G) denotes the number of components of G. We introduce the integral tension polynomial I_G(k), which evaluates the number of nowhere‐zero integral tensions in G with absolute values smaller than k. We show that 2^r(G)F_G(k)≥I_G(k)≥ (r(G)+1)F_G(k), where r(G)=|V(G)|?c(G), and, for every k>1, F_G(k+1)≥ F_G(k)˙k / (k?1) and I_G(k+1)≥I_G(k)˙k/(k?1). © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 137–146, 2002     

Sharp bounds for decompositions of graphs into complete r-partite subgraphs

If G is a graph on n vertices and r ≥ 2, we let m_r(G) denote the minimum number of complete multipartite subgraphs, with r or fewer parts, needed to partition the edge set, E(G). In determining m_r(G), we may assume that no two vertices of G have the same neighbor set. For such reducedgraphs G, we prove that m_r(G) ≥ log₂ (n + r − 1)/r. Furthermore, for each k ≥ 0 and r ≥ 2, there is a unique reduced graph G = G(r, k) with m_r(G) = k for which equality holds. We conclude with a short proof of the known eigenvalue bound m_r(G) ≥ max{n₊ (G, n₋(G)/(r − 1)}, and show that equality holds if G = G(r, k). © 1996 John Wiley & Sons, Inc.     

Cohen–Macaulayness and Limit Behavior of Depth for Powers of Cover Ideals

Let 𝕂 be a field, and let R = 𝕂[x ₁,…, x _n ] be the polynomial ring over 𝕂 in n indeterminates x ₁,…, x _n . Let G be a graph with vertex-set {x ₁,…, x _n }, and let J be the cover ideal of G in R. For a given positive integer k, we denote the kth symbolic power and the kth bracket power of J by J ^(k) and J ^[k], respectively. In this paper, we give necessary and sufficient conditions for R/J ^k , R/J ^(k), and R/J ^[k] to be Cohen–Macaulay. We also study the limit behavior of the depths of these rings.     

Complete Multipartite Graphs and the Relaxed Coloring Game

Let k be a positive integer, d be a nonnegative integer, and G be a finite graph. Two players, Alice and Bob, play a game on G by coloring the uncolored vertices with colors from a set X of k colors. At all times, the subgraph induced by a color class must have maximum degree at most d. Alice wins the game if all vertices are eventually colored; otherwise, Bob wins. The least k such that Alice has a winning strategy is called the d-relaxed game chromatic number of G, denoted ?? _g ^d (G). It is known that there exist graphs such that ?? _g ⁰(G)?=?3, but ?? _g ¹(G)?>?3. We will show that for all positive integers m, there exists a complete multipartite graph G such that m?????? _g ⁰(G)?<??? _g ¹(G).