On conjugate adjacency matrices of a graph

Let G be a simple graph of order n. Let and , where a and b are two nonzero integers and m is a positive integer such that m is not a perfect square. We say that A^c=[c_ij] is the conjugate adjacency matrix of the graph G if c_ij=c for any two adjacent vertices i and j, for any two nonadjacent vertices i and j, and c_ij=0 if i=j. Let P_G(λ)=|λI-A| and denote the characteristic polynomial and the conjugate characteristic polynomial of G, respectively. In this work we show that if then , where denotes the complement of G. In particular, we prove that if and only if P_G(λ)=P_H(λ) and . Further, let P^c(G) be the collection of conjugate characteristic polynomials of vertex-deleted subgraphs G_i=G?i(i=1,2,…,n). If P^c(G)=P^c(H) we prove that , provided that the order of G is greater than 2.     

Extended directed triple systems

Let {n;b₂,b₁} denote the class of extended directed triple systems of the order n in which the number of blocks of the form [a,b,a] is b₂ and the number of blocks of the form [b,a,a] or [a,a,b] is b₁. In this paper, we have shown that the necessary and sufficient condition for the existence of the class {n;b₂,b₁} is b₁≠1, 0?b₂+b₁?n and

(1)

for ;

(2)

for .

     

Families of low dimensional determinantal schemes

A scheme X⊂Pⁿ of codimension c is called standard determinantal if its homogeneous saturated ideal can be generated by the t×t minors of a homogeneous t×(t+c−1) matrix (f_ij). Given integers a₀≤a₁≤?≤a_t+c−2 and b₁≤?≤b_t, we denote by the stratum of standard determinantal schemes where f_ij are homogeneous polynomials of degrees a_j−b_i and is the Hilbert scheme (if n−c>0, resp. the postulation Hilbert scheme if n−c=0).Focusing mainly on zero and one dimensional determinantal schemes we determine the codimension of in and we show that is generically smooth along under certain conditions. For zero dimensional schemes (only) we find a counterexample to the conjectured value of appearing in Kleppe and Miró-Roig (2005) [25].     

Cubicity, boxicity, and vertex cover

A k-dimensional box is the cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line of the form [a_i,a_i+1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. In this paper we show that cub(G)≤t+⌈log(n−t)⌉−1 and , where t is the cardinality of a minimum vertex cover of G and n is the number of vertices of G. We also show the tightness of these upper bounds.F.S. Roberts in his pioneering paper on boxicity and cubicity had shown that for a graph G, and , where n is the number of vertices of G, and these bounds are tight. We show that if G is a bipartite graph then and this bound is tight. We also show that if G is a bipartite graph then . We point out that there exist graphs of very high boxicity but with very low chromatic number. For example there exist bipartite (i.e., 2 colorable) graphs with boxicity equal to . Interestingly, if boxicity is very close to , then chromatic number also has to be very high. In particular, we show that if , s≥0, then , where χ(G) is the chromatic number of G.     

Density of constant radius normal binary covering codes

A binary code with covering radius R is a subset C of the hypercube Q_n={0,1}ⁿ such that every x∈Q_n is within Hamming distance R of some codeword c∈C, where R is as small as possible. For a fixed coordinate i∈[n], define to be the set of codewords with a b in the ith position. Then C is normal if there exists an i∈[n] such that for any v∈Q_n, the sum of the Hamming distances from v to and is at most 2R+1. We newly define what it means for an asymmetric covering code to be normal, and consider the worst-case asymptotic densities ν^*(R) and of constant radius R symmetric and asymmetric normal covering codes, respectively. Using a probabilistic deletion method, and analysis adapted from previous work by Krivelevich, Sudakov, and Vu, we show that and , giving evidence that minimum size constant radius covering codes could still be normal.     

Any Diophantine quintuple contains a regular Diophantine quadruple

A set {a₁,…,am} of m distinct positive integers is called a Diophantine m-tuple if aiaj+1 is a perfect square for all i, j with 1?i<j?m. It is conjectured that if {a,b,c,d} is a Diophantine quadruple with a<b<c<d, then d=d₊, where d₊=a+b+c+2abc+2rst and , , . In this paper, we show that if {a,b,c,d,e} is a Diophantine quintuple with a<b<c<d<e, then d=d₊.     

Bounds on isoperimetric values of trees

Let G=(V,E) be a finite, simple and undirected graph. For S⊆V, let δ(S,G)={(u,v)∈E:u∈S and v∈V−S} be the edge boundary of S. Given an integer i, 1≤i≤|V|, let the edge isoperimetric value of G at i be defined as b_e(i,G)=min_S⊆V;|S|=i|δ(S,G)|. The edge isoperimetric peak of G is defined as b_e(G)=max_1≤j≤|V|b_e(j,G). Let b_v(G) denote the vertex isoperimetric peak defined in a corresponding way. The problem of determining a lower bound for the vertex isoperimetric peak in complete t-ary trees was recently considered in [Y. Otachi, K. Yamazaki, A lower bound for the vertex boundary-width of complete k-ary trees, Discrete Mathematics, in press (doi:10.1016/j.disc.2007.05.014)]. In this paper we provide bounds which improve those in the above cited paper. Our results can be generalized to arbitrary (rooted) trees.The depth d of a tree is the number of nodes on the longest path starting from the root and ending at a leaf. In this paper we show that for a complete binary tree of depth d (denoted as ), and where c₁, c₂ are constants. For a complete t-ary tree of depth d (denoted as ) and d≥clogt where c is a constant, we show that and where c₁, c₂ are constants. At the heart of our proof we have the following theorem which works for an arbitrary rooted tree and not just for a complete t-ary tree. Let T=(V,E,r) be a finite, connected and rooted tree — the root being the vertex r. Define a weight function w:V→N where the weight w(u) of a vertex u is the number of its successors (including itself) and let the weight index η(T) be defined as the number of distinct weights in the tree, i.e η(T)=|{w(u):u∈V}|. For a positive integer k, let ?(k)=|{i∈N:1≤i≤|V|,b_e(i,G)≤k}|. We show that .     

Further analysis of the number of spanning trees in circulant graphs

Let 1?s₁<s₂<?<s_k?⌊n/2⌋ be given integers. An undirected even-valent circulant graph, has n vertices 0,1,2,…, n-1, and for each and j(0?j?n-1) there is an edge between j and . Let stand for the number of spanning trees of . For this special class of graphs, a general and most recent result, which is obtained in [Y.P. Zhang, X. Yong, M. Golin, [The number of spanning trees in circulant graphs, Discrete Math. 223 (2000) 337-350]], is that where a_n satisfies a linear recurrence relation of order 2^s_k-1. And, most recently, for odd-valent circulant graphs, a nice investigation on the number a_n is [X. Chen, Q. Lin, F. Zhang, The number of spanning trees in odd-valent circulant graphs, Discrete Math. 282 (2004) 69-79].In this paper, we explore further properties of the numbers a_n from their combinatorial structures. Comparing with the previous work, the differences are that (1) in finding the coefficients of recurrence formulas for a_n, we avoid solving a system of linear equations with exponential size, but instead, we give explicit formulas; (2) we find the asymptotic functions and therefore we ‘answer’ the open problem posed in the conclusion of [Y.P. Zhang, X. Yong, M. Golin, The number of spanning trees in circulant graphs, Discrete Math. 223 (2000) 337-350]. As examples, we describe our technique and the asymptotics of the numbers.     

Long cycles and paths in distance graphs

For n∈N and D⊆N, the distance graph has vertex set {0,1,…,n−1} and edge set {ij∣0≤i,j≤n−1,|j−i|∈D}. Note that the important and very well-studied circulant graphs coincide with the regular distance graphs.A fundamental result concerning circulant graphs is that for these graphs, a simple greatest common divisor condition, their connectivity, and the existence of a Hamiltonian cycle are all equivalent. Our main result suitably extends this equivalence to distance graphs. We prove that for a finite set D of order at least 2, there is a constant c_D such that the greatest common divisor of the integers in D is 1 if and only if for every n, has a component of order at least n−c_D if and only if for every n≥c_D+3, has a cycle of order at least n−c_D. Furthermore, we discuss some consequences and variants of this result.     

An upper bound for Cubicity in terms of Boxicity

An axis-parallel b-dimensional box is a Cartesian product R₁×R₂×?×R_b where each R_i (for 1≤i≤b) is a closed interval of the form [a_i,b_i] on the real line. The boxicity of any graph G, is the minimum positive integer b such that G can be represented as the intersection graph of axis-parallel b-dimensional boxes. A b-dimensional cube is a Cartesian product R₁×R₂×?×R_b, where each R_i (for 1≤i≤b) is a closed interval of the form [a_i,a_i+1] on the real line. When the boxes are restricted to be axis-parallel cubes in b-dimension, the minimum dimension b required to represent the graph is called the cubicity of the graph (denoted by ). In this paper we prove that , where n is the number of vertices in the graph. We also show that this upper bound is tight.Some immediate consequences of the above result are listed below:

1.

Planar graphs have cubicity at most 3⌈log₂n⌉.

2.

Outer planar graphs have cubicity at most 2⌈log₂n⌉.

3.

Any graph of treewidth tw has cubicity at most (tw+2)⌈log₂n⌉. Thus, chordal graphs have cubicity at most (ω+1)⌈log₂n⌉ and circular arc graphs have cubicity at most (2ω+1)⌈log₂n⌉, where ω is the clique number.

The above upper bounds are tight, but for small constant factors.     

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 .     

Regular Steinhaus graphs of odd degree

A Steinhaus matrix is a binary square matrix of size n which is symmetric, with a diagonal of zeros, and whose upper-triangular coefficients satisfy a_i,j=a_i−1,j−1+a_i−1,j for all 2?i<j?n. Steinhaus matrices are determined by their first row. A Steinhaus graph is a simple graph whose adjacency matrix is a Steinhaus matrix. We give a short new proof of a theorem, due to Dymacek, which states that even Steinhaus graphs, i.e. those with all vertex degrees even, have doubly-symmetric Steinhaus matrices. In 1979 Dymacek conjectured that the complete graph on two vertices K₂ is the only regular Steinhaus graph of odd degree. Using Dymacek’s theorem, we prove that if (a_i,j)_1?i,j?n is a Steinhaus matrix associated with a regular Steinhaus graph of odd degree then its sub-matrix (a_i,j)_2?i,j?n−1 is a multi-symmetric matrix, that is a doubly-symmetric matrix where each row of its upper-triangular part is a symmetric sequence. We prove that the multi-symmetric Steinhaus matrices of size n whose Steinhaus graphs are regular modulo 4, i.e. where all vertex degrees are equal modulo 4, only depend on parameters for all even numbers n, and on parameters in the odd case. This result permits us to verify Dymacek’s conjecture up to 1500 vertices in the odd case.     

Mutually orthogonal equitable Latin rectangles

Let ab=n². We define an equitable Latin rectangle as an a×b matrix on a set of n symbols where each symbol appears either or times in each row of the matrix and either or times in each column of the matrix. Two equitable Latin rectangles are orthogonal in the usual way. Denote a set of ka×b mutually orthogonal equitable Latin rectangles as a k– MOELR (a,b;n). When a≠9,18,36, or 100, then we show that the maximum number of k– MOELR (a,b;n)≥3 for all possible values of (a,b).     

Spanning multi-paths in hypercubes

A set A of vertices of a hypercube is called balanced if . We prove that for every natural number n there exists a natural number π₁(n) such that for every hypercube Q with dim(Q)?π₁(n) there exists a family of pairwise vertex-disjoint paths P_i between A_i and B_i for i=1,2,…,n with if and only if {A_i,B_i∣i=1,2,…,n} is a balanced set.     

The Cameron-Erd?s conjecture

A subset A of integers is said to be sum-free if a+b∉A for any a,b∈A. Let s(n) be the number of sum-free sets in interval [1,n] of integers. P. Cameron and P. Erd?s conjectured that s(n)=O(2^n/2). We show that for even n and for odd n, where are absolute constants, thereby proving the conjecture.     

Analysis of sharp polynomial upper estimate of number of positive integral points in a five-dimensional tetrahedra

Let a?b?c?d?e?1 be real numbers and P₅ be the number of positive integral solutions of . In this paper we show that 120P₅?(a-1)(b-1)(c-1)(d-1)(e-1). This confirms a conjecture of Durfee for the dimension 5 case. We show also that the upper estimate of P₅ given by Lin and Yau is strictly sharper than that suggested by Durfee conjecture if , but is not sharper than that suggested by Durfee conjecture if .     

Solution to a conjecture on the maximal energy of bipartite bicyclic graphs

The energy of a simple graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let C_n denote the cycle of order n and the graph obtained from joining two cycles C₆ by a path P_n-12 with its two leaves. Let B_n denote the class of all bipartite bicyclic graphs but not the graph R_a,b, which is obtained from joining two cycles C_a and C_b (a,b≥10 and ) by an edge. In [I. Gutman, D. Vidovi?, Quest for molecular graphs with maximal energy: a computer experiment, J. Chem. Inf. Sci. 41(2001) 1002-1005], Gutman and Vidovi? conjectured that the bicyclic graph with maximal energy is , for n=14 and n≥16. In [X. Li, J. Zhang, On bicyclic graphs with maximal energy, Linear Algebra Appl. 427(2007) 87-98], Li and Zhang showed that the conjecture is true for graphs in the class B_n. However, they could not determine which of the two graphs R_a,b and has the maximal value of energy. In [B. Furtula, S. Radenkovi?, I. Gutman, Bicyclic molecular graphs with the greatest energy, J. Serb. Chem. Soc. 73(4)(2008) 431-433], numerical computations up to a+b=50 were reported, supporting the conjecture. So, it is still necessary to have a mathematical proof to this conjecture. This paper is to show that the energy of is larger than that of R_a,b, which proves the conjecture for bipartite bicyclic graphs. For non-bipartite bicyclic graphs, the conjecture is still open.     

Quantifications des algèbres de Hopf d'arbres plans décorés et lien avec les groupes quantiques

We introduce a functor from the category of braided spaces into the category of braided Hopf algebras which associates to a braided space V a braided Hopf algebra of planar rooted trees . We show that the Nichols algebra of V is a subquotient of . We construct a Hopf pairing between and , generalising one of the results of [Bull. Sci. Math. 126 (2002) 193-239]. When the braiding of c is given by c(v_i⊗v_j)=q_i,jv_j⊗v_i, we obtain a quantification of the Hopf algebras introduced in [Bull. Sci. Math. 126 (2002) 193-239; 126 (2002) 249-288]. When q_i,j=q^a_i,j, with q an indeterminate and (a_i,j)_i,j the Cartan matrix of a semi-simple Lie algebra , then is a subquotient of . In this case, we construct the crossed product of with a torus and then the Drinfel'd quantum double of this Hopf algebra. We show that is a subquotient of .     

A short proof of a cross-intersection theorem of Hilton

Families A₁,…,A_k of sets are said to be cross-intersecting if for any A_i∈A_i and A_j∈A_j, i≠j. A nice result of Hilton that generalises the Erd?s-Ko-Rado (EKR) Theorem says that if r≤n/2 and A₁,…,A_k are cross-intersecting sub-families of , then