2-Binary trees: Bijections and related issues

A 2-binary tree is a binary rooted tree whose root is colored black and the other vertices are either black or white. We present several bijections concerning different types of 2-binary trees as well as other combinatorial structures such as ternary trees, non-crossing trees, Schröder paths, Motzkin paths and Dyck paths. We also obtain a number of enumeration results with respect to certain statistics.     

Star complements in regular graphs: Old and new results

We survey results concerning star complements in finite regular graphs, and note the connection with designs and strongly regular graphs in certain cases. We include improved proofs along with new results on stars and windmills as star complements.     

Crossing graphs of fiber-complemented graphs

Fiber-complemented graphs form a vast non-bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a fiber-complemented graph, we introduce the crossing graph of a fiber-complemented graph G as the graph whose vertices are colors, and two colors are adjacent if they cross on some induced 4-cycle in G. We show that a fiber-complemented graph is 2-connected if and only if its crossing graph is connected. We characterize those fiber-complemented graphs whose crossing graph is complete, and also those whose crossing graph is chordal.     

Additivity of the crossing number of graphs with connectivity 2

We prove that the crossing number of graphs with connectivity 2 has in certain cases an additive property analogous to that of crossing number of graphs with connectivity ≤1.     

Homomorphisms to oriented cycles

We discuss the existence of homomorphisms to oriented cycles and give, for a special class of cyclesC, a characterization of those digraphs that admit, a homomorphism toC. Our result can be used to prove the multiplicativity of a certain class of oriented cycles, (and thus complete the characterization of multiplicative oriented cycles), as well as to prove the membership of the corresponding decision problem in the classNPcoNP. We also mention a conjecture on the existence of homomorphisms to arbitrary oriented cycles.     

Extreme values of the stationary distribution of random walks on directed graphs

We examine the stationary distribution of random walks on directed graphs. In particular, we focus on the principal ratio, which is the ratio of maximum to minimum values of vertices in the stationary distribution. We give an upper bound for this ratio over all strongly connected graphs on n vertices. We characterize all graphs achieving the upper bound and we give explicit constructions for these extremal graphs. Additionally, we show that under certain conditions, the principal ratio is tightly bounded. We also provide counterexamples to show the principal ratio cannot be tightly bounded under weaker conditions.     

Geometric aspects of 2-walk-regular graphs

A t-walk-regular graph is a graph for which the number of walks of given length between two vertices depends only on the distance between these two vertices, as long as this distance is at most t. Such graphs generalize distance-regular graphs and t-arc-transitive graphs. In this paper, we will focus on 1- and in particular 2-walk-regular graphs, and study analogues of certain results that are important for distance-regular graphs. We will generalize Delsarte?s clique bound to 1-walk-regular graphs, Godsil?s multiplicity bound and Terwilliger?s analysis of the local structure to 2-walk-regular graphs. We will show that 2-walk-regular graphs have a much richer combinatorial structure than 1-walk-regular graphs, for example by proving that there are finitely many non-geometric 2-walk-regular graphs with given smallest eigenvalue and given diameter (a geometric graph is the point graph of a special partial linear space); a result that is analogous to a result on distance-regular graphs. Such a result does not hold for 1-walk-regular graphs, as our construction methods will show.     

Classification of quadratic systems admitting the existence of an algebraic limit cycle

In the paper we find a set of necessary conditions that must be satisfied by a quadratic system in order to have an algebraic limit cycle. We find a countable set of ?5 parameter families of quadratic systems such that every quadratic system with an algebraic limit cycle must, after a change of variables, belong to one of those families. We provide a classification of all the quadratic systems which can have an algebraic limit cycle based on geometrical properties of the embedding of the system in the Poincaré compactification of R². We propose names for all the classes we distinguish and we classify all known examples of quadratic systems with algebraic limit cycle. We also prove the integrability of certain classes of quadratic systems.     

Graceful labellings of paths

It is easily shown that every path has a graceful labelling, however, in this paper we show that given almost any path P with n vertices then for every vertex v∈V(P) and for every integer i∈{0,…,n-1} there is a graceful labelling of P such that v has label i. We show precisely when these labellings can also be α-labellings. We then extend this result to strong edge-magic labellings. In obtaining these results we make heavy use of π-representations of α-labellings and review some relevant results of Kotzig and Rosa.     

On multiplicative graphs and the product conjecture

We study the following problem: which graphsG have the property that the class of all graphs not admitting a homomorphism intoG is closed under taking the product (conjunction)? Whether all undirected complete graphs have the property is a longstanding open problem due to S. Hedetniemi. We prove that all odd undirected cycles and all prime-power directed cycles have the property. The former result provides the first non-trivial infinite family of undirected graphs known to have the property, and the latter result verifies a conjecture of Ne?et?il and Pultr These results allow us (in conjunction with earlier results of Ne?et?il and Pultr [17], cf also [7]) to completely characterize all (finite and infinite, directed and undirected) paths and cycles having the property. We also derive the property for a wide class of 3-chromatic graphs studied by Gerards, [5].     

The outer-distance of nodes in random trees

The outer-distance of a nodeu in a rooted treeT _n is the height of the subtree determined byu and all nodesv such thatu is on the path joiningv and the root ofT. We show that the expected outer-distance of nodes of treesT _n in certain families is asymptotic toB logn where the constantB depends on .     

A note on the girth of digraphs

Behzad, Chartrand and Wall conjectured that the girth of a diregular graph of ordern and outdegreer is not greater than [n /r]. This conjecture has been proved forr=2 by Behzad and forr=3 by Bermond. We prove that a digraph of ordern and halfdegree ≧4 has girth not exceeding [n / 4]. We also obtain short proofs of the above results. Our method is an application of the theory of connectivity of digraphs.     

On claws belonging to every tournament

A directed graph is said to ben-unavoidable if it is contained as a subgraph by every tournament onn vertices. A number of theorems have been proven showing that certain graphs aren-unavoidable, the first being Rédei's results that every tournament has a Hamiltonian path. M. Saks and V. Sós gave more examples in [6] and also a conjecture that states: Every directed claw onn vertices such that the outdegree of the root is at most [n/2] isn-unavoidable. Here a claw is a rooted tree obtained by identifying the roots of a set of directed paths. We give a counterexample to this conjecture and prove the following result:any claw of rootdegreen/4 is n-unavoidable.     

On point covers of multiple intervals and axis-parallel rectangles

In certain families of hypergraphs the transversal number is bounded by some function of the packing number. In this paper we study hypergraphs related to multiple intervals and axisparallel rectangles, respectively. Essential improvements of former established upper bounds are presented here. We explore the close connection between the two problems at issue.Supported by the Alexander von Humboldt Foundation and the NSF grant No. STC-91-19999Supported by the NSF grant No. CCR-92-00788, the (Hungarian) National Scientific Research Fund (OTKA) grant No. F014919. The author was visiting the Computation and Automation Institute, Budapest while part of this research was done.     

On unimodular graphs

We study graphs whose adjacency matrices have determinant equal to 1 or −1, and characterize certain subclasses of these graphs. Graphs whose adjacency matrices are totally unimodular are also characterized. For bipartite graphs having a unique perfect matching, we provide a formula for the inverse of the corresponding adjacency matrix, and address the problem of when that inverse is diagonally similar to a nonnegative matrix. Special attention is paid to the case that such a graph is unicyclic.     

On the energy of some circulant graphs

We give an explicit construction of circulant graphs of very high energy. This construction is based on Gauss sums. We also show the Littlewood conjecture can be used to establish new result for a certain class of circulant graphs.     

Rouquier blocks

This paper investigates the Rouquier blocks of the Hecke algebras of the symmetric groups and the Rouquier blocks of the q-Schur algebras. We first give an algorithm for computing the decomposition numbers of these blocks in the ``abelian defect group case' and then use this algorithm to explicitly compute the decomposition numbers in a Rouquier block. For fields of characteristic zero, or when q=1 these results are known; significantly, our results also hold for fields of positive characteristic with q≠1. We also discuss the Rouquier blocks in the ``non–abelian defect group' case. Finally, we apply these results to show that certain Specht modules are irreducible.     

A lower bound for the recognition of digraph properties

The complexity of a digraph property is the number of entries of the adjacency matrix which must be examined by a decision tree algorithm to recognize the property in the worst case, Aanderaa and Rosenberg conjectured that there is a constant such that every digraph property which is monotone (not destroyed by the deletion of edges) and nontrivial (holds for some but not all digraphs) has complexity at leastv ² wherev is the number of nodes in the digraph. This conjecture was proved by Rivest and Vuillemin and a lower bound ofv ²/4–o(v ²) was subsequently found by Kahn, Saks, and Sturtevant. Here we show a lower bound ofv ²/2–o(v ²). We also prove that a certain class of monotone, nontrivial bipartite digraph properties is evasive (requires that every entry in the adjacency matrix be examined in the worst case).     

Minimal Bar Tableaux

Motivated by recent results of Stanley, we generalize the rank of a partition λ to the rank of a shifted partition S(λ). We show that the number of bars required in a minimal bar tableau of S(λ) is max(o, e + (ℓ(λ) mod 2)), where o and e are the number of odd and even rows of λ. As a consequence we show that the irreducible projective characters of S_n vanish on certain conjugacy classes. Another corollary is a lower bound on the degree of the terms in the expansion of Schur’s Q_λ symmetric functions in terms of the power sum symmetric functions. Received November 20, 2003     

Coloring planar perfect graphs by decomposition

This paper describes a decomposition scheme for coloring perfect graphs. Based on this scheme, one need only concentrate on coloring highly connected (at least 3-connected) perfect graphs. This idea is illustrated on planar perfect graphs, which yields a straightforward coloring algorithm. We suspect that, under appropriate definition, highly connected perfect graphs might possess certain regular properties that are amenable to coloring algorithms. This research has been supported in part by National Science Foundation under grant ECS—8105989 to Northwestern University.