On the number of complementary trees in a graph

Consider a graph with no loops or multiple arcs with n+1 nodes and 2n arcs labeled a_l,…,a_n,a′_l,…,a′_n, where n ≥ 5. A spanning tree of such a graph is called complementary if it contains exactly one arc of each pair {a_i,a′_i}. The purpose of this paper is to develop a procedure for finding complementary trees in a graph, given one such tree. Using the procedure repeatedly we give a constructive proof that every graph of the above form which has one complementary tree has at least six such trees.     

Reciprocal complementary Wiener numbers of trees, unicyclic graphs and bicyclic graphs

The reciprocal complementary Wiener number of a connected graph G is defined as

where V(G) is the vertex set, d(u,v|G) is the distance between vertices u and v, d is the diameter of G. We determine the trees with the smallest, the second smallest and the third smallest reciprocal complementary Wiener numbers, and the unicyclic and bicyclic graphs with the smallest and the second smallest reciprocal complementary Wiener numbers.     

Bounds on trees

We prove a finitary version of the Halpern–Läuchli Theorem. We also prove partition results about strong subtrees. Both results give estimates on the height of trees.     

Nilsemigroups on trees

We show how to reconstruct finite commutative nilsemigroups from their underlying partially ordered sets, and characterize which finite trees underlie finite commutative nilsemigroups.     

Bands on trees

Communicated by D. R. Brown     

Semi-preemptive routing on trees

We study a variant of the pickup-and-delivery problem (PDP) in which the objects that have to be transported can be reloaded at most d times, for a given d∈N. This problem is known to be polynomially solvable on paths or cycles and NP-complete on trees. We present a (4/3+ε)-approximation algorithm if the underlying graph is a tree. By using a result of Charikar et al. [M. Charikar, C. Chekuri, A. Goel, S. Guha, S. Plotkin, Approximating a finite metric by a small number of tree metrics, in: FOCS ’98: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, USA, 1998, pp. 379-388], this can be extended to a O(lognloglogn)-approximation for general graphs.     

Random walks on trees

The classical gambler's ruin problem, i.e., a random walk along a line may be viewed graph theoretically as a random walk along a path with the endpoints as absorbing states. This paper is an investigation of the natural generalization of this problem to that of a particle walking randomly on a tree with the endpoints as absorbing barriers. Expressions in terms of the graph structure are obtained from the probability of absorption at an endpoint e in a walk originating from a vertex v, as well as for the expected length of the walk.     

Birth-death processes on trees

In this paper, we consider birth-death processes on a tree T and we are interested when it is regular, recurrent and ergodic (strongly, exponentially). By constructing two corresponding birth death processes on Z+, we obtain computable conditions sufficient or necessary for that (in many cases, these two conditions coincide). With the help of these constructions, we give explicit upper and lower bounds for the Dirichlet eigenvalue λ0. At last, some examples are investigated to justify our results.     

Rainbow domination on trees

This paper studies a variation of domination in graphs called rainbow domination. For a positive integer k, a k-rainbow dominating function of a graph G is a function f from V(G) to the set of all subsets of {1,2,…,k} such that for any vertex v with f(v)=0? we have ∪_u∈NG(v)f(u)={1,2,…,k}. The 1-rainbow domination is the same as the ordinary domination. The k-rainbow domination problem is to determine the k-rainbow domination number of a graph G, that is the minimum value of ∑_v∈V(G)|f(v)| where f runs over all k-rainbow dominating functions of G. In this paper, we prove that the k-rainbow domination problem is NP-complete even when restricted to chordal graphs or bipartite graphs. We then give a linear-time algorithm for the k-rainbow domination problem on trees. For a given tree T, we also determine the smallest k such that .     

Limsup deviations on trees

The vertices of an infinite locally finite tree T are labelled by a collection of i.i.d. real random variables {Xσ}σ∈T which defines a tree indexed walk Sσ = ∑θ＜r≤σXr. We introduce and study the oscillations of the walk:Exact Hausdorff dimension of the set of such ξ 's is calculated. An application is given to study the local variation of Brownian motion. A general limsup deviation problem on trees is also studied.     

More on betweenness-uniform graphs

We study graphs whose vertices possess the same value of betweenness centrality (which is defined as the sum of relative numbers of shortest paths passing through a given vertex). Extending previously known results of S. Gago, J. Hurajová, T. Madaras (2013), we show that, apart of cycles, such graphs cannot contain 2-valent vertices and, moreover, are 3-connected if their diameter is 2. In addition, we prove that the betweenness uniformity is satisfied in a wide graph family of semi-symmetric graphs, which enables us to construct a variety of nontrivial cubic betweenness-uniform graphs.     

More on Graph Perturbations

Various modifications of a connected graph G are regarded asperturbations of an adjacency matrix A of G. Several resultsconcerning the resulting changes to the largest eigenvalue ofA are obtained by solving intermediate eigenvalue problems ofthe second type.     

Supplemental examples on complementary matrix algebras

In [1], M.-D. Choi, H. Radjavi and P. Rosenthal proved that, for each integer n4 (except 7 and 11), complementary algebras of linear operators on ⁿ do not necessarily have nontrivial complementary invariant subspaces. In this note we give counter-examples for the remaining two cases.     

More on subgradient duality

A duality theorem of P. Wolfe for nonlinear differential programming has been extended by the author to the non-differentiable case by replacing gradients by subgradients. In this paper this extended result is improved by allowing additional types of constraints. Also a converse duality theorem is proved.