Integral trees of diameter 6

A graph G is called integral if all eigenvalues of its adjacency matrix A(G) are integers. In this paper, the trees T(p,q)•T(r,m,t) and K_1,s•T(p,q)•T(r,m,t) of diameter 6 are defined. We determine their characteristic polynomials. We also obtain for the first time sufficient and conditions for them to be integral. To do so, we use number theory and apply a computer search. New families of integral trees of diameter 6 are presented. Some of these classes are infinite. They are different from those in the existing literature. We also prove that the problem of finding integral trees of diameter 6 is equivalent to the problem of solving some Diophantine equations. We give a positive answer to a question of Wang et al. [Families of integral trees with diameters 4, 6 and 8, Discrete Appl. Math. 136 (2004) 349-362].     

Star-critical Ramsey numbers

The graph Ramsey numberR(G,H) is the smallest integer r such that every 2-coloring of the edges of K_r contains either a red copy of G or a blue copy of H. We find the largest star that can be removed from K_r such that the underlying graph is still forced to have a red G or a blue H. Thus, we introduce the star-critical Ramsey numberr_∗(G,H) as the smallest integer k such that every 2-coloring of the edges of K_r−K_1,r−1−k contains either a red copy of G or a blue copy of H. We find the star-critical Ramsey number for trees versus complete graphs, multiple copies of K₂ and K₃, and paths versus a 4-cycle. In addition to finding the star-critical Ramsey numbers, the critical graphs are classified for R(T_n,K_m), R(nK₂,mK₂) and R(P_n,C₄).     

Chromatic equivalence classes of complete tripartite graphs

Some necessary conditions on a graph which has the same chromatic polynomial as the complete tripartite graph K_m,n,r are developed. Using these, we obtain the chromatic equivalence classes for K_m,n,n (where 1≤m≤n) and K_m1,m2,m3 (where |m_i−m_j|≤3). In particular, it is shown that (i) K_m,n,n (where 2≤m≤n) and (ii) K_m1,m2,m3 (where |m_i−m_j|≤3, 2≤m_i,i=1,2,3) are uniquely determined by their chromatic polynomials. The result (i), proved earlier by Liu et al. [R.Y. Liu, H.X. Zhao, C.Y. Ye, A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs, Discrete Math. 289 (2004) 175-179], answers a conjecture (raised in [G.L. Chia, B.H. Goh, K.M. Koh, The chromaticity of some families of complete tripartite graphs (In Honour of Prof. Roberto W. Frucht), Sci. Ser. A (1988) 27-37 (special issue)]) in the affirmative, while result (ii) extends a result of Zou [H.W. Zou, On the chromatic uniqueness of complete tripartite graphs K_n1,n2,n3 J. Systems Sci. Math. Sci. 20 (2000) 181-186].     

New results on the energy of integral circulant graphs

Circulant graphs are an important class of interconnection networks in parallel and distributed computing. Integral circulant graphs play an important role in modeling quantum spin networks supporting the perfect state transfer as well. The integral circulant graph ICG_n(D) has the vertex set Z_n = {0, 1, 2, … , n − 1} and vertices a and b are adjacent if gcd(a − b, n) ∈ D, where D ⊆ {d : d∣n, 1 ? d < n}. These graphs are highly symmetric, have integral spectra and some remarkable properties connecting chemical graph theory and number theory. The energy of a graph was first defined by Gutman, as the sum of the absolute values of the eigenvalues of the adjacency matrix. Recently, there was a vast research for the pairs and families of non-cospectral graphs having equal energies. Following Bapat and Pati [R.B. Bapat, S. Pati, Energy of a graph is never an odd integer, Bull. Kerala Math. Assoc. 1 (2004) 129-132], we characterize the energy of integral circulant graph modulo 4. Furthermore, we establish some general closed form expressions for the energy of integral circulant graphs and generalize some results from Ili? [A. Ili?, The energy of unitary Cayley graphs, Linear Algebra Appl. 431 (2009), 1881-1889]. We close the paper by proposing some open problems and characterizing extremal graphs with minimal energy among integral circulant graphs with n vertices, provided n is even.     

Laplacian integral graphs in S(a, b)

Let G_n,m be the family of graphs with n vertices and m edges, when n and m are previously given. It is well-known that there is a subset of G_n,m constituted by graphs G such that the vertex connectivity, the edge connectivity, and the minimum degree are all equal. In this paper, S(a, b)-classes of connected (a, b)-linear graphs with n vertices and m edges are described, where m is given as a function of a,b∈N/2. Some of them have extremal graphs for which the equalities above are extended to algebraic connectivity. These graphs are Laplacian integral although they are not threshold graphs. However, we do build threshold graphs in S(a, b).     

Integral complete multipartite graphs

A graph is called integral if all eigenvalues of its adjacency matrix are integers. In this paper, we investigate integral complete r-partite graphs K_p1,p2,…,pr=K_{a1·p1,a2·p2,…,as·ps} with s=3,4. We can construct infinite many new classes of such integral graphs by solving some certain Diophantine equations. These results are different from those in the existing literature. For s=4, we give a positive answer to a question of Wang et al. [Integral complete r-partite graphs, Discrete Math. 283 (2004) 231-241]. The problem of the existence of integral complete multipartite graphs K_{a1·p1,a2·p2,…,as·ps} with arbitrarily large number s remains open.     

Oscillation criteria related to integral averaging technique for linear matrix Hamiltonian systems

By employing a generalized Riccati technique and an integral averaging technique, new oscillation criteria are established for the linear matrix Hamiltonian system U′=A(x)U+B(x)V, V′=C(x)U−A∗(x)V under the assumption that all A(x), B(x)=B∗(x)>0, and C(x)=C∗(x) are n×n matrices of real-valued continuous functions on the interval I=[x₀,∞) (−∞<x₀). These criteria extend, improve, and unify a number of existing results and also handle cases not covered by known criteria. Several interesting examples that illustrate the importance of our results are included.     

The graphs with only self-dual signings

Given a graph G, it is possible to attach positive and negative signs to its lines only, to its points only, or to both. The resulting structures are called respectively signed graphs, marked graphs and nets. The dual of each such structure is obtained by changing every sign in it. We determine all graphs G for which every suitable marked graph on G is self-dual (the M-dual graphs), and also the corresponding graphs G for signed graphs (S-dual) and for nets (N-dual.A graph G is M-dual if and only if G or ? is one of the graphs K_2m, 2K_m, mK₂, K_m + K₂ or 2C₄. The S-dual graphs are C₆, 2C₃, 2C₄, 2K_1n, 2nK₂, K_1,2n, nK_1,2, K_2n, K?_n and all graphs obtained from these by the addition of isolated points. Finally, the only N-dual graph other than -K_2n is 2K₂.     

The Ramsey numbers r(Pm, Kn)

This note evaluates the Ramsey numbers r(P_m,K_n), and discusses developments in 0 generalized Ramsey theory for graphs.     

The equivariant topology of stable Kneser graphs

The stable Kneser graph SG_n,k, n?1, k?0, introduced by Schrijver (1978) [19], is a vertex critical graph with chromatic number k+2, its vertices are certain subsets of a set of cardinality m=2n+k. Björner and de Longueville (2003) [5] have shown that its box complex is homotopy equivalent to a sphere, Hom(K₂,SG_n,k)?Sk. The dihedral group D2m acts canonically on SG_n,k, the group C₂ with 2 elements acts on K₂. We almost determine the (C₂×D2m)-homotopy type of Hom(K₂,SG_n,k) and use this to prove the following results.The graphs SG_2s,4 are homotopy test graphs, i.e. for every graph H and r?0 such that Hom(SG_2s,4,H) is (r−1)-connected, the chromatic number χ(H) is at least r+6.If k∉{0,1,2,4,8} and n?N(k) then SG_n,k is not a homotopy test graph, i.e. there are a graph G and an r?1 such that Hom(SG_n,k,G) is (r−1)-connected and χ(G)<r+k+2.     

Two characterizations of interchange graphs of complete m-partite graphs

A graph G is m-partite if its points can be partitioned into m subsets V₁,…,V_m such that every line joins a point in V_i with a point in V_j, i ≠ j. A complete m-partite graph contains every line joining V_i with V_j. A complete graph K_p has every pair of its p points adjacent. The nth interchange graph I_n(G) of G is a graph whose points can be identified with the K_n+1's of G such that two points are adjacent whenever the corresponding K_n+1's have a K_n in common.Interchange graphs of complete 2-partite and 3-partite graphs have been characterized, but interchange graphs of complete m-partite graphs for m > 3 do not seem to have been investigated. The main result of this paper is two characterizations of interchange graphs of complete m-partite graphs for m ≥ 2.     

Bipartite rainbow numbers of matchings

Given two graphs G and H, let f(G,H) denote the maximum number c for which there is a way to color the edges of G with c colors such that every subgraph H of G has at least two edges of the same color. Equivalently, any edge-coloring of G with at least rb(G,H)=f(G,H)+1 colors contains a rainbow copy of H, where a rainbow subgraph of an edge-colored graph is such that no two edges of it have the same color. The number rb(G,H) is called the rainbow number ofHwith respect toG, and simply called the bipartite rainbow number ofH if G is the complete bipartite graph K_m,n. Erd?s, Simonovits and Sós showed that rb(K_n,K₃)=n. In 2004, Schiermeyer determined the rainbow numbers rb(K_n,K_k) for all n≥k≥4, and the rainbow numbers rb(K_n,kK₂) for all k≥2 and n≥3k+3. In this paper we will determine the rainbow numbers rb(K_m,n,kK₂) for all k≥1.     

Sphericity exceeds cubicity for almost all complete bipartite graphs

We will prove that sphericity exceeds cubicity for complete bipartite graphs K(m,n) with max (m,n) > n₀, that sph K(n,n) ≥ n, and that as a result of the latter there is a complete bipartite graph with sphericity exceeding cubicity for every value of cubicity at least 6. This answers the question of Fishburn [1].     

Strongly regular graphs and finite Ramsey theory

Some connections between strongly regular graphs and finite Ramsey theory are drawn. Let B_n denote the graph K₂+K?_n. If there exists a strongly regular graph with parameters (υ, k, λ, μ), then the Ramsey number r(B_λ+1, B_{υ?2k+μ ?1})?υ+1. We consider the implications of this inequality for both Ramsey theory and the theory of strongly regular graphs.     

On the Ramsey number of trees versus graphs with large clique number

Chvátal established that r(T_m, K_n) = (m – 1)(n – 1) + 1, where T_m is an arbitrary tree of order m and K_n is the complete graph of order n. This result was extended by Chartrand, Gould, and Polimeni who showed K_n could be replaced by a graph with clique number n and order n + 1 provided n ≧ 3 and m ≧ 3. We further extend these results to show that K_n can be replaced by any graph on n + 2 vertices with clique number n, provided n ≧ 5 and m ≧ 4. We then show that further extensions, in particular to graphs on n + 3 vertices with clique number n are impossible. We also investigate the Ramsey number of trees versus complete graphs minus sets of independent edges. We show that r(T_m, K_n –tK₂) = (m – 1)(n – t – 1) + 1 for m ≧ 3, n ≧ 6, where T_m is any tree of order m except the star, and for each t, O ≦ t ≦ [(n – 2)/2].     

On a ramification bound of torsion semi-stable representations over a local field

Let p be a rational prime, k be a perfect field of characteristic p, W=W(k) be the ring of Witt vectors, K be a finite totally ramified extension of Frac(W) of degree e and r be a non-negative integer satisfying r<p−1. In this paper, we prove the upper numbering ramification group for j>u(K,r,n) acts trivially on the pn-torsion semi-stable GK-representations with Hodge-Tate weights in {0,…,r}, where u(K,0,n)=0, u(K,1,n)=1+e(n+1/(p−1)) and u(K,r,n)=1−p−n+e(n+r/(p−1)) for 1<r<p−1.     

Resolvable even cycle decompositions of the tensor product of complete graphs

In this paper, we consider resolvable k-cycle decompositions (for short, k-RCD) of K_m×K_n, where × denotes the tensor product of graphs. It has been proved that the standard necessary conditions for the existence of a k-RCD of K_m×K_n are sufficient when k is even.     

Equidimensionality of convolution morphisms and applications to saturation problems

Fix a split connected reductive group G over a field k, and a positive integer r. For any r-tuple of dominant coweights μi of G, we consider the restriction mμ_• of the r-fold convolution morphism of Mirkovic-Vilonen to the twisted product of affine Schubert varieties corresponding to μ_•. We show that if all the coweights μi are minuscule, then the fibers of mμ_• are equidimensional varieties, with dimension the largest allowed by the semi-smallness of mμ_•. We derive various consequences: the equivalence of the non-vanishing of Hecke and representation ring structure constants, and a saturation property for these structure constants, when the coweights μi are sums of minuscule coweights. This complements the saturation results of Knutson-Tao and Kapovich-Leeb-Millson. We give a new proof of the P-R-V conjecture in the “sums of minuscules” setting. Finally, we generalize and reprove a result of Spaltenstein pertaining to equidimensionality of certain partial Springer resolutions of the nilpotent cone for GLn.     

A problem ? multi-colorings of graphs

In this paper we consider colorings of the edges of the complete graph K_m with n colors such that the edges of any color form a non-trivial complete subgraph of K_m. We allow an edge of K_m to have more than one color. Such a coloring will be called r-admissible if no cycle of length r has a different color for each edge. Let E (m, n, r) be the maximum number of incidences of colors and edges, taken over all r-admissible colorings of K_m with n colors. Then for r = 3,4, and 5 we give an upper bound for E (m, n, r); as well as a lower bound for E (m, n, r) for all r. An analogue to a problem of Zarankiewicz concerning 0, 1-matrices is mentioned.