Signed 2-independence in graphs

A function f : V→{−1,1} defined on the vertices of a graph G=(V,E) is a signed 2-independence function if the sum of its function values over any closed neighbourhood is at most one. That is, for every vV, f(N[v])1, where N[v] consists of v and every vertex adjacent to v. The weight of a signed 2-independence function is f(V)=∑f(v), over all vertices vV. The signed 2-independence number of a graph G, denoted α_s²(G), equals the maximum weight of a signed 2-independence function of G. In this paper, we establish upper bounds for α_s²(G) in terms of the order and size of the graph, and we characterize the graphs attaining these bounds. For a tree T, upper and lower bounds for α_s²(T) are established and the extremal graphs characterized. It is shown that α_s²(G) can be arbitrarily large negative even for a cubic graph G.     

On the eccentric distance sum of graphs

The eccentric distance sum is a novel topological index that offers a vast potential for structure activity/property relationships. For a graph G, it is defined as ξd(G)=_∑v∈Vε(v)D(v), where ε(v) is the eccentricity of the vertex v and D(v)=_∑u∈V(G)d(u,v) is the sum of all distances from the vertex v. Motivated by [G. Yu, L. Feng, A. Ili?, On the eccentric distance sum of trees and unicyclic graphs, J. Math. Anal. Appl. 375 (2011) 934-944], in this paper we characterize the extremal trees and graphs with maximal eccentric distance sum. Various lower and upper bounds for the eccentric distance sum in terms of other graph invariants including the Wiener index, the degree distance, eccentric connectivity index, independence number, connectivity, matching number, chromatic number and clique number are established. In addition, we present explicit formulae for the values of eccentric distance sum for the Cartesian product, applied to some graphs of chemical interest (like nanotubes and nanotori).     

Messy broadcasting — Decentralized broadcast schemes with limited knowledge

We consider versions of broadcasting that proceed in the absence of information about the network. In particular, the vertices of the network do not know the structure of the network or the starting time, originator, or state of the broadcast. Furthermore, the protocols are not coordinated. This synchronous anonymous communication model has been called messy broadcasting. We perform a worst case analysis of three variants of messy broadcasting. These results also provide upper bounds on broadcasting where every vertex simply calls each of its neighbors once in random order. We prove exact bounds on the time required for broadcasting under two variants and give a conjectured value for the third.     

Characterization and representation problems for intersection betweennesses

For a set system M=(M_v)_v∈V indexed by the elements of a finite set V, the intersection betweenness B(M) induced by M consists of all triples (u,v,w)∈V³ with M_u∩M_w⊆M_v. Similarly, the strict intersection betweenness B_s(M) induced by M consists of all triples (u,v,w)∈B(M) such that u, v, and w are pairwise distinct. The notion of a strict intersection betweenness was introduced by Burigana [L. Burigana, Tree representations of betweenness relations defined by intersection and inclusion, Math. Soc. Sci. 185 (2009) 5-36]. We provide axiomatic characterizations of intersection betweennesses and strict intersection betweennesses. Our results yield a simple and efficient algorithm that constructs a representing set system for a given (strict) intersection betweenness. We study graphs whose strict shortest path betweenness is a strict intersection betweenness. Finally, we explain how the algorithmic problem related to Burigana’s notion of a partial tree representation can be solved efficiently using well-known algorithms.     

Mixed graph edge coloring

We are interested in coloring the edges of a mixed graph, i.e., a graph containing unoriented and oriented edges. This problem is related to a communication problem in job-shop scheduling systems. In this paper we give general bounds on the number of required colors and analyze the complexity status of this problem. In particular, we provide NP-completeness results for the case of outerplanar graphs, as well as for 3-regular bipartite graphs (even when only 3 colors are allowed, or when 5 colors are allowed and the graph is fully oriented). Special cases admitting polynomial-time solutions are also discussed.     

Second-generation de novo design: a view from a medicinal chemist perspective

For computational de novo design, a general retrospective validation work is a very challenging task. Here we propose a comprehensive workflow to de novo design driven by the needs of computational and medicinal chemists and, at the same time, we propose a general validation scheme for this technique. The study was conducted combining a suite of already published programs developed within the framework of the NovoBench project, which involved three different pharmaceutical companies and four groups of developers. Based on 188 PDB protein–ligand complexes with diverse functions, the study involved the ligand reconstruction by means of a fragment-based de-novo design approach. The structure-based de novo search engine FlexNovo showed in five out of eight total cases the ability to reconstruct native ligands and to rank them in four cases out of five within the first five candidates. The generated structures were ranked according to their synthetic accessibilities evaluated by the program SYLVIA. This investigation showed that the final candidate molecules have about the same synthetic complexity as the respective reference ligands. Furthermore, the plausibility of being true actives was assessed through literature searches. Electronic supplementary material  The online version of this article (doi:) contains supplementary material, which is available to authorized users.

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.     

On the complexity of convex hull algorithms if rotational minima can be found very fast

For a large class of time functionsT, we show the following: Assuming that there is some parallel processor which requiresθ(T(j)) time units when searching the minimum amongj arbitrary points with respect to an arbitrary rotational ordering. Then the planar Convex Hull Problem forn points is of the complexityθ(nT(n)). Also our auxiliar results are significant: We shall deal with a graph theoretical lemma, and we shall prove a result which is similar to those of [Frie 72] and [Schm 83]: The worst-case complexity of the sorting problem is Ω(n log (n)) even if the operations “+”, “-”, “×”, “/” and queries ‘p(x) ∈ A?’ are possible where the rational functionp and the setA ?IR are arbitrary. At last, we describe the architecture of a network which actually searches polar minima inθ(T(j)) time units.     

On Harmonic Functions on Trees

We study the asymptotic behaviour of harmonic and p-harmonic functions (1<p<) on trees, obtaining estimates about the Hausdorff dimension of radial limits.