Abstract A p‐value of a sequence π = (x1, x2,…, xk) of elements of a finite metric space (X, d) is an element x for which \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}$\sum_{i=1}^{k}d^p(x,x_i)$\end{document} is minimum. The function ℓp with domain the set of all finite sequences defined by ℓp(π) = {x: x is a p‐value of π} is called the ℓp‐function on X. The ℓp‐functions with p = 1 and p = 2 are the well‐studied median and mean functions respectively. In this article, the ℓp‐function on finite trees is characterized axiomatically. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

Abstract When (X, d) is a finite metric space and π = (x1, …, xk) ∈ Xk, a central element for π is an element x of X for which max{d (x, xi): i = 1, …, k} is minimum. The function that returns the set of all central elements for any tuple π is called the center function on X. In this article, the center function on finite trees is characterized. © John Wiley & Sons, Inc.

Probe interval graphs have been introduced in the physical mapping and sequencing of DNA as a generalization of interval graphs. We prove that probe interval graphs are weakly triangulated, and hence are perfect, and characterize probe interval graphs by consecutive orders of their intrinsic cliques.

A consensus rule on a finite set X is a function c from the set of k-tuples for all $K > 0$ into the set of nonempty subsets of X. Elements in the image of c represent a consensus, or agreement, of the input. Axioms for consensus rules are presented, and when X is partially ordered, some consequences of these axioms are determined. A generalization of the median consensus rule is given when X is a distributive semilattice and is based on a weighting of the least move metric on the covering graph of X. It is characterized under the assumption that every join irreducible of X is an atom.

This paper examines the class of vertex-colored graphs that can be triangulated without the introduction of edges between vertices of the same color. This is related to a fundamental and long-standing problem for numerical taxonomists, called the Perfect Phylogeny Problem. These problems are known to be polynomially equivalent and NP-complete. This paper presents a dynamic programming algorithm that can be used to determine whether a given vertex-colored graph can be so triangulated and that runs in $O( ( n + m ( k - 2 ) )^{k + 1} )$ time, where the graph has n vertices, m edges, and k colors. The corresponding algorithm for the Perfect Phylogeny Problem runs in $O( r^{k + 1} k^{k + 1} + sk^2 )$ time, where s species are defined by kr-state characters.

Although molecular biologists often calculate consensus sequences from aligned DNA or protein sequences, relatively little is known about the properties of many of the consensus methods being used. Consequently, we wrote a program, CONSENSUS, to analyze and compare methods of calculating a consensus result (a base, an ambiguity code or a subset of codes) at a position in an aligned set of molecular sequences. The program supports alphabets of up to four symbols (e.g. [R,Y] or [A,C,G,T]). The program's output makes it suitable for exploratory data analysis or for selecting values of thresholds or confidence levels in consensus methods having such parameters.

If $D = ( V,A )$ is a digraph, its p-competition graph for p a positive integer has vertex set V and an edge between x and y if and only if there are distinct vertices $a_1, \cdots ,a_p $ in D with $( x,a_i )$ and $( y,a_i )$ arcs of D for each $i = 1, \cdots ,p$. This notion generalizes the notion of ordinary competition graph, which has been widely studied and is the special case where $p = 1$. Results about the case where $p = 2$ are obtained. In particular, the paper addresses the question of which complete bipartite graphs are 2-competition graphs. This problem is formulated as the following combinatorial problem: Given disjoint sets A and B such that $| A \cup B | = n$, when can one find n subsets of $A \cup B$ so that every a in A and b in B are together contained in at least two of the subsets and so that the intersection of every pair of subsets contains at most one element from A and at most one element from B?