Examples from trees, related to discrete subsets, pseudo-radiality and ω-boundedness

We construct some examples using trees. Some of them are consistent counterexamples for the discrete reflection of certain topological properties. All the properties dealt with here were already known to be non-discretely reflexive if we assume CH and we show that the same is true assuming the existence of a Suslin tree. In some cases we actually get some ZFC results. We construct also, using a Suslin tree, a compact space that is pseudo-radial but it is not discretely generated. With a similar construction, but using an Aronszajn tree, we present a ZFC space that is first countable, ω-bounded but is not strongly ω-bounded, answering a question of Peter Nyikos.     

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.     

Recursive automorphisms of recursive linear orderings

We characterize by classical order type those recursive linear orderings L such that every classically isomorphic recursive copy R of L has a non-identity recursive automorphism.     

The Laplacian spectral radii of trees with degree sequences

In this paper, we characterize all extremal trees with the largest Laplacian spectral radius in the set of all trees with a given degree sequence. Consequently, we also obtain all extremal trees with the largest Laplacian spectral radius in the sets of all trees of order n with the largest degree, the leaves number and the matching number, respectively.     

Eliminating graphs by means of parallel knock-out schemes

In 1997 Lampert and Slater introduced parallel knock-out schemes, an iterative process on graphs that goes through several rounds. In each round of this process, every vertex eliminates exactly one of its neighbors. The parallel knock-out number of a graph is the minimum number of rounds after which all vertices have been eliminated (if possible). The parallel knock-out number is related to well-known concepts like perfect matchings, hamiltonian cycles, and 2-factors.We derive a number of combinatorial and algorithmic results on parallel knock-out numbers: for families of sparse graphs (like planar graphs or graphs of bounded tree-width), the parallel knock-out number grows at most logarithmically with the number n of vertices; this bound is basically tight for trees. Furthermore, there is a family of bipartite graphs for which the parallel knock-out number grows proportionally to the square root of n. We characterize trees with parallel knock-out number at most 2, and we show that the parallel knock-out number for trees can be computed in polynomial time via a dynamic programming approach (whereas in general graphs this problem is known to be NP-hard). Finally, we prove that the parallel knock-out number of a claw-free graph is either infinite or less than or equal to 2.     

The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample

Let G be an undirected graph on n vertices and let S(G) be the set of all real symmetric n×n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. The inverse inertia problem for G asks which inertias can be attained by a matrix in S(G). We give a complete answer to this question for trees in terms of a new family of graph parameters, the maximal disconnection numbers of a graph. We also give a formula for the inertia set of a graph with a cut vertex in terms of inertia sets of proper subgraphs. Finally, we give an example of a graph that is not inertia-balanced, which settles an open problem from the October 2006 AIM Workshop on Spectra of Families of Matrices described by Graphs, Digraphs and Sign Patterns. We also determine some restrictions on the inertia set of any graph.     

The Number of Subtrees of Trees with Given Degree Sequence

This article investigates some properties of the number of subtrees of a tree with given degree sequence. These results are used to characterize trees with the given degree sequence that have the largest number of subtrees, which generalize the recent results of Kirk and Wang (SIAM J Discrete Math 22 (2008), 985–995). These trees coincide with those which were proven by Wang and independently Zhang et al. (2008) to minimize the Wiener index. We also provide a partial ordering of the extremal trees with different degree sequences, some extremal results follow as corollaries.     

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.     

The cover pebbling number of graphs

A pebbling move on a graph consists of taking two pebbles off of one vertex and placing one pebble on an adjacent vertex. In the traditional pebbling problem we try to reach a specified vertex of the graph by a sequence of pebbling moves. In this paper we investigate the case when every vertex of the graph must end up with at least one pebble after a series of pebbling moves. The cover pebbling number of a graph is the minimum number of pebbles such that however the pebbles are initially placed on the vertices of the graph we can eventually put a pebble on every vertex simultaneously. We find the cover pebbling numbers of trees and some other graphs. We also consider the more general problem where (possibly different) given numbers of pebbles are required for the vertices.     

Edge partitions of the Rado graph

We will prove that for every colouring of the edges of the Rado graph, (that is the countable homogeneous graph), with finitely many coulours, it contains an isomorphic copy whose edges are coloured with at most two of the colours. It was known [4] that there need not be a copy whose edges are coloured with only one of the colours. For the proof we use the lexicographical order on the vertices of the Rado graph, defined by Erdös, Hajnal and Pósa.Using the result we are able to describe a Ramsey basis for the class of Rado graphs whose edges are coloured with at most a finite number,r, of colours. This answers an old question of M. Pouzet.Supported by the French PRC Math-Info.Supported by NSERC of Canada Grant # 691325.     

Ladder systems on trees

We formulate the notion of uniformization of colorings of ladder systems on subsets of trees. We prove that Suslin trees have this property and also Aronszajn trees in the presence of Martin's Axiom. As an application we show that if a tree has this property, then every countable discrete family of subsets of the tree can be separated by a family of pairwise disjoint open sets. Such trees are then normal and hence countably paracompact. As a dual result for special Aronszajn trees we prove that the weak diamond, , implies that no special Aronszajn tree can be countably paracompact.

     

Ordering trees by the Laplacian coefficients

Motivated by a Mohar’s paper proposing “how to order trees by the Laplacian coefficients”, we investigate a partial ordering of trees with diameters 3 and 4 by the Laplacian coefficients. These results are used to determine several orderings of trees by the Laplacian coefficients.     

Gap structure after forcing with a coherent Souslin tree

We investigate the effect after forcing with a coherent Souslin tree on the gap structure of the class of coherent Aronszajn trees ordered by embeddability. We shall show, assuming the relativized version PFA(S) of the proper forcing axiom, that the Souslin tree S forces that the class of Aronszajn trees ordered by the embeddability relation is universal for linear orders of cardinality at most ${\aleph_1}$ .     

The least eigenvalue of the complements of trees

Let be the set of the complements of trees of order n. In this paper, we characterize the unique graph whose least eigenvalue attains the minimum among all graphs in .     

Characterizations of trees with equal paired and double domination numbers

A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, and a double dominating set is a dominating set that dominates every vertex of G at least twice. We show that for trees, the paired-domination number is less than or equal to the double domination number, solving a conjecture of Chellali and Haynes. Then we characterize the trees having equal paired and double domination numbers.     

Lexicographic product decompositions of half linearly ordered loops

In this paper we prove for an hl-loop Q an assertion analogous to the result of Jakubík concerning lexicographic products of half linearly ordered groups. We found conditions under which any two lexicographic product decompositions of an hl-loop Q with a finite number of lexicographic factors have isomorphic refinements.     

Sandpile groups and spanning trees of directed line graphs

We generalize a theorem of Knuth relating the oriented spanning trees of a directed graph G and its directed line graph LG. The sandpile group is an abelian group associated to a directed graph, whose order is the number of oriented spanning trees rooted at a fixed vertex. In the case when G is regular of degree k, we show that the sandpile group of G is isomorphic to the quotient of the sandpile group of LG by its k-torsion subgroup. As a corollary we compute the sandpile groups of two families of graphs widely studied in computer science, the de Bruijn graphs and Kautz graphs.     

On edge-weighted recursive trees and inversions in random permutations

We introduce random recursive trees, where deterministically weights are attached to the edges according to the labeling of the trees. We will give a bijection between recursive trees and permutations, which relates the arising edge-weights in recursive trees with inversions of the corresponding permutations. Using this bijection we obtain exact and limiting distribution results for the number of permutations of size n, where exactly m elements have j inversions. Furthermore we analyze the distribution of the sum of labels of the elements, which have exactly j inversions, where we can identify Dickman's infinitely divisible distribution as the limit law. Moreover we give a distributional analysis of weighted depths and weighted distances in edge-weighted recursive trees.