Colouring games based on autotopisms of Latin hyper-rectangles

Abstract

Every partial colouring of a Hamming graph is uniquely related to a partial Latin hyper-rectangle. In this paper we introduce the Θ-stabilized (a, b)-colouring game for Hamming graphs, a variant of the (a, b)-colouring game so that each move must respect a given autotopism Θ of the resulting partial Latin hyperrectangle. We examine the complexity of this variant by means of its chromatic number. We focus in particular on the bi-dimensional case, for which the game is played on the Cartesian product of two complete graphs, and also on the hypercube case.     

New proofs for Levine’s theorems

Recently, Levine [9] expressed the vertex weighted complexity on spanning trees (with a fixed root) of the directed line graph of a digraph D in terms of the edge weighted complexity on spanning trees (with a fixed root) of D. We present new proofs for two Levine’s Theorems. Furthermore, we express the number of unicycles of the directed line graph of a digraph D in terms of the number of unicycles of D.     

Colorful Isomorphic Spanning Trees in Complete Graphs

Can a complete graph on an even number n (> 4) of vertices be properly edge-colored with n − 1 colors in such a way that the edges can be partitioned into edge-disjoint colorful isomorphic spanning trees? A spanning treee is colorful if all n − 1 colors occur among its edges. It is proved that this is possible to accomplish whenever n is a power of two.Received July 24, 2001     

A p, q-Analogue of the Generalized Derangement Numbers

In this paper, we study the numbers D _n,k which are defined as the number of permutations σ of the symmetric group S _n such that σ has no cycles of length j for j ≤ k. In the case k = 1, D _n,1 is simply the number of derangements of an n-element set. As such, we shall call the numbers D _n,k generalized derangement numbers. Garsia and Remmel [4] defined some natural q-analogues of D _n,1, denoted by D _n,1(q), which give rise to natural q-analogues of the two classical recursions of the number of derangements. The method of Garsia and Remmel can be easily extended to give natural p, q-analogues D _n,1(p, q) which satisfy natural p, q-analogues of the two classical recursions for the number of derangements. In [4], Garsia and Remmel also suggested an approach to define q-analogues of the numbers D _n,k . In this paper, we show that their ideas can be extended to give a p, q-analogue of the generalized derangements numbers. Again there are two classical recursions for eneralized derangement numbers. However, the p, q-analogues of the two classical recursions are not as straightforward when k ≥ 2. Partially supported by NSF grant DMS 0400507.     

On the existence of two non-neighboring subgraphs in a graph

Does there exist a functionf(r, n) such that each graphG with _Z (G)≧f(r, n) contains either a complete subgraph of orderr or else two non-neighboringn-chromatic subgraphs? It is known thatf(r, 2) exists and we establish the existence off(r, 3). We also give some interesting results about graphs which do not contain two independent edges.     

A note on chain lengths and the Tutte polynomial

We show that the number of chains of given length in a graph G can be easily found from the Tutte polynomial of G. Hence two Tutte-equivalent graphs will have the same distribution of chain lengths. We give two applications of this latter statement.We also give the dual results for the numbers of multiple edges with given muliplicities.     

On a combinatorial problem related to permanents

Some numerical results will be presented concerning the largest and smallest values of square permanents containing the integers 1, 2, 3, ...,n ² n=1(1)8.Dedicated to Peter Naur on the occasion of his 60th birthday     

r-Strong edge colorings of graphs

Let G be a graph and for any natural number r, denotes the minimum number of colors required for a proper edge coloring of G in which no two vertices with distance at most r are incident to edges colored with the same set of colors. In [Z. Zhang, L. Liu, J. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett. 15 (2002) 623-626] it has been proved that for any tree T with at least three vertices, . Here we generalize this result and show that . Moreover, we show that if for any two vertices u and v with maximum degree d(u,v)?3, then . Also for any tree T with Δ(T)?3 we prove that . Finally, it is shown that for any graph G with no isolated edges, .     

Determinant identities for Laplace matrices

We show that every minor of an n×n Laplace matrix, i.e., a symmetric matrix whose row- and column sums are 0, can be written in terms of those minors that are obtained by deleting two rows and the corresponding columns. The proof is based on a classical determinant identity due to Sylvester. Furthermore, we show how our result can be applied in the context of electrical networks and spanning tree enumeration.     

The butterfly decomposition of plane trees

We introduce the notion of doubly rooted plane trees and give a decomposition of these trees, called the butterfly decomposition, which turns out to have many applications. From the butterfly decomposition we obtain a one-to-one correspondence between doubly rooted plane trees and free Dyck paths, which implies a simple derivation of a relation between the Catalan numbers and the central binomial coefficients. We also establish a one-to-one correspondence between leaf-colored doubly rooted plane trees and free Schröder paths. The classical Chung-Feller theorem as well as some generalizations and variations follow quickly from the butterfly decomposition. We next obtain two involutions on free Dyck paths and free Schröder paths, leading to parity results and combinatorial identities. We also use the butterfly decomposition to give a combinatorial treatment of Klazar's generating function for the number of chains in plane trees. Finally we study the total size of chains in plane trees with n edges and show that the average size of such chains tends asymptotically to (n+9)/6.     

Transitive Edge Coloring of Graphs and Dimension of Lattices

We explore properties of edge colorings of graphs dened by set intersections. An edge coloring of a graph G with vertex set V ={1,2, . . . , n} is called transitive if one can associate sets F ₁,F ₂, . . .,F _n to vertices of G so that for any two edges ij,kl E(G), the color of ij and kl is the same if and only if F _i F _j = F _k F _l . The term transitive refers to a natural partial order on the color set of these colorings.We prove a canonical Ramsey type result for transitive colorings of complete graphs which is equivalent to a stronger form of a conjecture of A. Sali on hypergraphs. This—through the reduction of Sali—shows that the dimension of n-element lattices is o(n) as conjectured by Füredi and Kahn.The proof relies on concepts and results which seem to have independent interest. One of them is a generalization of the induced matching lemma of Ruzsa and Szemerédi for transitive colorings. * Research supported in part by OTKA Grant T029074.     

A family of invariants of rooted forests

Let A be a commutative k-algebra over a field of k and Ξ a linear operator defined on A. We define a family of A-valued invariants Ψ for finite rooted forests by a recurrent algorithm using the operator Ξ and show that the invariant Ψ distinguishes rooted forests if (and only if) it distinguishes rooted trees T, and if (and only if) it is finer than the quantity α(T)=|Aut(T)| of rooted trees T. We also consider the generating function with , where is the set of rooted trees with n vertices. We show that the generating function U(q) satisfies the equation . Consequently, we get a recurrent formula for U_n (n?1), namely, U₁=Ξ(1) and U_n=ΞS_n−1(U₁,U₂,…,U_n−1) for any n?2, where are the elementary Schur polynomials. We also show that the (strict) order polynomials and two well-known quasi-symmetric function invariants of rooted forests are in the family of invariants Ψ and derive some consequences about these well-known invariants from our general results on Ψ. Finally, we generalize the invariant Ψ to labeled planar forests and discuss its certain relations with the Hopf algebra in Foissy (Bull. Sci. Math. 126 (2002) 193) spanned by labeled planar forests.     

Bartholdi zeta and L-functions of weighted digraphs, their coverings and products

Since a zeta function of a regular graph was introduced by Ihara [Y. Ihara, On discrete subgroups of the two by two projective linear group over p-adic fields, J. Math. Soc. Japan 19 (1966) 219-235], many kinds of zeta functions and L-functions of a graph or a digraph have been defined and investigated. Most of the works concerning zeta and L-functions of a graph contain the following: (1) defining a zeta function, (2) defining an L-function associated with a (regular) graph covering, (3) providing their determinant expressions, and (4) computing the zeta function of a graph covering and obtaining its decomposition formula as a product of L-functions. As a continuation of those works, we introduce a zeta function of a weighted digraph and an L-function associated with a weighted digraph bundle. A graph bundle is a notion containing a cartesian product of graphs and a (regular or irregular) graph covering. Also we provide determinant expressions of the zeta function and the L-function. Moreover, we compute the zeta function of a weighted digraph bundle and obtain its decomposition formula as a product of the L-functions.     

A Construction of Uniquely C4-free colourable Graphs

Abstract

An F-free colouring of a graph G is a partition {V₁,V₂,…,V_n} of the vertex set V(G) of G such that F is not an induced subgraph of G[V_i] for each i. A graph is uniquely F-free colourable if any two .F-free colourings induce the same partition of V(G). We give a constructive proof that uniquely C₄-free colourable graphs exist.     

On minors of the compound matrix of a Laplacian

Let L   be an n×n$n\times n$ matrix with zero row and column sums, n?3$n?3$. We obtain a formula for any minor of the (n−2)$(n-2)$-th compound of L. An application to counting spanning trees extending a given forest is given.     

On the Number of Latin Squares

We (1) determine the number of Latin rectangles with 11 columns and each possible number of rows, including the Latin squares of order 11, (2) answer some questions of Alter by showing that the number of reduced Latin squares of order n is divisible by f! where f is a particular integer close to (3) provide a formula for the number of Latin squares in terms of permanents of (+1, −1)-matrices, (4) find the extremal values for the number of 1-factorisations of k-regular bipartite graphs on 2n vertices whenever 1 ≤ k ≤ n ≤ 11, (5) show that the proportion of Latin squares with a non-trivial symmetry group tends quickly to zero as the order increases. Received September 3, 2004     

On the hole index of L(2,1)-labelings of r-regular graphs

An L(2,1)-labeling of a graph G is an assignment of nonnegative integers to the vertices of G so that adjacent vertices get labels at least distance two apart and vertices at distance two get distinct labels. A hole is an unused integer within the range of integers used by the labeling. The lambda number of a graph G, denoted λ(G), is the minimum span taken over all L(2,1)-labelings of G. The hole index of a graph G, denoted ρ(G), is the minimum number of holes taken over all L(2,1)-labelings with span exactly λ(G). Georges and Mauro [On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208-223] conjectured that if G is an r-regular graph and ρ(G)?1, then ρ(G) must divide r. We show that this conjecture does not hold by providing an infinite number of r-regular graphs G such that ρ(G) and r are relatively prime integers.     

Kernel method and linear recurrence system

Based on the kernel method, we present systematic methods to solve equation systems on generating functions of two variables. Using these methods, we get the generating functions for the number of permutations which avoid 1234 and 12k(k-1)…3$12k(k-1)\dots 3$ and permutations which avoid 1243 and 12…k$12\dots k$.     

Twisted derivations and distinct sets of lines that cover the same pairs of points

A partial projective plane of ordern consists of lines andn ² +n + 1 points such that every line hasn+1 points and distinct lines meet in a unique point. Suppose that two essentially different partial projective planes and of ordern, n a perfect square, that are defined on the same set of points cover the same pairs of points. For sufficiently largen we show that this implies that and have at leastn(n+1) lines. This bound is sharp and there exist essentially two different types of examples meeting the bound.As an application, we can show that derived planes provide an example for a pair of projective planes of square order with as much structure as possible in common, that is, as many lines as possible in common. Furthermore, we present a new method (twisted derivations) to obtain planes from one another by replacing the same number of lines as in a derivation.     

Simple proofs of open problems about the structure of involutions in the Riordan group

We prove that if D=(g(x),f(x)) is an element of order 2 in the Riordan group then g(x)=±exp[Φ(x,xf(x)] for some antisymmetric function Φ(x,z). Also we prove that every element of order 2 in the Riordan group can be written as BMB^-1 for some element B and M=(1,-1) in the Riordan group. These proofs provide solutions to two open problems presented by L. Shapiro [L.W. Shapiro, Some open questions about random walks, involutions, limiting distributions and generating functions, Adv. Appl. Math. 27 (2001) 585-596].